Einzelnen Beitrag anzeigen

alzaimar
(Moderator)

Registriert seit: 6. Mai 2005
Ort: Berlin
4.956 Beiträge
 
Delphi 2007 Enterprise
 
#35

Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen

  Alt 7. Dez 2007, 22:11
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.
Angehängte Dateien
Dateityp: pas fastposunit_523.pas (16,3 KB, 33x aufgerufen)
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat