Performance difference in string manipulation

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?
yurreaAsked:
Who is Participating?
 
MadshiConnect With a Mentor Commented:
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
 
d32coderCommented:
listening
0
 
JaccoCommented:
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
Free Tool: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

 
FrodoBegginsCommented:
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
 
JaccoCommented:
Oops...

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

Regards Jacco
0
 
yurreaAuthor Commented:
Madshi:

Great!

Thanks,
Yvann
0
 
FrodoBegginsCommented:
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
 
MadshiCommented:
Well...  :-)  I actually wondered about that, too. The answer to that could probably only give Borland...
0
 
JaccoCommented:
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
 
d32coderCommented:
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
 
yurreaAuthor Commented:
.. and the more strings to concat, the longer it would take for the code to execute.
0
 
yurreaAuthor Commented:
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
 
FrodoBegginsCommented:
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
 
yurreaAuthor Commented:
You're right!

:) Yvann
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.