[Optimiert] Explode Prozedur - Reloaded (Ersatz für CodeLib)

[alzaimar]

Hi!
Ich hab mir mal die Mühe gemacht, und eine alternative Explode-Funktion implementiert, die wohl doch etwas schneller ist, als die hier in der Code-Library hinterlegte Version.

Ich möchte Euch bitten, den Code zu testen und auch zu optimieren. Wenn wir damit durch sind, sollte diese Version in die Code-Library übernommen werden, bzw die jetzige Version ersetzen.

Details über die Herleitung (na ja, Recherche und Kopieren ) steht im Code.

[Edit] Unten genannte Tests sowie Zeitmessung eingearbeitet: Es ist ein komplettes Projekt mit Funktions- und Speed-Test. Bitte versucht, Teile davon zu optimieren (ASM, Pointer arithmetic etc.). [/edit]

History:
12.12. Version 1.1: Erste schwere Fehler ausgebaut: Strings am Ende wurden falsch bzw. gar nicht erkannt.
13.12. Version 1.2: Kleiner Fehler in der Prepare-Methode: (Hilfsvariable als Cardinal deklariert, bei Zuweisung <0 ignoriert), Facelifting auf Anregung von Elvis (Feld- und Variablennomenklatur). Ferner ist eine Test-Iterator-Basisklasse sowie ein Iterator für Char-Delimiter (z.B. für CSV) implementiert.
14.12 Version 1.3: Iterator für QS-Search implementier. Die Test-Routine wurde um Zeitmessungen für den Iterator sowie die Code-Library ergänzt.
23.12.07 Version 1.4: Beseitigt seltenen Bereichsüberlauf am Ende eines Strings.

Diese Version ist zwischen 4 und 1000x schneller als die Version aus der Code-Library.

[MStoll]

Hallo,

coole Sache, dass ihr mit vielen Leuten das Projekt angegangen seid, ne Funktion zu optimieren.
Ich wollte sie auch mal testen, um sie ggf. einzusetzen. Allerdings hab ich dabei (jedenfalls in meinem Fall) festgestellt, dass ich bereits ne schnellere Variante hatte (was mich angesichts eures Engagements bzgl. des Projekts etwas verwundert hatte).
Aber ehe ich hier irgendwie falsch liege, möchte ich euch bitten, meine Variante doch auch mal zu testen (sie arbeitet allerdings auf array of string und nicht mit einer StringList). Je nach Ergebnis eurer Tests könnt ihr mich sehr gerne korrigieren oder eben meine Variante einbauen.

Das soll jetzt nicht irgendwie eure Arbeit in Frage stellen, bitte nicht falsch verstehen. Ich wundere mich ja selbst über das Ergebnis meines Tests.

Delphi-Quellcode:

function explode(const n,s : string) : TStringDynArray;
var temp : array of integer;
    Len : integer;
    x, count, laenge : integer;

    function follows(const s,n : string; pos1 : integer) : boolean;
    var x : integer;
    begin
         {if pos1 + length(n) > length(s)+1 then
         begin
              result := false;
              exit;
         end;}

         for x := 0 to length(n)-1 do
             if n[x+1] <> s[pos1 + x] then
             begin
                  result := false;
                  exit;
             end;

         result := true;
    end;

begin
     x := 1;
     //SetLength(temp, 1);
     SetLength(temp, 20);
     count   := 1;
     temp[0] := 1;

     laenge := Length(s) - Length(n) + 1;

     while x <= laenge do
     begin
          if follows(s,n,x) then
          begin
               inc(x, length(n));
               //SetLength(temp, length(temp)+1);
               inc(count);
               if length(temp) < count then
                  SetLength(temp, count + 20);
               //temp[high(temp)] := x;
               temp[count-1] := x;
               continue;
          end;
          inc(x);
     end;
     SetLength(temp, count);

     SetLength(result, length(temp));
     for x := 0 to High(temp)-1 do
     begin
          Len := temp[x+1]-temp[x]-length(n);

          result[x] := copy(s, temp[x], Len);
     end;

     Len := length(s)-temp[high(temp)]+1;
     result[high(temp)] := copy(s, temp[high(temp)], Len);
