Schnellster Stringmatching-Algorithmus in ASM übersetzen

[alzaimar]

Erstmal Danke an Sirius für die Mühe. Wenn ich mir die Testunit von Sirius bringt Assembler hier wohl wirklich nichts. Schade eigentlich. Aber wenigstens weiss man einmal mehr, das Delphi ziemlich guten Assemblercode produziert.

Später poste ich mal einen Vergleich zwischen FastPos und Delphi-Pos.

[sirius]

Ich konnte zwar an einigen Stellen (denke ich) etwas herausholen, aber das bringt im Endeffekt nix, das das Nadelöhr allein in dem Teil steckt:

Delphi-Quellcode:

   While i < k Do Begin // Bei PChar: i <= k 
    If (c1 = sText[i]) And (cp = sText[i + n1]) Then ...
    inc(i, Skip[sText[i + n]]); 
  End;

Und da gibts nicht viel zu optimieren, ausser dass man alle Variablen in Registern vorhält und die Anzahl der Sprünge minimiert. Letzteres ist kaum möglich (es gibt kaum Sprünge zu eliminieren). Es war aber das Einzige was einen winzigen Zeitsprung gebracht hat. Und die RAM-Zugriffszeiten sind mittlerweile so gering, dass man mit Registervariablen fast nix mehr rausholen kann.

Edit: Was ich noch sagen wollte: Schöner Algorithmus . Die Sprungtabelle und das Vergleichen des ersten Zeichens sind der Kern. Der Rest ist Zugabe.

[alzaimar]

Zitat von sirius:

Und da gibts nicht viel zu optimieren, ausser dass man alle Variablen in Registern vorhält

Das das nichts bringt, hast Du gut erklärt.

Zitat von sirius:

Edit: Die Sprungtabelle und das Vergleichen des ersten Zeichens sind der Kern. Der Rest ist Zugabe.

Der Vergleich des letzten Zeichen bringt auch nochmal viel, da dadurch der Aufruf von CompareMem nochmals reduziert wird.

[Amateurprofi]

Zitat von alzaimar:

Zitat von sirius:

Und da gibts nicht viel zu optimieren, ausser dass man alle Variablen in Registern vorhält

Das das nichts bringt, hast Du gut erklärt.

Zitat von sirius:

Edit: Die Sprungtabelle und das Vergleichen des ersten Zeichens sind der Kern. Der Rest ist Zugabe.

Der Vergleich des letzten Zeichen bringt auch nochmal viel, da dadurch der Aufruf von CompareMem nochmals reduziert wird.

@alzaimar, sirius:

Ich denke, daß es da sehr wohl einiges zu optimieren gibt.
Deshalb habe ich mir die Mühe gemacht eine etwas schnellere ASM-Routine zu schreiben und die Performance zu testen.
Diese Routine ist ein "PosEx", man kann also auch vorgeben ab welcher Position im String gesucht werden soll.

Für die Performance-Messung wurde der String "SearchIn" auf eine Länge von 1Mio Zeichen gestellt, komplett mit dem Zeichen "a" gefüllt und der String "SearchFor" an das Ende von "SearchIn" gestellt.
Dann wurde für alzaimars, siriuss, meine und die system.pos Routine die Zeit (CPU-Ticks) gemessen.

Und das sind die Ergebnisse, die meines Erachtens für sich sprechen

Code:

SearchFor          b         ab        aba       abba      abbba    abbbba     abbbbba
alzaimar     3921148    4668872  145252980  145397708  145417164   87380040   87976592
sirius       3887104    4618452  145108488  145395176  145382700   87022640   86831224
amateurprofi 2845308    4612200    8583452    9482744    9258968    9259532   74201884
system-Pos   4172836  128869200  128814300  129164580  129334480  129133380  128982992

Die drastisch bessere Performance bei den Fällen, in denen SearchFor 3,4,5 oder 6 Zeichen lang ist, ergibt sich daraus, daß
meine Routine für die Fälle Length(SearchFor)<7 jeweils eine eigene Suchroutine benutzt, die nicht das bummelige CompareMem
verwendet.
Ich bin überzeugt, daß meine Routine; die nur ein erster Entwurf ist, durchaus noch einiges Optimierungs-Potenzial beinhaltet und werde mir demnächst noch ein paar Gedanken dazu machen.

Ein kleines simples Testprogramm ist im Anhang, die Beschreibung steht in ReadMe.txt

Und hier die Routine QPosEx

Delphi-Quellcode:

