Schnellster Stringmatching-Algorithmus in ASM übersetzen

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