In meinem Programm verarbeite ich Millionen von Zeichenfolgen, die einen speziellen Charakter haben, z. "|" Token innerhalb jeder Zeichenfolge zu trennen. Ich habe eine Funktion, um das n-te Token zurückzugeben, und das ist es:

function GetTok(const Line: string; const Delim: string; const TokenNum: Byte): string;
{ LK Feb 12, 2007 - This function has been optimized as best as possible }
var
 I, P, P2: integer;
begin
  P2 := Pos(Delim, Line);
  if TokenNum = 1 then begin
    if P2 = 0 then
      Result := Line
    else
      Result := copy(Line, 1, P2-1);
  end
  else begin
    P := 0; { To prevent warnings }
    for I := 2 to TokenNum do begin
      P := P2;
      if P = 0 then break;
      P2 := PosEx(Delim, Line, P+1);
    end;
    if P = 0 then
      Result := ''
    else if P2 = 0 then
      Result := copy(Line, P+1, MaxInt)
    else
      Result := copy(Line, P+1, P2-P-1);
  end;
end; { GetTok }

Ich habe diese Funktion bereits in Delphi 4 entwickelt. Sie ruft die sehr effiziente PosEx-Routine auf, die ursprünglich von Fastcode entwickelt wurde und jetzt in der StrUtils-Bibliothek von Delphi enthalten ist.

Ich habe kürzlich ein Upgrade auf Delphi 2009 durchgeführt und meine Zeichenfolgen sind alle Unicode. Diese GetTok-Funktion funktioniert immer noch und funktioniert immer noch gut.

Ich habe die neuen Bibliotheken in Delphi 2009 durchgesehen und es gibt viele neue Funktionen und Ergänzungen.

Ich habe jedoch in keiner der neuen Delphi-Bibliotheken und in den verschiedenen Fastcode-Projekten eine GetToken-Funktion gesehen, die ich benötige, und ich kann mit einer anderen Google-Suche nichts finden alsZarko Gajics: Delphi Split / Tokenizer-Funktionen, das ist nicht so optimiert wie das was ich schon habe.

Jede Verbesserung, sogar 10%, würde sich in meinem Programm bemerkbar machen. Ich weiß, dass StringLists eine Alternative ist und die Token immer getrennt zu halten, aber dies hat einen großen Overhead in Bezug auf den Speicher und ich bin nicht sicher, ob ich all diese Arbeit getan habe, um zu konvertieren, ob es noch schneller wäre.

Wütend. Nach all dem langwierigen Gerede lautet meine Frage nun wirklich:

Kennen Sie sehr schnelle Implementierungen einer GetToken-Routine? Eine Assembler-optimierte Version wäre ideal?

Wenn nicht, gibt es irgendwelche Optimierungen, die Sie an meinem obigen Code sehen können, die eine Verbesserung bewirken könnten?

Nachtrag: Barry Kelly erwähnte eine Frage, die ich vor einem Jahr gestellt hatte, um das Parsen der Zeilen in einer Datei zu optimieren. Zu diesem Zeitpunkt hatte ich noch nicht einmal an meine GetTok-Routine gedacht, die nicht für das Lesen oder Parsen verwendet wurde. Erst jetzt sah ich den Overhead meiner GetTok-Routine, der mich dazu veranlasste, diese Frage zu stellen. Bis zu den Antworten von Carl Smotricz und Barry hatte ich nie daran gedacht, die beiden miteinander zu verbinden. So offensichtlich, aber es hat sich einfach nicht registriert. Vielen Dank für den Hinweis.

