Schnellster Stringmatching-Algorithmus in ASM übersetzen

[alzaimar]

Hi ASM profis,

Ich habe hier einen wirklich schnellen Stringmatching-Algorithmus (also, sowas wie 'POS'), der aber wesentlich schneller als POS ist (2-20x).

Ich möchte gerne testen, ob dieser Algorithmus in Assembler noch (und vor allen Dingen, um wieviel) schneller ist. Er ist relativ simpel. Er basiert auf dem QuickSearch-Algorithmus von Daniel Sunday, mit einer Optimierung von mir. Diese wurde von Timo Raita (University of Turku) angeregt. Seine Arbeit behandelt diese Optimierung im Rahmen des Boyer-Moore Algorithmus.

Hier der Algorithmus. Er verwendet eine Sprungtabelle, die pro Substring nur einmal angelegt werden muss. Dieses Optimierungspotential interessiert mich aber jetzt nicht...

Hier der Algorithmus;

Delphi-Quellcode:

Function QSSearch(Const sSubStr, sText: String): Integer;
Var
  j, i, k, iTextLength: Cardinal;
  n, n1, n2: Cardinal;
  c1, cp: Char;
  Skip: Array[Char] Of Cardinal;
  c: Char;
  pPtr: Pointer;

Begin
  n := Length(sSubStr);
  c1 := sSubStr[1];
  cp := sSubStr[n];
  n1 := n - 1;
  n2 := n - 2;
  pPtr := @sSubStr[2];

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

  i := 1;
  j := 1;
  iTextLength := Length(sText);
  k := iTextLength - n + 1;
  While i < k Do Begin // Bei PChar: i <= k
    If (c1 = sText[i]) And (cp = sText[i + n1]) Then
      If (n < 3) Or CompareMem(@sText[i + 1], pPtr, n2) Then Begin
        Result := i;
        Exit;
      End;
    inc(i, Skip[sText[i + n]]); // Bei PChar und i=k ist sText[i+n] = #0, bei Strings erfolgt ein Überlauf
  End;

// Wegen o.g. Kommentare (PChar vs. String) Muss man hier eine extra Abfrage einbauen, ob
// der String nicht ganz am Ende auftaucht...
  Result := 0;
  If i = k Then
    If (c1 = sText[i]) And (cp = sText[i + n1]) Then
      If (n < 3) Or CompareMem(@sText[i + 1], pPtr, n2) Then
        Result := i;
End;

Im Prinzip geht es darum: Sei ABCDE (=T) mein Text, und ich suche nach 'CDE' (=S)
Ich fange an, und vergleiche die letze Stelle von S mit der 3.Stelle von T (weil len(S)=3). Wenn die beiden ungleich sin, und T[3] gar nicht in S vorkommt, kann ich gleich 3(!) Stellen nach rechts hüpfen. Kommt T[3] in S vor, dann entsprechend weniger. Das wird durch die 'Skip'-Tabelle festgelegt. Wenn die beiden Zeichen jedoch gleich sind, vergleiche ich T[1] mit S[1]. Stimmt das auch, vergleiche ich den Rest (das ist übrigens die Optimierung von Timo Raita: Kleine Ursache, riesen Wirkung)

Je länger der zu suchende Text, desto schneller (im Mittel) der Algorithmus.

Man kann natürlich noch die Startposition mit übergeben (das wäre dann die Zeile mit dem '***')

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

Also, hat Jemand Bock, das Teil in ASM zu übersetzen (oder sonstwie schneller zu machen)? Haben ja schließlich alle was davon.... :zwinker:

Bin mal gespannt....

[Edit]Fehlerhafte Version rausgeschmissen. Kommt davon, wenn man aus einer PChar in Strings umwandelt und ungenügend testet...[/edit]

[edit]
hier der Code von Sunday aus Charras & Lecroq

Code:

void preQsBc(char *x, int m, int qsBc[]) {
   int i;

   for (i = 0; i < ASIZE; ++i)
      qsBc[i] = m + 1;
   for (i = 0; i < m; ++i)
      qsBc[x[i]] = m - i;
}


void QS(char *x, int m, char *y, int n) {
   int j, qsBc[ASIZE];

   /* Preprocessing */
   preQsBc(x, m, qsBc);
 
   /* Searching */
   j = 0;
   while (j <= n - m) {
      if (memcmp(x, y + j, m) == 0)
         OUTPUT(j);
      j += qsBc[y[j + m]];               /* shift */
   }
}

[/edit]

[Amateurprofi]

@alzaimar:
Sieht ja sehr schön aus, kann aber meines Erachtens nicht funktionieren.

Nehmen wir mal an :
sText hat die Länge 100 und enthält nur 'A's
sSubStr ist 'BBBBB'

Vor der While-Schleife wird definiert:
n := 5; // Length(sSubStr)
j := 1;
iTextLength := 100; // Length(sText)
k := 95; // iTextLength - n;

Innerhalb der While-Schleife wird ausschließlich i verändert, also
haben wir nach Beendigung der While-Schleife folgenden Zustand
iTextLength = 100
k = 95
j = 1

Und nun kommt der Abschluß der Routine

Delphi-Quellcode:

  If j <= iTextLength + 1 Then
    Result := k + 1
  Else
    Result := 0;

j wird jetzt sicherlich <= iTextLength + 1 sein, also wird Result = k + 1 gesetzt,
und die Funktion wird als Fundstelle 96 ausgeben.

[alzaimar]

Au Backe, falsche Version... Na ja. Hab oben die Richtigere reingestellt.

[SirThornberry]

