Stringoperationen :: Performancemessung am bsp ANSI->ASCII

[choose]

Hallo X-Dragon,
ich beschreibe im Folgenden Messungen, die sich aus unserer Diskussion im Thread ASCII <-> ANSI ergaben, aber nichts mit der eigentlichen Fragegestellung zu tun haben.

Ausgangspunkt dieser Messung war die Frage nach einer performanteren Funktion, die eine veränderte Kopie eines Eingabestrings zurückgibt, etwa in dieser Form:

Delphi-Quellcode:

function GetModifiedString(const AnInputString: string): string;
var
  iChar: Integer;
begin
  Result:= '';
  for iChar:= 1 to Length(AnInputString) do
  case AnInputString[iChar] of
    ACharOne: Result:= Result+AnotherCharOne;
    ACharTwo: Result:= Result+AnotherCharTwo;
  else
    Result:= Result+AnInputString[iChar];
  end;
end;

Unter der Vorraussetzung, dass die Länge des Ergebnisstrings identisch mit der des Eingabestrings ist, sollte eine Lösung der Form

Delphi-Quellcode:

function GetModifiedString(const AnInputString: string): string;
var
  iChar: Integer;
begin
  Result:= AnInputString;
  for iChar:= Length(AnInputString) downto 1 do
  case Result[iChar] of
    ACharOne: Result[iChar]:= AnotherCharOne;
    ACharTwo: Result[iChar]:= AnotherCharTwo;
  end;
end;

ungleich performanter sein.
Die hier dargestellten Ergebnisse sollen das bestätigen.


Die im Folgenden diskutierte Referenzimplementierung verwendet die von X-Dragon dargestellte Implementierung als "Originalversion" (I) im Vergleich zu einer gemäß der Zielstellung der Messung angepssten Version (II). In Anlehnung an die erwähnte Problemstellung, wird der Durchsatz der Routinen an 131072 (2^17) zufälligen Strings der festen Länge 8 getestet und ausgewertet. Diese Messung wird im Beispiel 8 mal für die jeweilige Implementierung wiederholt, um den Effekt von Einflussgrößen wie Caching, Fragmentierung, etc. zu minimieren bzw. zu erkennen.

Delphi-Quellcode:

program Project1;
{$APPTYPE CONSOLE}
uses
  SysUtils,
  Windows;

type
  TANSIToASCIIFunc = function(const AnInputString: string): string;

//:Orginal implementation (I) by X-Dragon
function AnsiToIBMAscii(const s: string): string;
var
  i : Integer;
begin
  Result:= '';

  for i := 1 to Length(s) do
    case s[i] of
      #196: Result := Result + #142; // von Ä
      #214: Result := Result + #153; // von Ö
      #220: Result := Result + #154; // von Ü
      #228: Result := Result + #132; // von ä
      #246: Result := Result + #148; // von ö
      #252: Result := Result + #129; // von ü
      #223: Result := Result + #225; // von ß
    else
      Result := Result + s[i];
    end;
end;

//:Modified implementation (II)
function AnsiToIBMAsciiRefactored(const AnInput: string): string;
var
  iChar : Integer;
begin
  Result:= AnInput;
  for iChar := Length(Result) downto 1 do
    case Result[iChar] of
      #196: Result[iChar] := #142; // von Ä
      #214: Result[iChar] := #153; // von Ö
      #220: Result[iChar] := #154; // von Ü
      #228: Result[iChar] := #132; // von ä
      #246: Result[iChar] := #148; // von ö
      #252: Result[iChar] := #129; // von ü
      #223: Result[iChar] := #225; // von ß
    end;
end;

//:Tests performance of AFunc against strings of AnArray
procedure DoTest(const AMessage: string; const AnArray: array of string;
  const AFunc: TANSIToASCIIFunc);
var
  iRun: Integer;
  iString: Integer;
  iStartTime: Cardinal;
  iNeedTime: Cardinal;
begin
  // run test eight times
  // might reveal problems with fragmentation
  for iRun:= 0 to 7 do
  begin
    // retrieve start time (in msecs)
    iStartTime:= GetTickCount;
    // call ANSI->ASCII converter for every string in AnArray
    for iString:= Low(AnArray) to High(AnArray) do
      AFunc(AnArray[iString]);
    // calculate needed time (in msecs
    iNeedTime:= GetTickCount-iStartTime;

    // output result
    Writeln(Format('%s (Run %d): %d msec (%d per sec)',
      [AMessage, Succ(iRun), iNeedTime,
       Length(AnArray)*1000 div Succ(iNeedTime)]));
  end;
end;

//:Regression test on given functions against string array
procedure EnsureSameResults(const AStrings: array of string;
  const AFunctions: array of TANSIToASCIIFunc);
var
  iString: Integer;
  iFunc: Integer;
  myResult: string;