// Version von amateurprofi
FUNCTION QPosEx(SearchFor,SearchIn:String; Start:integer):integer;
asm
               pushad                     // Alle Register auf Stack legen
               sub   esp,$400             // Platz für Skiptabelle schaffen
               // Auf dem Stack liegen folgende Daten
               // ESP            : Skiptabelle
               // ESP+$400..$410 : EDI, ESI, EBP, ESP, EBX
               // ESP+$414       : EDX Adresse SearchIn
               // ESP+$418       : ECX Start
               // ESP+$41C       : EAX Adresse SearchFor
               // ESP+$420       : EBP
               // ESP+$424       : Returnadresse

               // Prüfen, ob SearchFor oder SearchIn leer ist, oder Start negativ ist
               test  eax,eax
               je    @Fail                // SearchFor ist leer
               test  edx,edx
               je    @Fail                // Searchin ist leer
               mov   ebx,[eax-4]          // Länge SearchFor
               test  ebx,ebx
               je    @Fail                // SearchFor ist leer
               test  ecx,ecx
               js    @Fail                // Start ist negative

               // Erste und letzte mögliche Fundstelle in ESI bzw. EBP
               je    @1
               sub   ecx,1                // =Start 0-basierend
@1:            lea   esi,[edx+ecx]        // Ab hier soll gesucht werden
               add   edx,[edx-4]
               mov   ebp,edx
               sub   ebp,ebx              // Bis hier soll gesucht werden

               // Prüfen, ob Erste mögliche Fundstelle hinter letzter liegt
               cmp   esi,ebp
               ja    @Fail

               // Prüfen, ob SearchFor nur 1 Zeichen ist
               // Dann ist keine SkipTabelle erforderlich
               cmp   ebx,1
               je    @Search1


               // Skiptabelle erstellen
               // 1) for i:=0 to 255 do Skip[i]:=n+1
               mov   edi,esp
               mov   ecx,$100
               mov   eax,ebx
               add   eax,1                // Length(Searchfor)+1
               rep   stosd
               // 2) For i:=0 To n-1 Do Skip[SearchFor[i]]:=n-i
               mov   edi,[esp+$41C]       // Adresse SearchFor
               mov   eax,ebx              // Length(Searchfor)
@FillSkip:     movzx edx,[edi+ecx]        // SearchFor[i]
               mov   [esp+edx*4],eax      // Skip[SearchFor[i]]:=n-i
               add   ecx,1
               sub   eax,1
               jne   @FillSkip

               // Erstes und Letztes Zeichen von SearchFor in AL/AH
               mov   al,[edi]             // Erstes Zeichen SearchFor
               mov   ah,[edi+ebx-1]       // Letzes Zeichen SearchFor

               // Prüfen, ob Length(SearchFor) > 6 ist
               cmp   ebx,6
               ja    @SearchX
               jmp   @Vector.Pointer[ebx*4-8]
@Vector:       dd    @Search2
               dd    @Search3
               dd    @Search4
               dd    @Search4  // Länge=5
               dd    @Search6

// Länge Searchfor > 6
@SearchX:      add   edi,1                // Auf zweites Zeichen von SearchFor
               mov   [esp+$41C],edi       // Merken für CompareMem
               jmp   @Search
// Länge SearchFor > 6
@SkipX:        mov   esi,edx              // Aufruf ex CompareMem
@Skip:         movzx edx,[esi+ebx]
               add   esi,[esp+edx*4]
               cmp   esi,ebp
               ja   @Fail
@Search:       cmp   [esi],al
               jne   @Skip
               cmp   [esi+ebx-1],ah
               jne   @Skip
               // Zweites bis vorletzten Zeichen von SearchFor prüfen
               mov   edx,esi              // ESI retten
               mov   edi,[esp+$41C]       // Zeiger zweites Zeichen von SearchFor
               add   esi,1                // Zeiger Text auf nächstes Zeichen
               mov   ecx,ebx              // Length(SearchFor)
               sub   ecx,2                // -2 (Erstes und letztes Zeichen)
               shr   ecx,2                // =Anzahl DWords
               repe  cmpsd                // DWords vergleichen
               jne   @SkipX               // Nicht gleich
               mov   ecx,ebx              // Length(SearchFor)
               sub   ecx,2                // -2 (Erstes und letztes Zeichen)
               and   ecx,3                // =Anzahl restliche Bytes
               repe  cmpsb                // Bytes vergleichen
               jne   @SkipX               // Nicht gleich
               mov   esi,edx              // Fundstelle
               jmp   @Found

// Länge SearchFor=1
@Search1:      mov   ecx,ebp              // Letzte mögliche Fundstelle
               sub   ecx,esi              // - Erste mögliche Fundstelle
               add   ecx,1                // = Anzahl zu prüfende Zeichen
               neg   ecx
               sub   esi,ecx
               mov   al,[eax]             // zu suchendes Zeichen
