Solved

Performance difference in string manipulation

Posted on 2001-08-19
14
199 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
  • 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
 
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
Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

 
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

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
IExtractImage Delphi 14 207
Multiple image collision 13 69
tvirtualstringtree freeze when load too manny images 10 53
PHP preg_replace code convert to Delphi 14 39
A lot of questions regard threads in Delphi.   One of the more specific questions is how to show progress of the thread.   Updating a progressbar from inside a thread is a mistake. A solution to this would be to send a synchronized message to the…
Have you ever had your Delphi form/application just hanging while waiting for data to load? This is the article to read if you want to learn some things about adding threads for data loading in the background. First, I'll setup a general applica…
This is used to tweak the memory usage for your computer, it is used for servers more so than workstations but just be careful editing registry settings as it may cause irreversible results. I hold no responsibility for anything you do to the regist…
Internet Business Fax to Email Made Easy - With eFax Corporate (http://www.enterprise.efax.com), you'll receive a dedicated online fax number, which is used the same way as a typical analog fax number. You'll receive secure faxes in your email, fr…

863 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

Need Help in Real-Time?

Connect with top rated Experts

18 Experts available now in Live!

Get 1:1 Help Now