[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.

[stoxx]

Zitat:

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.

Das habe ich nun ausgiebig getestet und kann man soooo pauschal nicht sagen.
Deine ASM FastPosEx ist in meinem Anwendungsfall überhaupt nicht zu gebrauchen und braucht mehr als doppelt so lange, wie Deine effiziente Pointerlösung. (allerdings ist eine Modifikation notwendig)
Es kommt immer auf den Kontext der Anwendung an, und man sollte es einfach mal austesten.

Im groben kann man aber folgende Ergebnisse zusammenfassen.

1. Die StringDivider im ersten Posting sollte man einsetzen, wenn man die Ergebnisse sowieso in einer TStrings Variable braucht.
2. Man sollte sich überlegen, ob man das nicht irgendwie umgehen kann, in dem man die Elemente in einem dynamischen Array speichert.
(natürlich setlength nicht bei jeder einzelnen erhöhung vergrößern, sondern schrittweise.
3. in der Version im ersten Posting muss noch die lokale Procedure unbedingt entfernt werden. (siehe mein Beitrag)
4. Bei wichtigen zeitkritischen Anwendungen die Explode Funktion aus der Klasse einfach in die eigene Klasse integrieren, die dann direkt mit den Member Variabeln arbeitet ... die Übergabe in TStrings ist sehr lahm....

FastPosEx sollte man nehmen, wenn man einen großen Datenbestand nach selten vorkommenden Strings durchsucht, dann aber wird die Geschwindigkeit unschlagbar gegenüber den anderen Lösungen. Die häufigen Funktionsaufrufe und Übergaben erweisen sich dann als negativ, wenn man nur einen Char als Sperator mit kurzen Zeilen hat. (Bei kurzen Zeilen meinte ich Bildschirmbreite) .. Im Falle meiner 100 MB CSV Referenz-Datei mit ca 90 Zeichen Breite und ca 25 Spalten (wo auch einige Leerspalten enthalten sind .. also einige Kommas nebeneinander) war die Pointerlösung aus dem ersten Posting unschlagbar.

Eine Lösung mit FastPosEx wird umso interessanter, je größer das Verhältnis Wortlänge/Vorkommen des Seperators ist.
Dafür wird dann aber FastPosEx wahnsinnig schnell, im Vergleich zu den anderen Varianten.
Bei einer durchschnittlichen Wortlänge von 5 Zeichen zwischen den Seperatoren ist FastPosEx die Hälfte langsamer.
Ab einer Wortlänge von durchschnittlich 10 Zeichen, ist es ungefähr gleich schnell.
Wobei man die Ergebnisse nicht direkt vergleichen kann, ich bin davon ausgeganen, dass man die Strings eventuell nicht in einer Stringlist braucht ..
Für CSV Dateien erwies es sich als ungeeignet. (zum vergleich: Pointerlösung- 100MB CSV Datei 1500 ms ... dieselbe Funktionalität mit FastPosEx 3500 ms)

[alzaimar]

Ich habe mal die FastCode-Routinen eingebaut.
Ergebnis: Bei einem einstelligen Trennzeichen (z.B. ';') ergeben sich Performancesteigerungen (MB/s) von 10-150% (die 150% natürlich bei extrem langen Strings), bei einem Trennzeichen mit weniger als 4 Zeichen ergeben sich Steigerungen von 10-30%. Bei Trennzeichen mit mehr als 4 Zeichen ist QuickSearch eh am schnellsten, also wird sich da nix tun.

Ich mag TStrings bzw. den Umgang damit.Man hat einen 50% Overhead ggü einem DynArray (dynamische Anpassung des Arrays, jeweils verdoppelung der Größe), dafür muss man sich aber um nix kümmern. Ich finde, mit den 50% kann man in den meisten Fällen leben (Man spart z.B. bei 1.000.000 Lese- und Schreibzugriffen ca. 250ms ein... Na ja.)

Wenn man aber an dem Teil feilen will, dann sollte man ein dynamisches StringArray befüllen.

Eventuell bring es was die TStringDivider-Klasse so umschreiben, das beim Explode gar keine Stringlisten erzeugt werden, sondern nur die Positionen der einzelnen Substrings im Text. Über eine Array-Eigenschaft 'Substrings[Index : Integer]' kann man dann auf die einzelnen Elemente zugreifen. Da hier nur ein String-Copy zum Einsatz kommt (beim Abrufen des SubStrings), könnte das etwas schneller werden.

Weiterhin sollte man die FastMove-Routine einbauen, das dürfte das 'String Copy' nochmals optimieren.

Wenn man dann noch die '"' - Behandlung implementiert, sollte Alle zufrieden sein. Ich mach mich heute Abend mal ans Werk.

[mimi]

Zitat:

Für CSV Dateien erwies es sich als ungeeignet. (zum vergleich: Pointerlösung- 100MB CSV Datei 1500 ms ... dieselbe Funktionalität mit FastPosEx 3500 ms)

Und ich dachte immer ASM sei so schnell..... aber nicht schlecht 100MB mit nur 1500 MS zu durchsuchen, Komplett ? also von vorne bis hinten ?

Zitat:

Wenn man dann noch die '"' - Behandlung implementiert, sollte Alle zufrieden sein.

Ja ! Das währe toll. Dann könnte ich die Funktion in meinem Aktuellen Projekt benutzten. Wenn die so schnell ist. Meins ist leider nicht so schnell.

[stoxx]

Bei einem einstelligen Trennzeichen (z.B. ';') ergeben sich Performancesteigerungen (MB/s) von 10-150% (die 150% natürlich bei extrem langen Strings),
100 chars per line: 1000000 lines in 2907 tics, 343997 lines per sec, 33,6 mb/s (del = ";")

das kann man mal als Referenz für den meinen Rechner nehmen.
Es stimmt, mit Fastcode erreicht man steigerungen in dem Bereich um ungefähr 100 Prozent.
Ich bin aber nun schon bei ca. um die 80 - 90 MB/s,
Wenn man nicht alle Spalten der CSV Datei benötigt, sogar auf 115 MB.
Das langsame sind nämlich die Stringkopien.
Ich habe es mit einem Pointerarray gelöst,das gespeichert wird, und erst beim Get_Zugriff auf den Index, wird der String mit SetString() kopiert.

Zitat:

Wenn man aber an dem Teil feilen will, dann sollte man ein dynamisches StringArray befüllen.

am besten gar nix befüllen nur wenn es gebraucht wird, da würdest Du ja nochmal einen String kopieren, das ist ja das lahme, eine reine PChar verwendung wäre die Lösung. die Fastcode Lösungen haben alle generell den Nachteil, dass sie nur reine Strings annehmen ....
Vielleicht bastel ich mir auch nochmal einen reinen PChar Textreader, dann gänge es sogar noch schneller
Dann entfällt NOCH einmal umkopieren. (100 Prozent Performance mehr)

Zitat:

Eventuell bring es was die TStringDivider-Klasse so umschreiben, das beim Explode gar keine Stringlisten erzeugt werden, sondern nur die Positionen der einzelnen Substrings im Text

so hab ichs gemacht ...

Zitat:

aber nicht schlecht 100MB mit nur 1500 MS zu durchsuchen, Komplett ? also von vorne bis hinten ?

ja, sollte kein Problem sein, die meisten nehmen nur keinen Lesepuffer zum lesen.
(Faktor 10 - 20 langsamer)

schau mal hier, die Rohdaten zu lesen, hast Du ungefähr in 750 ms gemacht ( 100 MB)

http://delphi.pjh2.de/articles/files/files.php

Zitat:

Und ich dachte immer ASM sei so schnell.....

du hast den falschen Schluss gezogen ....
ASM ist genauso schnell wie Delphi. wenn es gut compiliert.
Die Fastcode Lösungen sind oft trickreiche Sachen, man arbeitet mit ASM aber noch mit anderen Ideen.
Sprungadressen auf Funktionen anhand der Übergabeparameter berechnen usw.
Musst Du dir mal ansehen, reines Assember ist auch nicht schneller.

Das langsame sind die Strings ... einmal Setstring aus dem String heraus in einen Tempbuffer, .. und dann noch einmal!! in TStrings hinein.

schau Dir mal die procedure TStrings.SetTextStr(const Value: string); in SysUtils an ...

die fast function StrPosJOH wäre wahrscheinlich noch interessant, um die Position zu finden. dürfte Schneller sein, als die Schleife:

http://coding.derkeiler.com/Archive/.../msg00102.html

und dann in Assembler, aber da ist wohl ein Uppercase drin ....

http://coding.derkeiler.com/Archive/.../msg00057.html

hab ich aber noch nicht eingebaut

[alzaimar]

Die JOH_Pos-funktionen sind bei Delimitern <= 4 Zeichen schneller als das Quicksearch, bei einem Zeichen ist die JOH-charPos Funktion noch schneller. Viel schneller.

Und ich denke, die TStringDivider-Version mit 'copy-string-on-demand' sollte dann auch dem strengsten Kritiker gefallen. Hast schon Recht...

[stoxx]

also mit der Lösung im Anhang bin ich auf 93,1 MB pro Sekunden.
Im Vergleich zur ersten Lösung eine Steigerung um 300 Prozent.


Using TStringExploder in TStringList
100 chars per line; Itemlänge: 10; 1000000 lines in 1047 tics, 955110 lines per sec, 93,3 mb/s (del = ";")
10000 chars per line; Itemlänge: 100; 50000 lines in 1844 tics, 27115 lines per sec, 264,8 mb/s (del = ";")
1000000 chars per line; Itemlänge: 1000; 500 lines in 1610 tics, 311 lines per sec, 303,3 mb/s (del = ";")
100 chars per line; Itemlänge: 5; 1000000 lines in 1422 tics, 703235 lines per sec, 68,7 mb/s (del = ";")
1000 chars per line; Itemlänge: 5; 500000 lines in 6796 tics, 73573 lines per sec, 71,8 mb/s (del = ";")




Noch schneller wird es, wenn man nur die Hälfte der Columns benötigt !!

zum Testen.

For ColIDX := 0 To (d.ColCount Div 2) Do begin
// s.Add(d.Columns[ColIDX]); // Bremse ....
s1 := d.Columns[ColIDX];

end;


aber bitte vorsichtig, die kapslung stürzt noch ab bei sehr großen Strings, wahscheinlich wegen dem Arry, ist alles ungetestet. hatte keine Zeit mehr.
am besten die Funktionalitäts-logik irgendwie in die eigene Klasse die es benötigt, integrieren ...
unterstützt auch im Moment nur die Suche nach einem Zeichen ...

[stoxx]

Zitat:

Die JOH_Pos-funktionen sind bei Delimitern <= 4 Zeichen schneller als das Quicksearch

vielleicht bringt ja die JOH Pos auf PChar basierend noch mehr Performance
http://fastcode.sourceforge.net/Fast...trLenBV132.zip

Zitat:

Und ich dachte immer ASM sei so schnell.....

und hier sieht man mal, dass die Suche nach einem Zeichen (Null) von JOH in Pascal wesentlich schneller sein können, als eine ASM Routine ....


http://fastcode.sourceforge.net/Fast...nchmark132.xls

[stoxx]

hmmm .. weiß jemand was der da tut??

Könnte man die Operationen auch so gestalten, dass es auch mit einem beliebigen Zeichen funktioniert?
Oder ist diese Arithmetik nur für Null einsetzbar?

Delphi-Quellcode:

function StrLen_JOH_PAS_3_a(const Str: PChar): Cardinal;
var
  P, PStr: PChar;
  I, J: Integer;
begin
  if Str^ = #0 then
    begin
      Result := 0; Exit;
    end;
  if Str[1] = #0 then
    begin
      Result := 1; Exit;
    end;
  if Str[2] = #0 then
    begin
      Result := 2; Exit;
    end;
  if Str[3] = #0 then
    begin
      Result := 3; Exit;
    end;
 P := Pointer(Str);
 PStr := P;
 P := Pointer(Integer(P) and -4);
 repeat
   Inc(P, 4);
   I := PInteger(P)^;
   J := I - $01010101;
   I := not(I);
   I := I and J;
 until (I and $80808080) <> 0;
 Result := P - PStr;
 if I and $80 = 0 then
   if I and $8000 <> 0 then
     Inc(Result)
   else
     if I and $800000 <> 0 then
       Inc(Result, 2)
     else
       Inc(Result, 3)
end;

ist vom Benchmark doppelt so schnell, wie eine einfache schleife und jedes Byte anzusehen ..

Delphi-Quellcode:

function StrLen_JOH_PAS_1_a(const Str: PChar): Cardinal;
var
  P : PChar;
begin
  P := Str;
  while P^ <> #0 do
    Inc(P);
  Result := P - Str;
end;

[alzaimar]

Zitat von stoxx:

also mit der Lösung im Anhang bin ich auf 93,1 MB pro Sekunden.

Aber du liest die Strings nicht aus, oder? Du rufst doch nur 'explode' auf, gell?

[alzaimar]

Zitat von stoxx:

also mit der Lösung im Anhang bin ich auf 93,1 MB pro Sekunden.

Aber du liest die Strings nicht aus, oder? Du rufst doch nur 'explode' auf, gell?