begin
  Assert( Length(AFunctions)>=1 );

  // test every string in array
  for iString:= Low(AStrings) to High(AStrings) do
  begin
    // store result of first function in array
    myResult:= AFunctions[0](AStrings[iString]);

    // test stored result against result of every other function in array
    for iFunc:= Succ(Low(AFunctions)) to High(AFunctions) do
      if myResult<>AFunctions[iFunc](AStrings[iString]) then
      begin
        Writeln(Format('ERROR: String(%d)="%s", myResult="%s", AFunctions[%d]="%s"',
          [iString, AStrings[iString], myResult, iFunc,
           AFunctions[iFunc](AStrings[iString])]));
        Readln;
        Halt;
      end;
  end;

  Writeln(Format('Every function (%d) returns same result ',
    [Length(AFunctions)]));
end;

//:Creates random string with length of ALen
function MakeRandomString(const ALen: Cardinal): string;
var
  iChar: Cardinal;
begin
  SetLength(Result, ALen);
  // use only "visible" chars (ASCII-Value>=Space-Value)
  for iChar:=1 to ALen do
    Result[iChar]:= Char(32+Random(224));
end;

var
  myStrings: array[0..131071] of string;
  i: Integer;
begin
  // fill array with random strings
  for i:= Low(myStrings) to High(myStrings) do
    myStrings[i]:= MakeRandomString(8);
  writeln(Format('Created %d random strings', [Length(myStrings)]));

  // test functions
  EnsureSameResults(myStrings, [AnsiToIBMAscii, AnsiToIBMAsciiRefactored]);

  // do test with original version
  DoTest('origin', myStrings, AnsiToIBMAscii);
  // do test with refactored version
  DoTest('refact', myStrings, AnsiToIBMAsciiRefactored);

  Readln;
end.

Die Ausgabe des Programms eines beliebigen Laufs auf einem AMD Athlon 1,2 GHz unter Win2K hatte diese Gestalt:

Code:

Created 131072 random strings
Every function (2) returns same result
origin (Run 1): 771 msec (169782 per sec)
origin (Run 2): 761 msec (172010 per sec)
origin (Run 3): 761 msec (172010 per sec)
origin (Run 4): 762 msec (171785 per sec)
origin (Run 5): 771 msec (169782 per sec)
origin (Run 6): 771 msec (169782 per sec)
origin (Run 7): 771 msec (169782 per sec)
origin (Run 8]: 761 msec (172010 per sec)
refact (Run 1): 80 msec (1618172 per sec)
refact (Run 2): 80 msec (1618172 per sec)
refact (Run 3): 70 msec (1846084 per sec)
refact (Run 4): 80 msec (1618172 per sec)
refact (Run 5): 70 msec (1846084 per sec)
refact (Run 6): 71 msec (1820444 per sec)
refact (Run 7): 90 msec (1440351 per sec)
refact (Run 8]: 70 msec (1846084 per sec)

Es ist zu erkennen, dass beide Varianten mit konstanter Geschwindigkeit arbeiten, also keine Probleme mit Speicherfragementierung oä auftreten (@X-Dragon: Die voreilige Äußerung zur Zunahme der Zeit bei (I) begründete sich in der Tatsache, dass bei jedem Aufruf an Result Konkateniert wurde), und (II) im Vergleich zu (I) 10 mal schneller arbeitet.
Eine Profiler-Analyse (inkl Debug-DCUs mit AQTime3) ergab, für die Unteraufrufe aus (I) und (II) Folgendes:

Code:

Routine Name  | % Time w C | Hit Count
--------------+------------+----------      
LStrFromChar  |      50,01 |  1015812
LStrCat       |      34,35 |  1048576
LStrClr       |       8,85 |   262144
(body only)   |       4,53 |   131072
LStrLen       |       2,26 |   131072

                    Ergebnisse für (I)



Routine Name  | % Time w C | Hit Count
--------------+------------+---------
(body only)   |      43,18 |   131072
LStrAsg       |      41,22 |   131072
UniqueStringA |      15,33 |    32764
LStrLen       |       0,27 |   131072

                   Ergebnisse für (II)

Die Tabellen zeigen in der Spalte "% Time with Children" die "verbrachte Zeit" in Unteraufrufen bzw. dem Code der Routine selbst ("body only") sowie die Anzahl der Aufrufe bei 131072 zu verarbeitenen Strings.

Es ist deutlich zu erkennen, dass (I) den Großteil der Zeit (>95%) mit der Verarbeitung von Strings (Alloziierung, Kopieren, etc.) statt mit der Fallunterscheidung, der eigentlichen Programmlogik, zubringt. In (II) hingegen, wird über 40% der Zeit für die Programmlogik genutzt und auch die Funktionen zur Stringverarbeitung werden maximal einmal pro Aufruf von (II) verwendet. Die Lösung (I) hingegen verwendet selbige etwa achtmal häufiger, was der Länge der zu verarbeitenen Strings entspricht.

Die Testergebnisse zeigen, dass die Variante (II) bedingt durch effizientere Stringverarbeitung im Rahmen des Testszenarios etwa 10 mal schneller ist.
Strings der Länge 4096 konnten diesen Quotienten auf über 26 Erhöhen.

Ich hoffe, dass die Ergebnisse dieses Beitrags helfen können, Programme mit Stringverarbeitung performanter zu gestalten, ohne direkten Speicherzugriff, zB in Form von PChar oder ASM, verwenden zu müssen.

[edit=sakura] Leerzeichen eingefügt Mfg, sakura[/edit]