Schnellster Stringmatching-Algorithmus in ASM übersetzen

[hoika]

Hallo,

doch geht, siehe http://www.fastcodeproject.org/

Allein das Schreiben in Assembler bringt aber noch keinen Vorteil.
Mit Assembler kann ich auch langsamen Code schreiben.
NOP, NOP, NOP. ;)


Heiko

[stoxx]

Zitat:

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

alllsooo :-)

bevor man mit ASM optimiert, von dem ich sowieso keine Ahnung habe *grien* .. muss man sich erst einmal fragen, was man tun möchte, damit man nicht auf eine falsche Fährte gelockt wird.


Ein Bayer Moore Algorithmus hat ja immer noch die Laufzeit O(m/n).
m ist die Länge des zu durchsuchenden Textes und n die Länge des Suchstrings. Die Laufzeit wird also besser, je länger der zu suchende String ist.
Eine Laufzeit O(m) zum Beispiel wäre ja eine lineare Abhängigkeit der Laufzeit vom zu durchsuchendem Text. (Wenn der Text doppelt so lang wird, brauch ich doppelt so lange Zeit zum Suchen)
Wenn also m=n wäre und der Suchtext gleich lang dem zu durchzuchendem Text, dann hättest Du eine Laufzeit von O(1) .. egal wie lang der Text wäre, der Algorithmus wäre gleich schnell (weil Du wahrscheinlich nur das erste und letzte Zeichen vergleichen könntest)

Der Bayer Moor Algorithmus wäre also bei Aufgaben interessant, wenn man die gesamte Festplatte unindiziert nach Vorkommen eines bestimmten Wortes durchsucht.
Das macht Windows irgendwie in annehmbarer Zeit, naja ... geht so :-). Jetzt wäre also die Frage, wie oft will und braucht man das ...
Vor allen Dingen, weil in der realen Umsetzung bei Deiner explode Funktion der Algorithmus gar nicht das wahre Nadelöhr ist, sondern die häufigen String-Kopien..

http://www.delphipraxis.net/internal...=849704#849704


Wenn man eine einfache Suche mit Deiner Explode Funktion intelligent programmiert und noch etwas umgeschrieben in die eigene Klasse bastelt, hat man die Daten in der doppelten Geschwindigkeit verarbeitet, wie man braucht, um sie nur roh von der Festplatte zu lesen. (lesen von CSV Dateien)
750 ms als Beispiel um 100 MB Daten von der Festplatte zu lesen, und weitere 750 ms um sie auseinander zu dividieren.



Ich finde, dafür ist es nicht wert, den Algorithmus noch stark auf ASM zu optimieren. Gut, dann würen man irgendwann fast mit Festplattengeschwindigkeit. hmmm .. na gut, mir fällt dazu im Moment kein Anwendungsfall ein.

Ich denke, viel interessanter ist die Frage, wie durchsucht man einen relativ festen Datenbestand oder einen langen String, nach immer wieder anderen Texten. (Dictionary) (Typischer Anwendungsfall wäre die Suchmaschine Google. Die Zeit für eine Suche ist ja nicht abhängig von der Größe des Internets, also KEINE Laufzeit O(m) sondern nur abhängig von der Länge des Suchbegriffs (also O(n) )
Oder man will alle Vorkommen von Gensequenzen in einem ewig langem String durchsuchen ...


Und dafür gibts sehr moderne Algorithmen, wie Suffix-trees .. oder besser Suffix-Arrays, die zwar ein klein wenig langsamer sind als die Trees, aber dafür nicht soviel Speicher verbraten (bei intelligenter PRogrammierung stehen die Arrays den Trees sogar in nix nach)
Außerdem kann man so einen Suffixarray auf der Festplatte speichern, so einen Baum muss man immer neu aufbauchen.
(eine SuffixArray implementierung in Delphi hab ich leider nicht)

Ich hatte mir mal vor einiger Zeit einen SuffixTree von einem C-Quelltext umgeschrieben. wir könnten das ja mal vergleichen, im direkten Vergleich. Wenn Du Lust hast, können wir uns mal kurzschließen :-)
Aufgabe also: Wie durchsuche ich einen Datenbestand auf alle Vorkommen eines Subtextes, möglichst schnell ... (mit Indizierung)
Nur, wenn Du das für Deinen Anwendungsfall benötigst ...