@Loop:         cmp   al,[esi+ecx]
               je    @Found1
               add   ecx,1
               jne   @Loop
               jmp   @Fail
@Found1:       lea   esi,[esi+ecx]          // ESI auf Fundstelle
               jmp   @Found

// Länge SearchFor=2
@Skip2:        movzx edx,[esi+ebx]
               add   esi,[esp+edx*4]
               cmp   esi,ebp
               ja   @Fail
@Search2:      cmp   [esi],al
               jne   @Skip2
               cmp   [esi+ebx-1],ah
               jne   @Skip2
               jmp   @Found

// Länge SearchFor=3
@Skip3:        movzx edx,[esi+ebx]
               add   esi,[esp+edx*4]
               cmp   esi,ebp
               ja   @Fail
@Search3:      cmp   [esi],al
               jne   @Skip3
               cmp   [esi+ebx-1],ah
               jne   @Skip3
               mov   dx,[edi]
               cmp   dx,[esi]
               jne   @Skip3
               jmp   @Found

// Länge SearchFor=4 oder 5
@Skip4:        movzx edx,[esi+ebx]
               add   esi,[esp+edx*4]
               cmp   esi,ebp
               ja   @Fail
@Search4:      cmp   [esi],al
               jne   @Skip4
               cmp   [esi+ebx-1],ah
               jne   @Skip4
               mov   edx,[edi]
               cmp   edx,[esi]
               jne   @Skip4
               jmp   @Found

// Länge SearchFor=6
@Skip6:        movzx edx,[esi+ebx]
               add   esi,[esp+edx*4]
               cmp   esi,ebp
               ja   @Fail
@Search6:      cmp   [esi],al
               jne   @Skip6
               cmp   [esi+ebx-1],ah
               jne   @Skip6
               mov   edx,[edi+1]
               cmp   edx,[esi+1]
               jne   @Skip6
               jmp   @Found

@Found:        // Gefunden, Index berechnen
               sub   esi,[esp+$414]
               add   esi,1
               jmp   @SetRes

@Fail:         // Nicht gefunden, Result=0
               xor   esi,esi

@SetRes:       // Result speichern
               mov   [esp+$41C],esi

               // Skiptabelle vom Stack nehmen
               add   esp,$400

               // Register wieder herstellen, Result in EAX
               popad
end;

[alzaimar]

Meine Tests ergeben ernüchternde 1-7% Verbesserung. Ich verwende zufällige Strings, wo der Vergleich mit Comparemem relativ selten vorkommt (Die Grundidee der Raita-Optimierung).

Für einbuchstabige Suchtexte gibt es zudem wesentlich schnellere Verfahren (FastCode-Challenge, CharPos), diese sind ca. 2-5x schneller als Deine Variante. Die Sprungtabelle ist hier der Pferdefuss. Zudem wird immer die überflüssige Logik beim Vergleich aufgerufen.

Bei Suchtexten mit 2 und 3 Buchstaben ist die FCC-Pos-Variante schneller.

Bei langen Suchtexten (bei denen also die Raita-Optimierung häufig greift), nehmen sich Assembler und Delphi-Variante nicht mehr viel.

Wenn man ein generelles schnelles PosEx möchte, sollte man diese drei Routinen vereinen. Bei kurzen Texten (bis ca. 1000) ruft man die FCC-Pos Variante auf, sucht man nach einem Zeichen die FCC-Charpos Variante und sonst Quicksearch. Welche Variante (Assembler oder Delphi) ist fast egal. Da die Asm-Variante jedoch bei einer Suchtextlänge von 4 optimiert ist, sollte man der Assemblervariante den Vorzug geben.

Ich habe mal eine FastPos-Unit angehängt, allerdings war ich jetzt zu faul, die PosEx-Varianten von der FCC-Homepage einzubauen.

[sirius]

Zitat:

Die drastisch bessere Performance bei den Fällen, in denen SearchFor 3,4,5 oder 6 Zeichen lang ist, ergibt sich daraus, daß
meine Routine für die Fälle Length(SearchFor)<7 jeweils eine eigene Suchroutine benutzt, die nicht das bummelige CompareMem
verwendet.

Das war ja nicht die Aufgabe
Ansonsten bringt dein Algortihmus nix. Das kann man immernoch ohne Assembler machen. In der Testroutine von oben sind alle drei (fast) identisch.

[Amateurprofi]

Zitat von alzaimar:

Meine Tests ergeben ernüchternde 1-7% Verbesserung. Ich verwende zufällige Strings, wo der Vergleich mit Comparemem relativ selten vorkommt (Die Grundidee der Raita-Optimierung).

Ich habe mal eine FastPos-Unit angehängt, allerdings war ich jetzt zu faul, die PosEx-Varianten von der FCC-Homepage einzubauen.

