Solved

Performance difference in string manipulation

Posted on 2001-08-19
14
205 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
Industry Leaders: 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

Independent Software Vendors: 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!

Question has a verified solution.

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

In this tutorial I will show you how to use the Windows Speech API in Delphi. I will only cover basic functions such as text to speech and controlling the speed of the speech. SAPI Installation First you need to install the SAPI type library, th…
In my programming career I have only very rarely run into situations where operator overloading would be of any use in my work.  Normally those situations involved math with either overly large numbers (hundreds of thousands of digits or accuracy re…
There's a multitude of different network monitoring solutions out there, and you're probably wondering what makes NetCrunch so special. It's completely agentless, but does let you create an agent, if you desire. It offers powerful scalability …
Monitoring a network: why having a policy is the best policy? Michael Kulchisky, MCSE, MCSA, MCP, VTSP, VSP, CCSP outlines the enormous benefits of having a policy-based approach when monitoring medium and large networks. Software utilized in this v…

729 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