Schnellster Stringmatching-Algorithmus in ASM übersetzen

[alzaimar]

Gute Idee. Nur bei einem 1GB-String wird das mit dem Speicher dann ein wenig knapp...

[sirius]

Zitat von alzaimar:

@sirius: Mit direkten PChar in ASM zu arbeiten, würde nichts bringen? Wenn ich das in Delphi mache (in PChar umwandeln) kann ich mir die blöde Abfrage am Ende zwar sparen, dafür wird der Code aber um ein Vielfaches langsamer.

Kann man da gar nichts machen?

Und was meinst du mit 'Sprungtabelle hart codieren'?

Wo habe ich was von PChar geschrieben?

Ja, das hart codieren habe ich auch wieder verworfen, man könnte quasi das Array konstant mit 0 füllen und bei inc abfragen, das Array ander Stelle 0 ist. Ist aber totaler Blödsinn.

[alzaimar]

Zitat von sirius:

Wo habe ich was von PChar geschrieben?

War darauf bezogen.

Zitat von sirius:

Viel Potenzial sehe ich auf Anhieb nicht.

War so'ne Idee von mir. Schließlich arbeiten die Performancegeier alle mit PChar, weil sie meinen, das das dann schneller wird.

[sirius]

Mir gefällt String viel besser (weil da steht die Länge auch gleich "im" String)

Deine Optimierung...liegt die in dem c1 und dem cp?
Ab welcher Länge von substr siehst du da Vorteile?

[Progman]

Hat sich schonmal jemand die Function Pos (und ähnliche) im Originalcode angeschaut?
Die sind in Assembler. Also kann man da nichts mehr beschleunigen.

[xaromz]

Hallo,

Zitat von Progman:

Hat sich schonmal jemand die Function Pos (und ähnliche) im Originalcode angeschaut?
Die sind in Assembler. Also kann man da nichts mehr beschleunigen.

also...
erstens ist die Pos-Funktion von Delphi ziemlich schlecht programmiert (oder haben die das inzwischen optimiert?), und zweitens kann ich Dir einen Assembler-Code schreiben, der für diese Funktion drei Tage braucht . alzaimar's Algorithmus ist sicher auch ohne Assembler wesentlich schneller (hat er ja auch geschrieben).

Gruß
xaromz

[Luckie]

Zitat von Progman:

Die sind in Assembler. Also kann man da nichts mehr beschleunigen.

Es ist erwiesen, dass die original Version von Pos langsam ist. Und nur weil sie in ASM direkt codiert wurde heißt das nicht, dass man da nichst mehr optimieren und / oder verbessern könnte.

[alzaimar]

@Sirius: Die Optimierung von Raita (und von mir) liegt darin, das man nicht jedesmal 'CompareMem' aufruft, sondern eben nur dann, wenn die ersten und letzten Zeichen übereinstimmen. Es gibt sogar noch eine Optimierung, die das letzte, das erste und das mittlere Zeichen vergleichen, und erst dann CompareMem aufrufen. Da hatte ich bei meinem Szenario (Tags in XML-Dateien finden) keinen Geschwindigkeitsvorteil.

Wenn ich das weglasse, also direkt CompareMem aufrufe, dauert das bei meinem Testprogramm 3x so lange. Aber ich gebe zu, der Suchstring ist 8 Zeichen lang.

Angeblich ist Boyer-Moore ja noch schneller, ich konnte das aber nicht verifizieren. Im Gegenteil, er ist aufgrund des Overheads in der Schleife doch langsamer (jedenfalls in Delphi).

Ich habe eben mal den Gewinner der FastCode-Challenge (Pos) eingebaut und selbst der Code ist 1,5x langsamer.

Bevor das hier ausartet, sollte ich gleich mal Folgendes sagen:

Der QuickSearch-Algorithmus spielt seine Stärken umso stärker aus, je länger der Suchtext ist. Weiterhin sollte der zu suchende Text nicht zu kurz sein, da der Overhead im Berechnen der Sprungtabelle sonst den Performancegewinn zunichte macht.

QS eignet sich also für lange Texte und Suchstrings mit mehr als 4 Zeichen. Wenn man QS also in seinem Code verwenden möchte, dann sollte man für kurze Strings (PI x Daumen: 1000 Zeichen) und Suchstrings mit weniger als 4 Zeichen zu dem FastCode-Pos greifen, ansonsten zum QS.

Übrigens verwendet man Stringmatching-Algorithmen bei der Suche nach Gensequenzen. Ich hatte das Problem, in mehreren MB großen XML-Strings nach bestimmten Tags zu suchen. Daher die Optimierung "erst erstes und letztes Zeichen vergleichen", denn das ist '<' und '>' und das kommt im XML ja relativ selten vor.

So wie ich das sehe, wird man nur marginal etwas herausholen können. Ich denke, ich poste heute abend mal ein verbessertes Pos, das den FCC-Gewinner und QS vereint.

@ProgMan: Nicht die Sprache ist entscheidend, sondern der Algorithmus. Selbst die POS-Funktion der RTL ist lahm, gegenüber dem Gewinner der Fastcode-Challenge (Faktor 3 ungefähr).

[sirius]

Delphi-Quellcode:

function QSString(const ssubstr,text:string):Integer;stdcall;
//Delphi fügt automatisch push ebp; mov ebp,esp; ein
asm
  push ebx  //register retten
  push edi
  push esi

  mov eax,[ebp+8] //ssubbstr
  mov edx,[eax-4] //length(ssubstr)
  mov ebx,edx     //ebx=length(ssubstr) (für später)
  sub edx,2       //edx=length(ssubstr)-2
  push edx      //n2 = [ebp - 16]  =length(ssubstr)-2
  movzx edx, byte ptr [eax]
  push edx      //c1 = [ebp - 20]  =ssubstr[1]
  movzx edx, byte ptr [eax+ebx-1]
  push edx      //cp= [ebp -  24]  =ssubstr[ length(ssubstr) ]


  mov cx,$0100  //array mit ebx=length(ssubstr)+1 füllen
  inc ebx
 @fillarray:
    push ebx
    dec cx
  jnz @fillarray
  dec ebx

  // For i := 0 To n-1 Do Skip[sSubStr[i]] := n - i;
  xor ecx,ecx
  mov edi,[ebp+8] //ssubstr
  push ebx        //length(ssubstr) auf [esp] legen/retten
  mov esi,ebp
  sub esi,$41C      //Zeiger auf Sprungtabelle
 @fillotherskip:  //for i=ecx :=0 to ebx
    movzx eax, byte ptr [edi+ecx] //ssubstr[ecx+1] in eax
    mov [esi+eax*4],ebx  //[sprungtabelle+xxx] := length(ssubstr)-i
    inc ecx
    dec ebx
  jnz @fillotherskip


  mov esi,[ebp+12]   //Zeiger auf text

  mov ecx,[esi-4]    //length(text) in ecx
  sub ecx,[esp]      //ecx ist jetzt k (length(ssubstr) abgezogen)
  jle @endwhile      //wenn k<=0 Schleife überspringen

  xor edi,edi       //Zählvariable
  mov bl,[ebp-20]   //c1 und
  mov bh,[ebp-24]   //cp
  lea edx,[ebp-$41C]  //Zeiger auf Sprungtabelle


  //in Schleife gilt:
  //edi ist Zähler i
  //esi ist Zeiger auf Text
  //ebx ist erster(bl) und letzter(bh) Char von substr
  //[esp] ist n (Länge von substr)
  //ecx ist k (Abbruchbedingung)
  //edx ist Zeiger auf Sprungtabelle

 @while:

    cmp [esi+edi],bl         //Vergleich text[i] mit c1
    jnz @endif        //wenn ungleich --> springen
    mov eax,[esp]     //length(ssubstr) in eax
    add eax,edi       //i addieren
    cmp [esi+eax-1],bh         //Vergleich text[i+length(ssubstr)] mit cp
    jnz @endif

      cmp [esp],3      //length(ssubstr) mit 3 vergleichen
      jl @positiveExit //wenn kleiner 3 dann Ergebnis gefunden

      //comparemem
      push ecx //register retten
      push edx
      push edi
      push esi
      mov ecx,[ebp-16]   //length(ssubstr)-2
      mov edx,ecx
      and edx,3
      add esi,edi
      inc esi
      mov edi,[ebp+8]
      inc edi
      shr ecx,2
      xor eax,eax
      repe cmpsd         //Vergleich von DWORDs
      jne @endcmp
      mov ecx,edx
      repe cmpsb         //Vergleich der restlichen Bytes
      jne @endcmp
      inc eax
     @endcmp:
      pop esi
      pop edi
      pop edx          //register zurückholen
      pop ecx
      test al,al       //Ergebnis von comparemem auswerten
      jnz @positiveExit

   @endif:
    mov eax,[esp] //length(ssubstr) nach eax
    add eax,edi   //i dazuaddieren
    movzx eax, byte ptr [esi+eax] //test[i+length(ssubstr)+1]
    mov eax, [edx+eax*4] //Wert aus Sprungtabelle
    add edi, eax      //..zu i dazuaddieren
    cmp edi, ecx      //mit k vergleichen
  jle @while
 @endwhile:

  xor eax,eax    //result:=0
  jmp @exit
@positiveExit:
  mov eax,edi  //result:=i
  inc eax
@Exit:
  lea esp,ebp-12
  pop esi
  pop edi
  pop ebx
end;

Wenn ich mich nicht um +1 oder -1 mal verzählt habe, dürfte das stimmen.
Den letzten Absatz habe ich weggelassen.
Am meisten habe ich auf den Teil innerhalb der While-Schleife und darin außerhalb des IF-Blocks "optimiert".

Jetzt könnte man noch das cmp [esp],3 rausnehmen (weis nicht wieviel das bringt) und comparemem sozusagen als inline-Funktion reinschieben.
Aber erstmal testen, ob überhaupt alles richtig gemacht wird.

Edit: Fehler entfernt und Multiplikation entfernt

[alzaimar]

Klappt leider nicht.

Wenn der Suchstring im Text nicht vorhanden ist, geht das sauschnell. Nur leider findet er nix, auch wenn der Suchtext vorhanden ist, oder es kommt eine AV. Die AV kommt auch manchmal, wenn der Text nicht vorhanden ist.

Vermutlich irgendwas mit der Sprungtabelle.... Denk dran: Du kannst die Schleife nicht umdrehen:
For i := 1 To n Do Skip[sSubStr[i]] := n - i + 1; Wenn ein Buchstabe im Suchtext mehrmals vorkommt, dann wird das kleinste 'n-i+1' genommen. Daher muss(!) i hochgezählt werden ...