Ist denn bei den "zufälligen" Strings sichergestellt, daß der Text erst am Ende des Strings (oder auch gar nicht) gefunden werden kann ?
Meines Erachtens macht ein Performancetest (in diesem Fall) nur dann Sinn, wenn der String komplett durchsucht werden muß.
Wenn die Fundstelle irgendwo am Anfang liegt, wird eigentlich nur der durch die Erstellung der Skiptabelle entstehende Overhead gemessen.

Im Übrigen halte ich 1-7 % Verbesserung für ganz ordentlich. (Für 7% Gehaltserhöhung streiken die Leute).

Und : kannst du bitte die FastPos-Unit mal als ganz normalen Text-File anhängen. (Egal wie ich sie öffne sehe ich nur ein wirres Durcheinander). Danke.

[Amateurprofi]

Zitat von sirius:

Zitat:

Die drastisch bessere Performance bei den Fällen, in denen SearchFor 3,4,5 oder 6 Zeichen lang ist, ergibt sich daraus, daß
meine Routine für die Fälle Length(SearchFor)<7 jeweils eine eigene Suchroutine benutzt, die nicht das bummelige CompareMem
verwendet.

Das war ja nicht die Aufgabe :zwinker:
Ansonsten bringt dein Algortihmus nix. Das kann man immernoch ohne Assembler machen. In der Testroutine von oben sind alle drei (fast) identisch.

Ich nehme mal die Zahlen aus der letzten Spalte
alzaimars (pascal) 87976592 Ticks
deine Version (asm) 86831224 Ticks. Verbesserung vs. alzaimars = 1.3 %
meine Version (asm) 74201884 Ticks. Verbesserung vs. deine = 14.5 %

Das du deine 1.3 % als nix bezeichnest, ist ja ok (auch wenn das nicht meine Meinung ist, denn jede Verbesserung hat ihren Wert).
Jedoch denke ich, daß die von mir erzielten 14.5 % (das ist mehr als das 10-fache deiner Optimierung) schon ganz ordentlich sind.

[sirius]

Keine Ahnung, wo du deine Zahlen hernimmst:

Code:

10 Mio Zeichen (zufällige Klein-, Großbuchstaben und Ziffern); 100 Durchläufe

SubStr-Position             Ums.     Ticks   "Takte"

nicht enthalten:            Sirius   1641    5904826
nicht enthalten:            Alzaim   1672    5983740
nicht enthalten:            AmProf   1578    5624764

am Ende:                    Sirius   1516    5419565
am Ende:                    Alzaim   1531    5478115
am Ende:                    AmProf   1531    5523135

04 Zeichen kurz vorm Ende:  Sirius   2000    7174492
04 Zeichen kurz vorm Ende:  Alzaim   2063    7363324
04 Zeichen kurz vorm Ende:  AmProf   1907    6784691

10 Zeichen kurz vorm Ende:  Sirius   1656    5965412
10 Zeichen kurz vorm Ende:  Alzaim   1703    6070397
10 Zeichen kurz vorm Ende:  AmProf   1594    5729845

30 Zeichen kurz vorm Ende:  Sirius   1500    5365152
30 Zeichen kurz vorm Ende:  Alzaim   1547    5497721
30 Zeichen kurz vorm Ende:  AmProf   1469    5270731

(Bei "nicht enthalten" und "am Ende" ist das Erste Zeichen des subst. nicht im eigentlichen SuchText enthalten)

Hier ist dein Algorithmus auch kaum bei kurzen Suchstrings besser. Aber wie gesagt, es ging ja nicht um kurze SuchStrings und auch nicht darum, alle Algortihmen in einer Assemblerroutine unterzubringen. Das du jetzt vielleicht noch 1% herausgeholt hast, mag ja sein. Wobei das 1% bezogen ist auf meinen bzw. Alzis Umsetzung. Beziehe die Differenz mal auf das ursprüngliche Delphi-Pos!
In meinem Beitrag #32 beziehe ich mich eben darauf, dass bis auf wenige Takte (was ich nicht explizit schrieb), aus diesem Algorithmus nichts mehr rauszuholen ist. Außer dass man ein paar Sprünge entfernt und dies und das (ich war auch noch nicht vollständig am Ende), wobei ich die Suche dann abgebrochen habe...(meine Pausen sind ja auch nicht ewig lang) denn eine Verbesserung um den Faktor 2 bis Inf (was meiner Meinung nach alzis Erwartungen entsprach) war nicht mehr möglich zu erreichen, nicht mal annähernd.

Aber du kannst ja gerne deine Routine weiter verfeinern und hier zur Verfügung stellen

[jbg]

Ups. habe glatt die 2. und 3. Seite übersehen.