Schnellster Stringmatching-Algorithmus in ASM übersetzen

[sirius]

Daran habe ich auch gedacht
Ich schau nochmal.

[Tyrael Y.]

Was ist wenn mein SubString nur aus einem Zeichen besteht?

  pPtr := @sSubStr[2];
Edit:

Zitat:

Ach, er klappt sowieso nur für Suchstrings mit mehr als einem Zeichen...

Ich sollte erst den ganzen Beitrag lesen bevor ich den Code kritisiere bzw. wie wäre es wenn du trotzdem den Fall von einem Zeichen abfängst zB mittels Assertion ?

[sirius]

Also die Schleife war schon richtigrum (das hatte ich vorher schon erkannt), deswegen zähle ich ja ebx zurück und ecx hoch.
Der Fehler war am Ende von comparemem (die 4 POPs waren etwas durcheinander geraten)

So, jetzt habe ich es mal in dein Programm eingebaut und mal mit dem Code von Delphi verglichen. Bringt nix.

[DerDan]

Hallo,

Zitat von Tyrael Y.:

Iwie wäre es wenn du trotzdem den Fall von einem Zeichen abfängst zB mittels Assertion ?

oder mit einer korrekten Funktion ???


mfg

DerDan

[sirius]

Was habt ihr denn? Ein Zeichen klappt doch prima, oder

[shmia]

Also ich würde alle Index-Operationen durch Zeigeroperationen ersetzen und kein Assembler verwenden.
Das bringt allerdings nur dann etwas, wenn der Inde kontinuierlich ansteigt oder fällt.
Beispiel ("langsam"):

Delphi-Quellcode:

  For c := Low(Char) To High(Char) Do 
    Skip[c] := n + 1;

Und so mit Zeigeroperationen:

Delphi-Quellcode:

  pSkip := @Skip[Low(Char)];  // pSkip:PChar
  For c := Low(Char) To High(Char) Do 
  begin
    pSkip^ := n + 1;
    Inc(pSkip);
  end;

Der entstehende Code ist dann von der Geschwindigkeit so nahe an einer Assembler Implementierung, dass es sich nicht lohnt Assembler zu verwenden.

Ganz wichtig:
Man benötigt unbedingt ein Testbett, mit dem man min. 10 verschiedene Fälle automatisiert testen kann.
Im Prinzip ein Unit-Test.
Nur so kann man die Funktion Schritt für Schritt verbessern, ohne dass man ständig neue Bugs einbaut.

[sirius]

Ich habe die Erstellung der Sprungtabelle mal nach außen verlagert (außerhalb der Zeitmessung). Das bringt nix.

Edit:
Einen kleinen Punkt bringt es die Anzahl der Sprünge pro Schleife möglichst auf 1 zu minimieren:

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
  mov edx,[esp]     //Länge


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



  sub ebp,$41C    //ebp zeigt auf Sprungtabelle

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

 @while:



      cmp edx,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+$40C]   //length(ssubstr)-2
      mov edx,ecx
      and edx,3
      add esi,edi
      inc esi
      mov edi,[ebp+$424]
      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

    //Der Block wird hauptsächlich durchlaufen und verursacht die benötigte Zeit
   @endif:
    mov eax,edx //length(ssubstr) nach eax
    add eax,edi   //i dazuaddieren
   @endifEX:
    movzx eax, byte ptr [esi+eax] //test[i+length(ssubstr)+1]
    mov eax, [ebp+eax*4] //Wert aus Sprungtabelle
    add edi, eax      //..zu i dazuaddieren
    cmp edi, ecx      //mit k vergleichen
  jg @endwhile
    cmp [esi+edi],bl //Vergleich von text[i] mit c1
    jnz @endif

    mov eax,edx     //length(ssubstr) in eax
    add eax,edi       //i addieren
    cmp [esi+eax-1],bh         //Vergleich text[i+length(ssubstr)] mit cp
    jnz @endifEx
    jmp @while

 @endwhile:

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

Edit2: Immer noch kleine Veränderungen, aber der große Sprung wird es mit dem Algorithmus nicht mehr

[alzaimar]

shima, das stimmt nicht bzw. nur bedingt. Ich habe mich auch gewundert, aber ein Array-Zugriff ist wirklich sehr schnell:

Beweis: (Form, Memo, Button):

Delphi-Quellcode:

Procedure TForm1.btindexClick(Sender: TObject);
Var
  a: Array[0..1000000] Of Byte;
  t, r, i: Cardinal;
  p: ^byte;

Begin
  t := GetTickCount;
  For r := 1 To 1000 Do
    For i := 0 To High(a) Do
      a[i] := 1;
  Memo.Lines.add('Index : ' + IntToStr(GetTickCount - t));
  t := GetTickCount;
  For r := 1 To 1000 Do Begin
    p := @a;
    For i := 0 To High(a) Do Begin
      p^ := 1;
      inc(p);
    End
  End;
  Memo.Lines.add('Ptr : ' + IntToStr(GetTickCount - t));
End;

Ergibt bei mir

Zitat von Mein LCD:

Index : 1250
Ptr : 1985

Ich vermute, wenn sich der Assembler-Guru Sirius nochmal reinkniet, dann bekommt er das hin. Seine Assembler-Routine scheint wirklich verdammt schnell zu sein. Wenn sie denn funktioniert...

Wie gesagt, bei kleinen Strings klappt das (es ist vermutlich nur ne Kleinigkeit...)

Zitat von Tyrael Y.:

Zitat von sirius:

Was habt ihr denn? Ein Zeichen klappt doch prima, oder

Naja laut dem Code den ich zitiert habe kann es ja nicht laufen, da auf den zweiten Char im Substring zugegriffen wird.

Selbst wenn es funktionieren würde: Bei einem Zeichen ist die Sprungtabelle für das Zeichen = 1 und dann wird das zu langsam.

Im Anhang mal eine Unit die den FastCode-Gewinner, mein QSSearch (na ja, von Daniel Sunday und einer Prise Alz) und dem naiven Durchraser bei einbuchstabigem Suchstring. Hups. auch das kann man optimieren, das ist mir aber zu blöd.

[Tyrael Y.]

Zitat von sirius:

Was habt ihr denn? Ein Zeichen klappt doch prima, oder

Naja laut dem Code den ich zitiert habe kann es ja nicht laufen, da auf den zweiten Char im Substring zugegriffen wird.

[SirThornberry]

Zitat von Tyrael Y.:

Zitat von sirius:

Was habt ihr denn? Ein Zeichen klappt doch prima, oder

Naja laut dem Code den ich zitiert habe kann es ja nicht laufen, da auf den zweiten Char im Substring zugegriffen wird.

Nicht ganz. Es wird nur die Adresse gesucht. Es wird also einfach zur Basisadresse der Variablen der Index * sizeof(element) dazu addiert. Und diese Variable wird dann glaub ich gar nicht verwendet wenn der String kleiner 1 oder gleich 1 ist.