Ja, mein Delim ist ein einzelner Charakter, daher kann ich natürlich einige wichtige Optimierungen vornehmen. Meine Verwendung von Pos und PosEx in der GetTok-Routine (oben) hat mich für die Idee blind gemacht, dass ich es mit einer Zeichen-für-Zeichen-Suche schneller machen kann, stattdessen mit Code-Bits wie:

      while (cp^ > #0) and (cp^ <= Delim) do    
        Inc(cp);

Ich werde alle Antworten durchgehen und die verschiedenen Vorschläge ausprobieren und vergleichen. Dann werde ich die Ergebnisse veröffentlichen.

Verwirrung: Okay, jetzt bin ich wirklich ratlos.

Ich habe die Empfehlung von Carl und Barry angenommen, mit PChars zu arbeiten, und hier ist meine Implementierung:

function GetTok(const Line: string; const Delim: string; const TokenNum: Byte): string;
{ LK Feb 12, 2007 - This function has been optimized as best as possible }
{ LK Nov 7, 2009 - Reoptimized using PChars instead of calls to Pos and PosEx }
{ See; https://stackoverflow.com/questions/1694001/is-there-a-fast-gettoken-routine-for-delphi }
var
 I: integer;
 PLine, PStart: PChar;
begin
  PLine := PChar(Line);
  PStart := PLine;
  inc(PLine);
  for I := 1 to TokenNum do begin
    while (PLine^ <> #0) and (PLine^ <> Delim) do
      inc(PLine);
    if I = TokenNum then begin
      SetString(Result, PStart, PLine - PStart);
      break;
    end;
    if PLine^ = #0 then begin
      Result := '';
      break;
    end;
    inc(PLine);
    PStart := PLine;
  end;
end; { GetTok }

Auf dem Papier denke ich nicht, dass Sie viel besser als das tun können.

Also habe ich beide Routinen für die Aufgabe verwendet und AQTime verwendet, um zu sehen, was passiert. In dem Lauf, den ich durchgeführt hatte, waren 1.108.514 Aufrufe von GetTok enthalten.

AQTime hat die ursprüngliche Routine auf 0,40 Sekunden festgelegt. Die Millionen Anrufe nach Pos dauerten 0,10 Sekunden. Eine halbe Million TokenNum = 1-Kopien dauerten 0,10 Sekunden. Die 600.000 PosEx-Aufrufe dauerten nur 0,03 Sekunden.

Dann habe ich meine neue Routine mit AQTime für denselben Lauf und genau dieselben Aufrufe geplant. AQTime berichtet, dass meine neue "schnelle" Routine 3,65 Sekunden dauerte, was 9-mal so lang ist. Der Täter laut AQTime war die erste Schleife:

     while (PLine^ <> #0) and (PLine^ <> Delim) do
       inc(PLine);

Die while-Zeile, die 18 Millionen Mal ausgeführt wurde, wurde mit 2,66 Sekunden angegeben. Die 16 Millionen Mal ausgeführte Inc-Linie soll 0,47 Sekunden gedauert haben.

Jetzt glaubte ich zu wissen, was hier vor sich ging. Ich hatte ein ähnliches Problem mit AQTime in einer Frage, die ich letztes Jahr gestellt habe:Warum ist CharInSet schneller als die Case-Anweisung?

Wieder war es Barry Kelly, der mich darauf aufmerksam gemacht hat. Grundsätzlich ist ein Instrumentierungsprofiler wie AQTime nicht unbedingt für die Mikrooptimierung geeignet. Es fügt jeder Zeile einen Overhead hinzu, der die Ergebnisse überschwemmen kann, die in diesen Zahlen deutlich gezeigt werden. Die 34 Millionen Zeilen, die in meinem neuen "optimierten Code" ausgeführt werden, überwältigen die mehreren Millionen Zeilen meines ursprünglichen Codes, wobei die Routinen Pos und PosEx anscheinend nur wenig oder gar keinen Aufwand verursachen.

Barry gab mir ein Codebeispiel mit QueryPerformanceCounter, um zu überprüfen, ob und in welchem ​​Fall er korrekt war.

Okay, machen wir jetzt dasselbe mit QueryPerformanceCounter, um zu beweisen, dass meine neue Routine schneller und nicht 9-mal langsamer ist, als es AQTime sagt. Also los geht's:

function TimeIt(const Title: string): double;
var  i: Integer;
  start, finish, freq: Int64;
  Seconds: double;
begin
  QueryPerformanceCounter(start);
  for i := 1 to 250000 do
    GetTokOld('This is a string|that needs|parsing', '|', 1);
  for i := 1 to 250000 do
    GetTokOld('This is a string|that needs|parsing', '|', 2);
  for i := 1 to 250000 do
    GetTokOld('This is a string|that needs|parsing', '|', 3);
  for i := 1 to 250000 do
    GetTokOld('This is a string|that needs|parsing', '|', 4);
  QueryPerformanceCounter(finish);
  QueryPerformanceFrequency(freq);
  Seconds := (finish - start) / freq;
  Result := Seconds;
end;

Damit werden 1.000.000 Aufrufe von GetTok getestet.

Meine alte Prozedur mit den Aufrufen Pos und PosEx dauerte 0,29 Sekunden. Das neue mit PChars hat 2,07 Sekunden gedauert.

Jetzt bin ich total verwirrt! Kann mir jemand sagen, warum das PChar-Verfahren nicht nur langsamer ist, sondern 8- bis 9-mal langsamer !?

Geheimnis gelüftet! Andreas sagte in seiner Antwort, den Delim-Parameter von einem String in einen Char zu ändern. Ich werde immer nur ein Char verwenden, also ist dies zumindest für meine Implementierung sehr gut möglich. Ich war erstaunt, was passiert ist.

Die Zeit für die 1 Million Anrufe ging von 1,88 Sekunden auf 0,22 Sekunden zurück.

Und überraschenderweise stieg die Zeit für meine ursprüngliche Pos / PosEx-Routine von 0,29 auf 0,44 Sekunden, als ich den Delim-Parameter in ein Char änderte.

Ehrlich gesagt bin ich von Delphis Optimierer enttäuscht. Das Delim ist ein konstanter Parameter. Das Optimierungsprogramm sollte bemerkt haben, dass dieselbe Konvertierung in der Schleife stattfindet, und sollte sie herausbewegt haben, damit sie nur einmal ausgeführt wird.

Ich überprüfe meine Parameter für die Codegenerierung noch einmal. Ja, ich habe Optimization True und String Formatprüfung deaktiviert.

Das Fazit ist, dass die neue PChar-Routine mit Andrea's Fix ungefähr 25% schneller ist als meine ursprüngliche (.22 versus .29).

Ich möchte die anderen Kommentare hier noch weiter verfolgen und ausprobieren.

Durch Deaktivieren der Optimierung und Aktivieren der String-Formatprüfung wird nur die Zeit von .22 auf .30 erhöht. Es fügt ungefähr das gleiche zum Original hinzu.

Der Vorteil der Verwendung von Assembler-Code oder des Aufrufs von Routinen, die in Assembler wie Pos oder PosEx geschrieben wurden, besteht darin, dass sie NICHT den von Ihnen festgelegten Codegenerierungsoptionen unterliegen. Sie laufen immer auf die gleiche Art und Weise, eine voroptimierte und nicht aufgeblähte Art und Weise.

Ich habe in den letzten Tagen erneut bestätigt, dass der beste Weg, Code für die Mikrooptimierung zu vergleichen, darin besteht, den Assembler-Code im CPU-Fenster zu betrachten und zu vergleichen. Es wäre schön, wenn Embarcadero dieses Fenster etwas komfortabler machen könnte und es uns erlauben würde, Teile in die Zwischenablage zu kopieren oder Teile davon zu drucken.

Außerdem habe ich AQTime zu Beginn dieses Beitrags zu Unrecht zugeschlagen, da ich dachte, dass die zusätzliche Zeit für meine neue Routine ausschließlich auf die hinzugefügte Instrumentierung zurückzuführen ist. Jetzt, da ich zurückgehe und mit dem Parameter Char anstelle von String überprüfe, ist die while-Schleife auf .30 Sekunden (von 2,66) und die inc-Zeile auf .14 Sekunden (von .47) reduziert. Seltsam, dass die Inc-Linie auch runtergehen würde. Aber ich bin von all diesen Tests schon erschöpft.

Ich nahm Carls Idee, eine Schleife nach Zeichen zu machen, und schrieb diesen Code mit dieser Idee um. Es macht eine weitere Verbesserung, bis auf .19 Sekunden von .22. Also hier ist jetzt das bisher beste:

function GetTok(const Line: string; const Delim: Char; const TokenNum: Byte): string;
{ LK Nov 8, 2009 - Reoptimized using PChars instead of calls to Pos and PosEx }
{ See; https://stackoverflow.com/questions/1694001/is-there-a-fast-gettoken-routine-for-delphi }
var
  I, CurToken: Integer;
  PLine, PStart: PChar;
begin
  CurToken := 1;
  PLine := PChar(Line);
  PStart := PLine;
  for I := 1 to length(Line) do begin
    if PLine^ = Delim then begin
      if CurToken = TokenNum then
        break
      else begin
        CurToken := CurToken + 1;
        inc(PLine);
        PStart := PLine;
      end;
    end
    else
      inc(PLine);
  end;
  if CurToken = TokenNum then
    SetString(Result, PStart, PLine - PStart)
  else
    Result := '';
end;

Es kann noch einige kleinere Optimierungen geben, wie zum Beispiel den Vergleich CurToken = Tokennum, der vom selben Typ sein sollte, Integer oder Byte, je nachdem, welcher schneller ist.

Aber sagen wir mal, ich bin jetzt glücklich.

Nochmals vielen Dank an die StackOverflow Delphi-Community.