end;

n ist das Pattern, s der große String.

Ich hab das getestet mit folgender Datei im Anhang, hab sie 8x hintereinander in einen String reingetan (damit es auch wirklich viele Daten sind) und dann mit verschiedenen Patterns (#10, ' ', '0') getestet.

Gruß
Michael

[C.Schoch]

Super vielen Dank alzaimar!

Bin aber selbst nicht ganz durchgestiegen warum der Fehler überhaupt auftritt, wäre nett wenn mir das mal einer erklären könnte, weil eigentlich bin ich ja mit dem Index noch im Breich des Arrays

[alzaimar]

@MStoll:
In der Testumgebung aus dem 1.Post schneidet Deine Version zwischen 1.2 und 4x langsamer ab, als die vorgestellte Variante mit QuickSearch. Das ist aber auch nicht weiter verwunderlich.

Der Quicksearch-Algorithmus spielt seine Stärken um so deutlicher aus, je länger der Suchtext und/oder Trenntext ist. Wenn der Trenntext aus genau einem Zeichen besteht, wird eine triviale Suche per Schleife aufgerufen. Du hast in deinen Tests ja nur nach diesem einen Zeichen gesucht und da wäre es denkbar, das Deine Variante aufgrund des geringeren Overheads besser abschneidet.

In einem anderen Thread wird die Basis, also das Suchen nach dem nächsten Vorkommen des 'Delimiters' optimiert. Ich hatte bisher noch keine Zeit, das in den TStringDivider einzubauen, es sollten sich jedoch bei kürzeren Delimitern noch drastische Geschwindigkeitsvorteile ergeben.

@C.Schoch:
Sei 'i' die aktuelle Position im Text T, p der zu suchende Text und Lp dessen Länge. Der Trick besteht darin, das Zeichen T[i+Lp] zu analysieren. Und dieser Wert T[i+Lp] kann eben leider auch Length(T)+1 sein. Das spielt unter C keine Rolle, denn dann ist T[i+Lp]=#0, aber bei Delphi ist das undefiniert, oder eben 'out of range'. Ich hatte immer den 'RangeCheck' ausgeschaltet, aber bei sehr großen Strings liegt dieser Wert dann trotzdem in der Pampa. Also muss man für den einen Fall (i=Length(T)-Lp+1) einen Sonderfall einbauen.

Beispiel:
Sei T='ABCDEFG', p= 'XYZ' und i=1. Da nun T[i+Lp]='D' nicht im Suchtext vorkommt, können wir gleich an die Stelle 5 springen und da unser Glück nochmal versuchen. Nun prüfen wir wieder das Zeichen T[i+Lp=5+3=8]. Hups, das gibts ja nicht, denn T ist ja nur 7 Zeichen lang=>Peng

[MStoll]

@alzaimar:
Ok, das kann gut sein. Hab es nicht mit mehr als einem Zeichen im Delimiter probiert.

[stoxx]

30%- 75% Prozent Performancegewinn gewinnst Du bei einem Seperator der Länge 1, wenn Du die lokale Funktion in der Explode Procedure weglässt.
(ein Zeichen als Seperator braucht man ja häufig für CSV Files)
Schon wenn die _AddString Procedure nur drin steht, und gar nicht aufgerufen wird, bricht die Performance durch den Aufruf-Stack massiv ein.
TStrings ist auch ein sehr schwieriges Nadelöhr. Vielleicht besser doch ein Dynarray als Ergebnistyp verwenden, neuerdings kann man ja auch Records Definieren, die einen String beinhalten können, obwohl nicht als Shortstring deklariert.
SetString könnte man noch durch die beste ASM Fastmove Funktion ersetzen. Dann wirds sogar noch schneller...
Wenn man dann noch mit CSV Dateien arbeitet, und weiß, dass eine Spalte wahrscheinlich nie länger als 255 Zeichen wird, dann ist shortstring noch etwas
schneller.
Dann schafft man es auch, eine 100 MB CSV-Datei in 1,5 sec komplett zu durchforsten

die funktion muss also raus:

Delphi-Quellcode:

  Procedure _AddString;
  Var
    sTmp: String;

  Begin
    SetString(sTmp,ptrSubStr,Integer(ptrText) - Integer(ptrSubStr));
    aItems.Add(sTmp)
  End;

neue Variante:

Delphi-Quellcode:

Procedure TStringDivider.Explode(Const aText: String; aItems: TStrings);
Var
  ptrSubStr,ptrText,ptrTextEnd: PChar;
  sTmp: String;
Begin
  If length(fPattern) > 1 Then
    QSExplode(aText,aItems)
  Else Begin
    aItems.clear;
    ptrText := PChar(@aText[1]);
    ptrSubStr := ptrText;
    ptrTextEnd := PChar(@aText[Length(aText)]);
    inc(ptrTextEnd);
    Repeat
      If ptrText^ = fPatternFirstChar Then Begin

        SetString(sTmp,ptrSubStr,Integer(ptrText) - Integer(ptrSubStr));
        aItems.Add(sTmp);

        inc(ptrText);
        ptrSubStr := ptrText;
      End
      Else
        inc(ptrText);
    Until Integer(ptrText) = Integer(ptrTextEnd);

    SetString(sTmp,ptrSubStr,Integer(ptrText) - Integer(ptrSubStr));
    aItems.Add(sTmp);


  End;
End;

Hier mal ein Performancevergleich:
Alte Variante:
-------------------
Using TStringDivider in TStringList
100 chars per line: 1000000 lines in 2907 tics, 343997 lines per sec, 33,6 mb/s (del = ";")
100 chars per line: 1000000 lines in 1297 tics, 771010 lines per sec, 75,3 mb/s (del = "<Foobar>")
100 chars per line: 1000000 lines in 2187 tics, 457247 lines per sec, 44,7 mb/s (del = "ABCDE")
10000 chars per line: 50000 lines in 3781 tics, 13224 lines per sec, 129,1 mb/s (del = ";")
10000 chars per line: 50000 lines in 1422 tics, 35162 lines per sec, 343,4 mb/s (del = "<Foobar>")
10000 chars per line: 50000 lines in 2188 tics, 22852 lines per sec, 223,2 mb/s (del = "ABCDE")
1000000 chars per line: 500 lines in 3281 tics, 152 lines per sec, 148,8 mb/s (del = ";")
1000000 chars per line: 500 lines in 1047 tics, 478 lines per sec, 466,4 mb/s (del = "<Foobar>")
1000000 chars per line: 500 lines in 1718 tics, 291 lines per sec, 284,2 mb/s (del = "ABCDE")

Neue Variante:
-----------------
100 chars per line: 1000000 lines in 2219 tics, 450653 lines per sec, 44,0 mb/s (del = ";")
100 chars per line: 1000000 lines in 1359 tics, 735835 lines per sec, 71,9 mb/s (del = "<Foobar>")
100 chars per line: 1000000 lines in 2172 tics, 460405 lines per sec, 45,0 mb/s (del = "ABCDE")
10000 chars per line: 50000 lines in 2234 tics, 22381 lines per sec, 218,6 mb/s (del = ";")
10000 chars per line: 50000 lines in 1438 tics, 34771 lines per sec, 339,6 mb/s (del = "<Foobar>")
10000 chars per line: 50000 lines in 2219 tics, 22533 lines per sec, 220,0 mb/s (del = "ABCDE")
1000000 chars per line: 500 lines in 1875 tics, 267 lines per sec, 260,4 mb/s (del = ";")
1000000 chars per line: 500 lines in 984 tics, 508 lines per sec, 496,2 mb/s (del = "<Foobar>")
1000000 chars per line: 500 lines in 1735 tics, 288 lines per sec, 281,4 mb/s (del = "ABCDE")



30% Performancezuwachs (del = ";") - 100 chars per line: 1000000 lines
70% Performancezuwachs (del = ";") - 10000 chars per line: 50000 lines
75% Performancezuwachs (del = ";") - 1000000 chars per line: 500 lines

[alzaimar]

Hi Stoxx,

Danke für die Tipps. Ich habe mittlerweile eine Version, die die FastCode-Gewinner mit einbezieht. Bei Trennern der Länge 1 ist die neue Version um ein vielfaches schneller.
Hier in der Delphi-Praxis habe ich den Suchalgorithmus zur Optimierung vorgestellt. Letztendlich habe ich eine Kombination aus FastCode und QSearch als bisherigen Outperformer implementiert.

Meine Pos-Version ist im Anhang, wenn Du magst, kannst Du das ja in die Explode-Routine einbauen. Ganz speziell das sehr schnelle 'CharPos' dürfte interessant sein.

In einer QSearch-Version war der Fehlerteufel drin. Ich hoffe, das das bei der hier nicht der Fall ist. Wenn der Trenner ganz am Ende steht, hat die ursprüngliche QSearch-Variante versagt. Die Version im Anhang arbeitet korrekt.

[edit] Was hab ich bloß für ungetesteten Müll auf meinem Laptop? Da war doch glatt ein Fehler drin [/edit]

Kurz getestet (CharPos und FastMove): Geschwindigkeitszuwachs 7-50%

[grenzgaenger]

Zitat von stoxx:

(ein Zeichen als Seperator braucht man ja häufig für CSV Files)

in CSV files hat man aber auch(sehr häufig) eingeklammerte zeichenketten. wie

Zitat:

1, 23, "hier wollen wir mal was schreiben, und hier gehts weiter", und 'n neuer string, auch das geht, 45 223

dabei müsste die folgende zerlegung herhauskommen bei 'n quote von " und 'n delemiter von ,

• 1
• 23
• hier wollen wir mal was schreiben, und hier gehts weiter
• und 'n neuer string
• auch das geht
• 45 223

aber dafür ist ja explode nicht gedacht, oder doch?

einen schönen guten morgen
GG

[alzaimar]

Nein.

[stoxx]

Zitat:

in CSV files hat man aber auch(sehr häufig) eingeklammerte zeichenketten. wie

na die müsste man halt getrennt rauslöschen, wir haben solche CSV Files nicht .. oder damit keine so häufigen Stringkopien gemacht werden, das Setstring so verändern, dass hochkommas nicht mit reingesetzt werden .. man müsste die Explodefunktion nur kurz umschreiben ...

[stoxx]

Zitat:

In einer QSearch-Version war der Fehlerteufel drin. Ich hoffe, das das bei der hier nicht der Fall ist. Wenn der Trenner ganz am Ende steht, hat die ursprüngliche QSearch-Variante versagt. Die Version im Anhang arbeitet korrekt.

hättest Du vielleicht die korriegierte Variante von QSearch bitte noch in Pascal Roh-Text? Ich hab immer gern beide Variante implementiert, falls mal irgendwas nicht funktioniert und der Code auf 128 Bit Windows nicht mehr laufen sollte
Das wäre ganz nett von Dir!!

Zitat:

Kurz getestet (CharPos und FastMove): Geschwindigkeitszuwachs 7-50%

hast Du jetzt FastPos in die Explodefunktion schon eingebaut?
Vielleicht magst die ja noch in den ersten Post dranhängen? ... nicht ersetzen, das wäre nicht gar so schön ...

Die kritischste Zeit in Deiner Implementierung ist eigentlich das zweimal "harte" kopierens des Strings einmal in einem Tempstring und dann nochmal in eine Tstringlist (TStrings) ..
Und zusätzlich glaube ich nicht, dass man die Dividerklasse so verwenden möchte, dass als Endprodukt eine Tstringliste der getrennten Strings haben möchte, sondern man möchte ja eher per Index auf die einzelnen Elemente zugreifen können. Man würde also Deine Rückgabe TStrings nochmal durchlaufen, und erst dann verarbeiten. Besser ist es also wenn man die reine Explodefunktion ohne Kapslung intelligent in seine eigene Klasse einbaut, die dann noch einen Indexzugriff hat, auf die einzelnen elemente per property hat, wo eine Stringkopie erst im allerletzten Moment zum beispiel an eine StrToFloatDef() Funktion geleitet wird...