Gruß stoxx

[Gausi]

Zitat:

Zitat von stoxx

Ein Bayer Moore Algorithmus hat ja immer noch die Laufzeit O(m/n).

Also erstens heißt das Boyer-Moore, und zweitens hat das Ding im Mittel ne Laufzeit von O(log(n)/n * m) (log zur Basis der Alphabetgröße, aber das ist ja egal). Im Worst-Case ist die Laufzeit O(m*n) bzw. O(m), je nachdem welche Boyer-Moore-Variante man nun genau nimmt (Wikipedia nicht fragen, da steht teilweise Stuss.) O(1), wenn m=n ist, ist auch Quatsch - wenn das Muster gleich dem Text ist, muss man das ja überprüfen, man hat also m Schritte im Worst-Case, einen im Best-Case, also O(m) im Mittel. ;-)

Ich habe nicht den ganzen Thread gelesen, aber der Algorithmus ganz oben sieht sehr nach Quicksearch (von Sunday) aus, eine Variante von Boyer-Moore-Horspool. Diese beiden Algorithmen sind in vielen Anwendungsgebieten die schnellsten bekannten Algorithmen (ja, schneller als der Standard-Boyer-Moore!). Zumindest für den Fall, dass man den zu durchsuchenden Text nicht aufbereitet, sondern nur das Suchmuster, aber das ist ja ne ganz andere Herangehensweise.

Für kleine Alphabete (z.B. für eine Suche in DNS-Sequenzen) eignen sich dann allerdings andere Algorithmen besser. Da wären die Faktor-basierten Algorithmen (die auch mit Suffix-Trees arbeiten) besser, oder die sogenannten Faktor-Orakel, die so um 2001 das "erfunden" wurden.

Ansonsten ist der Algorithmus im ersten Beitrag sehr zu empfehlen, und eine Optimierung halte ich im Gegnsatz zu meinem Vorredner für durchaus sinnvoll. :-D

[stoxx]

Zitat:

Zitat von Gausi

Zitat:

Zitat von stoxx

Ein Bayer Moore Algorithmus hat ja immer noch die Laufzeit O(m/n).

Also erstens heißt das Boyer-Moore, und zweitens hat das Ding im Mittel ne Laufzeit von O(log(n)/n * m) (log zur Basis der Alphabetgröße, aber das ist ja egal). Im Worst-Case ist die Laufzeit O(m*n) bzw. O(m), je nachdem welche Boyer-Moore-Variante man nun genau nimmt (Wikipedia nicht fragen, da steht teilweise Stuss.) O(1), wenn m=n ist, ist auch Quatsch - wenn das Muster gleich dem Text ist, muss man das ja überprüfen, man hat also m Schritte im Worst-Case, einen im Best-Case, also O(m) im Mittel. ;-)

Ich habe nicht den ganzen Thread gelesen, aber der Algorithmus ganz oben sieht sehr nach Quicksearch (von Sunday) aus, eine Variante von Boyer-Moore-Horspool. Diese beiden Algorithmen sind in vielen Anwendungsgebieten die schnellsten bekannten Algorithmen (ja, schneller als der Standard-Boyer-Moore!). Zumindest für den Fall, dass man den zu durchsuchenden Text nicht aufbereitet, sondern nur das Suchmuster, aber das ist ja ne ganz andere Herangehensweise.

Für kleine Alphabete (z.B. für eine Suche in DNS-Sequenzen) eignen sich dann allerdings andere Algorithmen besser. Da wären die Faktor-basierten Algorithmen (die auch mit Suffix-Trees arbeiten) besser, oder die sogenannten Faktor-Orakel, die so um 2001 das "erfunden" wurden.

Ansonsten ist der Algorithmus im ersten Beitrag sehr zu empfehlen, und eine Optimierung halte ich im Gegnsatz zu meinem Vorredner für durchaus sinnvoll. :-D

