What's happening with these string manipulation times?

From: Raptor (bogus_at_none.com)
Date: 12/30/04 

Date: Wed, 29 Dec 2004 17:06:11 -0800

I'm testing various aspects of string manipulation,
timing various routines I write and find posted
here and there.

My test consists of loading a 500,000 character text
file into a RichEdit, copying the RichEdit.Text to a
string, checking system tick count, running the function,
then getting elapsed time from another tick count check.
For example:

procedure TForm1.btnTestClick(Sender: TObject);
var
  aStr : string;
begin
  aStr := richedit1.Text;
  dbT(True); // Start timing.
  aStr := ReplaceStr(aStr, 'the', '***');
  dbM(dbT(False)); // Displays time via
dbm
  richedit1.Text := aStr; // popup message.
end;

I'm only timing the function, as you see. dbX are my
debug and test calls.

I've tried a number of routines. For two of them, listed
below, the first time I click the button after loading the
edit window with text, the function takes 80 and 30 SECONDS
respectively, but on subsequent clicks only 10 and 90 MILLI-
seconds respectively. If the file is reloaded, same pattern,
i.e., very long first click and short second+ click.

(A third routine, too long and complex to list, implements
BMH algorithm, etc., only takes about 20 milliseconds for
either
click.)

Can someone suggest what may be happening here, and even
better,
how one might avoid such behavior?

I have been testing third-party TreeView components for the
past several weeks, and find that a sluggish first-response
to a click or whatever, is not that uncommon.

What gives? Tests are on a 500MHz Celeron w/ 64MB.

Raptor

============== CODE =====================

// 80 seconds first time, .01 seconds the second.
function ReplaceStr(sSrc, sLookFor, sReplaceWith : string )
: string;
var
  nPos,
  nLenLookFor : integer;
begin
  nPos := Pos( sLookFor, sSrc );
  nLenLookFor := Length( sLookFor );
  while(nPos > 0)do
  begin
    Delete( sSrc, nPos, nLenLookFor );
    Insert( sReplaceWith, sSrc, nPos );
    nPos := Pos( sLookFor, sSrc );
  end;
  Result := sSrc;
end;

// 80 seconds first time, .09 seconds the second.
function _StringReplace(const S, OldPattern, NewPattern:
string; Flags: TReplaceFlags): string;
var
 i : integer;
SearchStr,
 Patt : string;
ChStart,
 ChPatt : PChar;
OldPattLen : integer;
NewPattLen : integer;
 Delta : integer;
begin
result:=S;
OldPattLen:=Length(OldPattern);
NewPattLen:=Length(NewPattern);
if rfIgnoreCase in Flags then begin
   SearchStr:=ANSIUppercase(S);
   Patt:=ANSIUpperCase(OldPattern);
end
else begin
   SearchStr:=S;
   Patt:=OldPattern;
end;
if OldPattLen > NewPattLen then begin // We may do only one
string truncation
   ChStart:=PChar(SearchStr);
   ChPatt:=ChStart;
   Delta:=0;
   while true do begin
     ChPatt:=StrPos(ChPatt, PChar(Patt));
     if ChPatt = nil then
       break;
     Move(NewPattern[1], result[ChPatt-ChStart+1-Delta],
NewPattLen);
     Move(result[(ChPatt-ChStart-Delta)+OldPattLen+1],
        result[ChPatt-ChStart+NewPattLen+1-Delta],
     Length(Result)-(ChPatt-ChStart-Delta)-OldPattLen);
     Delta:=Delta+OldPattLen-NewPattLen; // Keep track of
difference in positions between S and result
     if not (rfReplaceAll in Flags) then
       break;
     inc(ChPatt);
   end;
   SetLength(Result, Length(Result)-Delta);
end
else if OldPattLen < NewPattLen then begin // The slowest,
needs to enlarge string for each replacement
   ChStart:=PChar(SearchStr);
   ChPatt:=ChStart;
   Delta:=0;
   while true do begin
     ChPatt:=StrPos(ChPatt, PChar(Patt));
     if ChPatt = nil then
       break;
     SetLength(Result,
Length(Result)+NewPattLen-OldPattLen);
     Move(result[(ChPatt-ChStart)+Delta+OldPattLen+1],
result[(ChPatt-ChStart)+(NewPattLen)+Delta+1],
Length(Result)-(ChPatt-ChStart)-Delta-NewPattLen);
     Move(NewPattern[1], result[ChPatt-ChStart+1+Delta],
NewPattLen);
     Delta:=Delta+(NewPattLen-OldPattLen); // Keep track of
difference in positions between S and result
     if not (rfReplaceAll in Flags) then
       break;
     inc(ChPatt);
   end;
end
else if OldPattLen = 1 then begin // Just replace Chars...
   for i:=1 to Length(SearchStr) do
     if SearchStr[i] = Patt[1] then begin
       result[i]:=NewPattern[1];
       if not (rfReplaceAll in Flags) then
         break;
     end;
end
else begin // Equal length, but more than 1 char...keep
length, move chars
   ChStart:=PChar(SearchStr);
   ChPatt:=ChStart;
   while true do begin
     ChPatt:=StrPos(ChPatt, PChar(Patt));
     if ChPatt = nil then
       break;
     Move(NewPattern[1], result[ChPatt-ChStart+1],
OldPattLen);
     if not (rfReplaceAll in Flags) then
       break;
     inc(ChPatt);
   end;
end;
end;

Quantcast