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

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