hehe .. danke, Du hast Recht mit der Laufzeit O(1) ... war zu kurz nachgedacht.
In der realen Anwendung hats mir halt nix gebracht,.... Wenn es mich sehr viel Zeit kostet,die Daten irgendwo herzubekommen, wie sie dann zu durchsuchen .. (mit dem einfachsten suchalgorithmus beim linearen durchgehen mit einer simplen Pascal Schleife ... hmmm .. dann kann ich höchstens den Faktor 2 sparen. Weil die Daten muss ich ja noch irgendwo beschaffen.
Wenn ich dann noch einmal zuviel kopiere, dann wird noch langsamer ( guck Dir mal die Explode Implementierung an)
und da kann der Algorithmus gar nix mehr machen. Da dauerts einfach drei oder viermal so lange. Nur weil man ihn schlecht umgesetzt hat.
Naja ... waren nur die praktischen Erfahrungen.
Die Theorie eines Algorithmus muss nicht unbedingt in der Praxis zutreffen. Suffix Arrays sind per Definition laut mathematik langsamer als Suffix-Trees. Dennoch gibt es C-implementationen die genauso schnell sind, wie ein Tree ..
So ist das eben :)

[Gausi]

Ich hab ja auch nicht von der Theorie gesprochen, sondern von der Praxis. ;-) In der Theorie ist Knuth-Morris-Pratt super, weil er ne lineare Worst-Case-Laufzeit hat. Praktisch nutzbar ist er nicht. Boyer-Moore kann man prima analysieren, aber wenn man davon den Teil weglässt, der dafür sorgt, dass die Laufzeit auch im Worst-Case linear wird (und nicht n*m), dann wirds in der Praxis fast doppelt so schnell.

Mal ein paar Beispiel-Zeiten von meinen aktuellen Tests, einfache Implementierungen ohne besondere Optimierung (Textlänge: 1MB, Alphabetgröße: 25, Musterlänge: 100 Zeichen, Zufallstexte/-Muster):

Naiver Algorithmus (nicht pos, sondern was selbstgebautes): 4ms
Knuth-Morris-Pratt (standard/verbessert): 5,3ms/3,5ms
Boyer-Moore (standard/verbessert): 520µs/321µs
Quicksearch (das Dingen hier): 318µs
Boyer-Moore-Horspool: 299µs

Die "verbesserten" Varianten setzen die Ideen zu "schnellen Implementierung" aus den entsprechenden Original-Artikeln um. In der Regel sind die letzten drei fast gleichwertig, aber sehr häufig hat der letzte die Nase ein paar µs vorne. Wenn das Nadelöhr allerdings eh woanders liegt, ist das natürlich alles wurscht. :stupid:

[alzaimar]

In meinen Tests hat der Horspool schlechter abgeschnitten als Quicksearch. Vielleicht zeigst du mal deine Version, meine Tests beruhten auf den Implementierungen von Charras & Lecroq.

Einen sehr interessanten Ansatz habe ich hier entdeckt. Er basiert auf Sundays Arbeit, kann jedoch die Anzahl der Vergleiche halbieren. Leider ist er in der Praxis bei meinen Tests langsamer, was wohl an dem Overhead der indirekten Indizierung liegt. Ein Paradebeispiel, das theoretische Überlegungen nicht immer das Maß aller Dinge ist.

Noch etwas zu Tries, DAWGs etc. Das sind wahre Performancewunder, aber leider verbraten sie so dermaßen viel Speicher, das sie sich in der Praxis nicht zum Suchen in langen Texten eignen. Als Wörterbuch sind sie dagegen wirklich 'kinky'.

Hab ich erwähnt, das ich den QSearch für eine sehr schnelle Adresssuche verwende? Wir haben ca. 500.000 Kundenadressen, und die Disponenten kenn manchmal nicht den vollständigen Kundennamen, sondern nur Teile, oder Straße etc. Mit Quicksearch kann ich eine 'while-you-type' Suche in Echtzeit durchführen. Der Disponent tippt also 'Kassu' ein, das Teil findet 'Dipl. Ing. Kassupke' ,'Die Kassupke Company' etc.

Die gewünschte (und mit FastCode.org erreichte) teilweise drastische Verbesserung hat nur sportliche Aspekte, weil man den Unterschied in meinem Anwendungsfall eh nicht merkt.

[Gausi]

Ich habe den Horspool "ausgerollt". Kann man auch bei Boyer-Moore selbst anwenden, dadurch wird BM in eingen Fällen doppelt so schnell. Der Trick ist, einge Dinge auszulagern. Dafür ändert man das Bad-Character-Array für das letzte Zeichen des Musters ab und kann so in einer "schnellen Schleife" das Muster rüberschieben, bis mal ein passendes Zeichen gefunden wurde. dann geht man aus der schnellen Schleife raus und fängt mit der Überprüfung an.
Dieser Trick funktioniert bei Quicksearch allerdings nicht ;-).