in asm übersetzen ist einfach. Schau dir einfach das CPU-Fenster an in Delphi oder nimm einen Disassembler.

Delphi-Quellcode:

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

Und anstelle des Aufrufs von comparemem könnte man den Code vielleicht direkt dort plazieren um zu vermeiden das erst auf den Stack gepackt wird und später wieder davon runter genommen wird.

das nächste ist folgendes

Delphi-Quellcode:

If j <= iTextLength + 1 Then 
  Result := k + 1 
Else 
  Result := 0;

Die Prüfung ist falsch. Wie du bereits mitbekommen hast funktioniert die Funktion nicht wenn n = iTextLength.

Und wie ich grad noch mitbekommen hab. Wenn n > iTextLength kommen völlig falsche Ergebnisse raus (auf Grund eines Überlaufes)

Bevor man also die Geschwindigkeit der Funktion optimiert sollte man solche Fehler unbedingt beseitigen. Solange solche Fehler drin sind ist ein Geschwindigkeitsvorteil gegenüber einer funktionierenden Funktion uninteressant. (denn was bringt mir eine schnelle nicht funktionierende Funktion?)

[Edit]
ok, da war wohl noch eine falsche Version hochgeladen
[/Edit]

[alzaimar]

Hi Sir Thornberry,

In ASM übersetzen UND/ODER schneller machen, darum geht es.

Das CompareMem wird i.a. relativ selten aufgerufen, hier steckt also kaum Potential. Ich hatte eine PChar-Variante, aber die ist einfach zu langsam.

[SirThornberry]

kaum potenzial ist aber auch potenzial :mrgreen: Wenn du das ganze fixer haben willst und an mehreren Stellen auf minimale Geschwindigkeitsgewinne verzichtest kommt am ende auch kein großer Geschwingigkeitsvorteil dabei heraus.

[sirius]

Viel Potenzial sehe ich auf Anhieb nicht. Man könnte die Sprungtabelle schon mal hard codieren (aber sowas hast du sicher eh schon vor).
Evtl. kann man die Register effektiver nutzen. Ansonsten ist Delphi in der Optimierung schon nicht schlecht.
Und bei Comparemem ... der überprüft erst in 4 Byte-Schritten und wenn da alles geklappt hat, vergleicht er nochmal alles in Byte-Schritten.
Edit: Irrtum bei Comparemem. Der überprüpft die Bytes nicht nochmal von vorn (Habe zuerst das AND EDX,3 übersehen, was ich grad einfügen wollte :oops: )
Also: kein Potenzial

[QuickAndDirty]

Wenn das letzte Zeichen des gesuchten Strings, im gesuchten string nochmal vorkommt wird es nihct gehen ne?


Gesucht
S=ADD
in
T=abADDcfgh

ich vergleiche S[3] mit T[3] und springe dann 3 weiter ja?

und dann?

Ich hab mir nur deine beschreibung durchgelesen den Code sehe ich mir gleich noch mal an.
Vielleicht gebt es das Problem im Code ja garnicht.

[Edit]
OK die skip Tabelle löst das Problem, schon gut hab nichts gesagt
[/EDIT]

[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'?

[QuickAndDirty]

zum Optimieren:
du kannst dir die vergleiche in der While Schleife (i > k) sparen
und eine
While true do
Schleife nehmen

wenn du vorher am ende von SText für einen garantierten Treffer sorgst!!! (Methode von Wirth der Typ von Pascal)
Das ist zwar nicht so einfach weil do eine art PosEx auf die letzen length(sSubstring) zeichen in sText ausführen must
um heraus zufinden welche der zeichen von sSubstring noch angehängt werden müssen, aber dann sollte es gehen.

Beispiel 1
S=FG
T=ABCDEFGHIJKLMN

anhängen
ABCDEFGHIJKLMNFG

Beispiel 2
S=NG
T=ABCDEFGHIJKLMN

anhängen
ABCDEFGHIJKLMNG


am ende der Schleife brauchst du nur prüfen ob der Treffer DEIN Treffer ist oder ein Echter Treffer.
So sparst du dir bei großen Texten auf jeden Fall ne Menge vergleiche.

[alzaimar]

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

[sirius]

Zitat:

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'?

:gruebel: 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:

Zitat von sirius

:gruebel: Wo habe ich was von PChar geschrieben?

War darauf bezogen.

Zitat:

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:

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 :wink: . alzaimar's Algorithmus ist sicher auch ohne Assembler wesentlich schneller (hat er ja auch geschrieben).

Gruß
xaromz

[Luckie]

Zitat:

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:

Delphi-Quellcode:

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

[sirius]

Daran habe ich auch gedacht :gruebel:
Ich schau nochmal.

[Tyrael Y.]

Was ist wenn mein SubString nur aus einem Zeichen besteht?

Delphi-Quellcode:

  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:

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 :gruebel:

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

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:

Zitat von Tyrael Y.

Zitat:

Zitat von sirius

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

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:

Zitat von sirius

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

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

[SirThornberry]

Zitat:

Zitat von Tyrael Y.

Zitat:

Zitat von sirius

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

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.

[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 :thumb: . Die Sprungtabelle und das Vergleichen des ersten Zeichens sind der Kern. Der Rest ist Zugabe.

[alzaimar]

Zitat:

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:

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:

Zitat von alzaimar

Zitat:

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:

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 :zwinker:
Ansonsten bringt dein Algortihmus nix. Das kann man immernoch ohne Assembler machen. In der Testroutine von oben sind alle drei (fast) identisch.

[Amateurprofi]

Zitat:

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:

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 :zwinker:

[jbg]

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