Solved

Performance difference in string manipulation

Posted on 2001-08-19
14
203 Views
Last Modified: 2012-05-04
Case #1

  ...

Str := '';

for i := 1 to 10000 do
begin
  Str := Str + '1234567890ABCDEFGHIJKLMNOPQRSTUVWXYZ' + '1234567890ABCDEFGHIJKLMNOPQRSTUVWXYZ'
end

  ...


Cast #2

Str := ''

for i := 1 to 10000 do
begin
  Str := Str + '1234567890ABCDEFGHIJKLMNOPQRSTUVWXYZ'
  Str := Str + '1234567890ABCDEFGHIJKLMNOPQRSTUVWXYZ'
end

  ...



Question:

Why is it that Case #2 performs much faster than Case #1?
0
Comment
Question by:yurrea
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 4
  • 3
  • 3
  • +2
14 Comments
 

Expert Comment

by:d32coder
ID: 6404993
listening
0
 
LVL 10

Expert Comment

by:Jacco
ID: 6405125
Because in the first case delphi precalculates the constant expression.

case 1 is compiled like:

Str := '';

for i := 1 to 10000 do
begin
 Str := Str + '1234567890ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890ABCDEFGHIJKLMNOPQRSTUVWXYZ'
end

So the first case has only 10000 string concats and the second case 20000.

A quicker solution would be:

 Str := '1234567890ABCDEFGHIJKLMNOPQRSTUVWXYZ';

 for i := 1 to 13 do
 begin
   Str := Str + Str;
   if i =  4 then Str4 := Str;
   if i =  8 then Str8 := Str;
   if i =  9 then Str9 := Str;
   if i = 10 then Str10 := Str;
 end;

 Str := Str + Str4 + Str8 + Str9 + Str10;

Because there you have only 17 concats.

Regards Jacco


0
 
LVL 2

Expert Comment

by:FrodoBeggins
ID: 6405139
Yes, Jacco, that's what even I think. But read the question more carefuly: "Why is it that Case #2 performs much faster than Case #1?". Or why 20000 concats are much faster than 10000?

Rgds,
Frodo
0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 10

Expert Comment

by:Jacco
ID: 6405162
Oops...

That seems odd. Have you checked the cpu window? To see what ASM delphi complies?

Regards Jacco
0
 
LVL 20

Accepted Solution

by:
Madshi earned 100 total points
ID: 6405191
The first assignment ends up in something like this:

Str := '';
for i := 1 to 10000 do
begin
  _LStrCatN(Str, 3, Str, '1234567890ABCDEFGHIJKLMNOPQRSTUVWXYZ', '1234567890ABCDEFGHIJKLMNOPQRSTUVWXYZ');
end;

Where _LStrCatN looks like this (see System.pas):

procedure _LStrCatN(var dest: string; argCnt: integer; arg1: string; [arg2: string;] [arg3: string] [...]);

In other words, a *new* string is allocated and build together from 3 strings, namely the old "Str" and 2x the 1-Z string.

The second assignment ends up in something like this:

// procedure _LStrCat(var dest: string; source: string);

Str := ''
for i := 1 to 10000 do
begin
  _LStrCat(Str, '1234567890ABCDEFGHIJKLMNOPQRSTUVWXYZ');
  _LStrCat(Str, '1234567890ABCDEFGHIJKLMNOPQRSTUVWXYZ');
end

The second loop is much faster, because there's not a new string allocated all the time, instead "Str" really gets changed only. That can save a lot of allocations.

Jaccos first loop is exactly as fast as yurrea's second loop, so Jaccos conclusions are evidently wrong (I'm sorry)...

Regards, Madshi.
0
 

Author Comment

by:yurrea
ID: 6405232
Madshi:

Great!

Thanks,
Yvann
0
 
LVL 2

Expert Comment

by:FrodoBeggins
ID: 6405272
Great, Madshi. I knew you're the one to answer here. But here's an interesting question: why the compiler doesn't call the faster
   procedure _LStrCat3{var dest:AnsiString; source1: AnsiString; source2: AnsiString};
instead of
   procedure _LStrCatN{var dest:AnsiString; argCnt: Integer; ...};

:-))

Rgds,
Frodo
0
 
LVL 20

Expert Comment

by:Madshi
ID: 6405304
Well...  :-)  I actually wondered about that, too. The answer to that could probably only give Borland...
0
 
LVL 10

Expert Comment

by:Jacco
ID: 6407050
Hi,

Yep I was obviously wrong :(

Another interesting question is why Borlands expression evaluator does not optimize the expression itself by concatting the to constant strings at compile time...

Regards Jacco
0
 

Expert Comment

by:d32coder
ID: 6407459
probably because he's concatting 2 constants

Str := Str + '1234567890ABCDEFGHIJKLMNOPQRSTUVWXYZ' + '1234567890ABCDEFGHIJKLMNOPQRSTUVWXYZ'

most programmers would concat these two constants at 'write-time'.

Str := Str + '1234567890ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890ABCDEFGHIJKLMNOPQRSTUVWXYZ'

0
 

Author Comment

by:yurrea
ID: 6408215
.. and the more strings to concat, the longer it would take for the code to execute.
0
 

Author Comment

by:yurrea
ID: 6408240
here's one more:


case 1: { concat str with constants }

str := '';
for i := 1 to 4000 do
begin
  str := str + 'abcdefg' + 'abcdefg';
end;


case 2: { concat str with variables }

str := '';
for i := 1 to 4000 do
begin
  str := str + var1 + var2;
end;


case 3: { concat str with self }

str := '';
for i := 1 to 4000 do
begin
  str := str + str + str;
end;


Case 1 concatinates str with two constants.  Case 2 concatinates str with two string variables.  It takes Case 1 and Case 2 the same amount of time to execute.  However, Case 3 which concatinates with itself executes A LOT FASTER than Cases 1 & 2.

TESTING RESULT:
Case 1 - 3 seconds.
Case 2 - 3 seconds.
Case 3 - less than a second.

Case 2 and Case 3 is similar in a way that it concatinates variables.  However, the performance difference is very noticeable.  Why is that?
0
 
LVL 2

Expert Comment

by:FrodoBeggins
ID: 6408652
Nope. Case3 does nothing. It concatenates nothng. The string is empty. It takes no time to complete the folowing too:
  str := '';
  for i := 1 to 40000 do
    str := str + '' + '';
That calls the procedure _LStrCatN, but the procedure is smart enough to exit fast :-)

Rgds,
Frodo
0
 

Author Comment

by:yurrea
ID: 6408669
You're right!

:) Yvann
0

Featured Post

Free Tool: Subnet Calculator

The subnet calculator helps you design networks by taking an IP address and network mask and returning information such as network, broadcast address, and host range.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

This article explains how to create forms/units independent of other forms/units object names in a delphi project. Have you ever created a form for user input in a Delphi project and then had the need to have that same form in a other Delphi proj…
Creating an auto free TStringList The TStringList is a basic and frequently used object in Delphi. On many occasions, you may want to create a temporary list, process some items in the list and be done with the list. In such cases, you have to…
In an interesting question (https://www.experts-exchange.com/questions/29008360/) here at Experts Exchange, a member asked how to split a single image into multiple images. The primary usage for this is to place many photographs on a flatbed scanner…
Attackers love to prey on accounts that have privileges. Reducing privileged accounts and protecting privileged accounts therefore is paramount. Users, groups, and service accounts need to be protected to help protect the entire Active Directory …

734 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question