Delphi-Quellcode:

function PreProcess_BMH_BC(p: String): TBC_IntArray;
var i, m: Integer;
    c: Char;
begin
  m := Length(p);
  for c := low(Char) to High(Char) do
    result[c] := m;
  for i := 1 to m-1 do     
    result[p[i]] := m-i;
end;

// Suche mit Horspool, direkt die unrolled-Variante. Sehr ähnlich zu BM_Unrolled
function Search_BMH_Unrolled(t,p: String): Integer;
var m, n, k, j: Integer;
    BC: TBC_IntArray;
    BC_last: Integer;
    Large: Integer;
begin
  m := Length(p);
  n := Length(t);
  Large := m + n + 1;

  BC := PreProcess_BMH_BC(p);

  // "echten" BC-Shift merken
  BC_last := BC[p[m]];
  // BC(lastCh) mit "Large" überschreiben
  BC[p[m]] := Large;

  k := m;
  result := 0;

  while k <= n do
  begin
      //fast loop
      repeat
        k := k + BC[t[k]];
      until k > n;

      //undo
      if k <= Large then
        //Muster nicht gefunden
        break
      else
        k := k - Large;

      j := 1;
      // slow loop
      while (j < m) and (p[m-j] = t[k-j]) do
        inc(j);

      if j=m then
      begin
        // Muster gefunden
        result := k - j + 1;
        k := k + m; //oder: k+1, oder: break; je nachdem, wie man den Text komplett durchsucht haben will
      end else
      begin
          // Muster verschieben
          if t[k] = p[m] then
            k := k + BC_last    // Hier dann den original-Wert nehmen
          else
            k := k + BC[t[k]];
      end;
  end;
end;

[stoxx]

Zitat:

Noch etwas zu Tries, DAWGs etc. Das sind wahre Performancewunder, aber leider verbraten sie so dermaßen viel Speicher, das sie sich in der Praxis nicht zum Suchen in langen Texten eignen. Als Wörterbuch sind sie dagegen wirklich 'kinky'.

nur zur Info: Suffixarrays brauchen genauso viel Platz, wie die Original Daten selber. Die Daten werden nur geschickt umsortiert. und sind (fast) genauso schnell, wie Suffixtrees ...

[Sereby]

Tut mir leid das alte Thema aus der Versenkung holen zu müssen.
Aber als ich gestern auf da Thema gestoßen bin war ich erstmal begeistert doch heute, als ichs in meinem projekt getestet habe, dann doch etwas enttäuscht denn:

Durch die Funktion "CharPos_JOH_SSE2_1_b" wird irgendwie das Memory Management durcheinandergebracht oder wie auch immer. Denn sobald diese Funktion mit-compiliert wird bekomme ich an einer völlig anderen stelle, die überhaupt nicht mit diesem Pos zu tun hat (beim auslesen eines Streams mit (TMemoryStream).Read), eine "Invalid floating Point Value" Fehlermeldung beim versuch etwa 800kb zu lesen.

Aber erst beim 2. Versuch eine etwas größere Datei zu lesen.
1. Datei ~ 30kb -> liest er anscheinend Problemlos.
2. Datei danach ~ 850KB -> Bums.... Fehlermeldung bei Read!

Wenn die "CharPos_JOH_SSE2_1_b" Funktion nicht mit-compiliert wird funktioniert alles Problemlos!

Zusatzinfo: ich verwende auch die neueste Version von FastMM4

Wer weiss woran es liegt oder ne Ahnung hat: bitte sagts mir :-)

[alzaimar]

Das Einzige, was sein könnte, ist die Verwendung spezieller ASM-Befehle. Ich hab die Routine vom den FastCode-Projekt (www.FastCode.Org). Dort gibt es auche reine Pascal-Routine, die diesbezüglich keine Probleme machen sollte.

Kompiliere das Ganze mal mit 'RangeCheck' und 'Overflowcheck' on (Bereichs- und Überlaufprüfung). Vielleicht ist ja noch ein Korken im Code.

edit: Der genannte Link ist tot, der hier aber nicht
www.fastcodeproject.org