Boyer Moore Algorithmus

[Amateurprofi]

Zitat von Horst_:

Hallo,

@Amateurprofi:
Du hat Deine CPU aber noch nicht die Frequenz hochgeschraubt..
Wenn ich nur Test aufrufe, kommt 6684 / 6660 raus->delta = 24
Wenn ich in Test nach der Festlegung auf CPU1 eine rechneintensive Schleife einbaue ~1 Sekunde dann habe 1700/1694-> delta= 6 ( recht genau 3.2/0.8 [Ghz/Ghz]
Hier gibt es auch schon eine Variante mit REPNE SCASB
http://www.delphipraxis.net/51284-te...n-zaehlen.html
Lazarus will es nicht kompilieren und wenn ich EAX und EDX wieder einsetze statt &S und EAX um 1 statt 65536 erhöhe und shr 16 entferne , zählt das Programm bei 100000 Zeilen "Franz jagt..." nur 85 "Taxi" in nur 209 ms statt über 300 ms für alle anderen.

Gruß Horst

Hallo Horst,
Zu "Frequenz hochgeschraubt"
Sorry, aber da sehe ich keinen Zusammenhang.
Ich messe ja nicht Zeit, sondern CPU-Ticks.
Da sollte es doch völlig egal sein, ob die CPU nun 3G-Takte/s macht, oder 1 Takt pro Stunde.
Es sei denn, die Frequenzerhöhung würde bewirken, dass dann die CPU pro Takt mehr Befehle abarbeitet, aber das kann ich mir nicht vorstellen. Sie macht eben bei hoher Frequenz mehr pro Zeiteinheit, jedoch nicht mehr pro Takt.
Wie auch immer, wenn auch geringfügig, ist REPNE SCASB langsamer als das konventionelle Zählen.

Zu "&S"
Versuche es mal ohne das "&", könnte sein, dass es dann verstanden wird.

Zu EAX um 1 statt um $10000 erhöhen.
Ja klar, kommt dann kein richtiges Ergebnis.
Das was Du als 85 x gefunden interpretierst ist nicht die Anzahl gefundener Taxis sondern der Buchstabe "U".

Mit XOR EAX,EAX und dann MOV AL,[ESI] wird das erste Zeichen des zu suchenden Textes in AL gestellt, und die oberen 3 Bytes in EAX genullt. (Ich hätte das XOR EAX,EAX weggelassen und mit MOVZX EAX, [ESI].Byte das gleiche erreicht).

Wenn du nach "Taxi" suchst, steht beim ersten Durchlauf in AL $54 = "T".
Wird dann das erste Mal "Taxi" gefunden, und du erhöhst EAX um 1, dann steht in AL nicht mehr $54 = "T" sondern $55 = "U" und es wird nicht mehr nach "Taxi" sondern nach "Uaxi" gesucht.
Das wird nicht gefunden, also steht am Schluss in EAX $55 = "U" = 85, dass dann als vermeintliche Anzahl Fundstellen zurückgegeben wird.

Ich hätte ohnehin nicht im Hi-Word von EAX gezählt, sondern lieber in EBP gezählt, natürlich am Anfang ein PUSH EBP und am Ende ein POP EBP.
So wie es ist, wird ohne jede Not die maximale Anzahl der Fundstellen auf 65536 limitiert, mit dem unschönen Effekt, dass bei mehr als 65536 Fundstellen 65536 zurückgegeben wird - was zu Fehlinterpretationen führen kann.

[Horst_]

Hallo,

ich habe mal himitsu's Version geändert, welche bei mir nicht übel abschneidet.

Delphi-Quellcode:

function CountString(const S, SubStr: string): integer; assembler;
// Leicht geändert, zählt nicht nur bis 65536
// Siehe www.delphipraxis.net/51284-teil-string-anderem-string-suchen-zaehlen.html
asm
         PUSH    ESI
         PUSH    EDI
         PUSH    EBX
         TEST    EAX, EAX
         JE      @Exit          // S nicht vorhanden
         TEST    EDX, EDX
         JE      @Exit0         // SubString nicht vorhanden
         MOV     ESI, EDX       // EDI Adresse SubString
         MOV     EDI, EAX       // EDI Adresse S

         MOV     ECX, [EDI - 4] // Laenge S
         MOV     EDX, [ESI - 4] // Laenge SubString
         DEC     EDX            // Restlaenge des Substrings, die untersucht werden muss
         JS      @Exit0         // Substring hatte Laenge = 0

         MOV     AL, [ESI]      // Erstes Zeichen des Substrings nach dem gesucht wird
         INC     ESI            // Startpos fuer dahinter weiter vergleichen
         SUB     ECX, EDX       // Differenz der Laengen
         JLE     @Exit0         // Substring laenger als S -> und tschuesz

         MOV     EBX, ECX
         PUSH    Dword 0        // Anzahl Vorkommen auf dem Stack an [ESP]
         @Loop:
         MOV     ECX, EBX
         REPNE   SCASB          // Suche erste Zeichen
         JNE     @Ready           // Suche abgeschlossen
         MOV     EBX, ECX       // Position merken
         PUSH    ESI             // Merken für den naechsten Such-Durchgang
         PUSH    EDI
         MOV     ECX, EDX       // Die noch zu vergleichende Anzahl
         REPE    CMPSB          // Vergleich des Restes des Substrings ab dort
         POP     EDI
         POP     ESI
         JNE     @Loop
         INC     [ESP]          //erhoehe Anzahl Vorkommen
         JMP     @Loop

         @Exit0:
         MOV     EAX,0
         JMP     @Exit
         @Ready:
         POP     EAX
         @Exit:
         POP     EBX
         POP     EDI
         POP     ESI
end;

Der Suchtext besteht aus 100000 Zeilen.Gesamtlänge 6.2 Mio Zeichen

Code:

"Taxi"
Asm        Count: 100000 in 544ms
BMH Count:        100000 in 321ms
SP Search Count: 100000 in 564ms
Std PosEx Count: 100000 in 340ms
himitsu Count:    100000 in 280ms   <---

" Taxi" // Ein häufiger Buchstabe vorne
Asm        Count: 100000 in 819ms
BMH Count:        100000 in 284ms <---
SP Search Count: 100000 in 544ms
Std PosEx Count: 100000 in 1021ms
himitsu Count:    100000 in 745ms

"XTaxi"  // Ein nicht vorhandener Buchstabe vorne
Asm        Count: 0 in 519ms
BMH Count:        0 in 244ms
SP Search Count: 0 in 471ms
Std PosEx Count: 0 in 212ms
himitsu Count:    0 in 210ms        <--

// Die fast längste Zeile #13#10 fehlt
"Franz jagt im komplett verwahrlosten Taxi quer durch Bayern."
Asm        Count: 100000 in 396ms  <---
BMH Count:        100000 in 534ms
SP Search Count: 100000 in 806ms
Std PosEx Count: 100000 in 453ms
himitsu Count:    100000 in 482ms

//Ein nicht vorhandener Buchstabe am Ende eines langen Textes
"Franz jagt im komplett verwahrlosten Taxi quer durch Bayern.X" 
Asm        Count: 0 in 1189ms
BMH Count:        0 in 69ms <--- auch nur 89 Mb/s
SP Search Count: 0 in 340ms
Std PosEx Count: 0 in 440ms
himitsu Count:    0 in 484ms

Gruß Horst

[Ginko]

Moin,
Bei mir sieht das ganz anders aus ?! Ich hab mal noch hier den dazu genommen http://www.delphipraxis.net/711182-post1.html, der schlägt sich bei mir bis jetzt am besten (Alles im Anhang).

Code:

"Taxi"
BMH Count:        100000 in 503ms
SP Search Count: 100000 in 785ms
Asm AmatProf:     100000 in 743ms
QSSearch Count:   100000 in 396ms <---
Asm himitsu:      100000 in 1463ms
Std PosEx Count: 100000 in 1559ms

" Taxi" // Ein häufiger Buchstabe vorne
BMH Count:        100000 in 423ms <--
SP Search Count: 100000 in 752ms
Asm AmatProf:     100000 in 1185ms
QSSearch Count:   100000 in 423ms <--
Asm himitsu:      100000 in 3854ms
Std PosEx Count: 100000 in 3643ms

"XTaxi" // Ein nicht vorhandener Buchstabe vorne
BMH Count:        0 in 409ms
SP Search Count: 0 in 666ms
Asm AmatProf:     0 in 405ms
QSSearch Count:   0 in 305ms <--
Asm himitsu:      0 in 1177ms
Std PosEx Count: 0 in 1178ms

// Die fast längste Zeile #13#10 fehlt
"Franz jagt im komplett verwahrlosten Taxi quer durch Bayern."
BMH Count:        100000 in 1191ms
SP Search Count: 100000 in 1343ms
Asm AmatProf:     100000 in 592ms <--
QSSearch Count:   100000 in 601ms
Asm himitsu:      100000 in 2353ms
Std PosEx Count: 100000 in 2031ms

//Ein nicht vorhandener Buchstabe am Ende eines langen Textes
"Franz jagt im komplett verwahrlosten Taxi quer durch Bayern.X"
BMH Count:        0 in 103ms
SP Search Count: 0 in 413ms
Asm AmatProf:     0 in 1276ms
QSSearch Count:   0 in 79ms <--
Asm himitsu:      0 in 2455ms
Std PosEx Count: 0 in 2050ms

//Nur ein Buchstabe
"t"
BMH Count:        400000 in 1989ms
SP Search Count: 400000 in 1987ms
Asm AmatProf:     400000 in 841ms <--
QSSearch Count:   400000 in 1289ms
Asm himitsu:      400000 in 2137ms
Std PosEx Count: 400000 in 2677ms

"Franz jagt im komplett"
BMH Count:        100000 in 667ms
SP Search Count: 100000 in 757ms
Asm AmatProf:     100000 in 739ms
QSSearch Count:   100000 in 339ms <--
Asm himitsu:      100000 in 1753ms
Std PosEx Count: 100000 in 1831ms

50 Durchläufe/Test. Datei 100000 Zeilen.

[Furtbichler]

Zitat von Furtbichler:

Superduperschnell ist es nicht, aber benötigst du unbedingt BM? Und wenn ja, dann vermutlich besser QuickSearch....

Zitat von Ginko:

Ich hab mal noch hier den dazu genommen

Sag ich doch.

[Horst_]

Hallo,

ich bin erstaunt über die großen Unterschiede zwischen meinem AMD Phenom II X4 955 3.2Ghz
// etwas umgestellt zum besseren Vergleich
//50 Durchläufe

Code:

" Taxi" // Ein häufiger Buchstabe vorne 
BMH Count:       100000 in 284ms <--- 1091 Mb/s
SP Search Count: 100000 in 544ms
Asm AmatProfi  : 100000 in 819ms
himitsu Count:   100000 in 745ms
Std PosEx Count: 100000 in 1021ms

und der unbekannten CPU von Ginko:

Code:

" Taxi" // Ein häufiger Buchstabe vorne
BMH Count:       100000 in 423ms <---  733 Mb/s
SP Search Count: 100000 in 752ms
Asm AmatProf:    100000 in 1185ms
QSSearch Count:  100000 in 423ms <--
Asm himitsu:     100000 in 3854ms
Std PosEx Count: 100000 in 3643ms

Da liegen ja Welten bei BMH /Std PosEx zwischen bei mir 284/1021=0,278 und bei Ginko 423/3643 = 0,116.
Auch BMH/asm himitsu/ ist ja völlig anders:
Bei mir 284/745 = 0,381 gegenüber 284/3854 = 0,0737 ( völlig induskutabel nur 7% von BMH)
Zumal dabei Amateruprofis Version mehr als 3 mal schneller, während es bei mir langsamer ist.
Da beide Sachen in Assembler sind, wird ein der Code identisch umgesetzt, egal welcher Compiler dort am Werk ist.
Ich bin sehr erstaunt über die Größe des Unterschiedes.
Zur Geschwindigkeit an sich, das dort 310 Mb (6.2e6*50) in 69/109 ms abgeklappert werden habe ich vorhin unterschlagen.
Statt 89 Mb/s sind 50*89 = 4.45 Gb/s

Gruß Horst

[Ginko]

Das gute abschneiden der Standard PosEx Funktion bei dir wundert mich schon sehr.
Also bei Post 42.

Meine Daten zum Test:
CPU Typ DualCore Intel Core 2 Duo E6400, 1600 MHz (6 x 267) (StandardMax 2400 Mhz, auf 1600 festgelegt über Energieoptionen)
2 GB Speicher
Win 7 32Bit
Lazarus 1.0.8

@Furtbichler ich hatte auch schon mal einen QS nach Sunday drinnen, der hat aber nicht gut abgeschnitten (deshalb hatte ich ihn auch wieder rausgemacht), die Verbesserung von alzaimar machen scheinbar viel aus.

[Horst_]

Hallo,

ich habe die tatsächlich die selben Bedingungen.Ob 4 oder 2 Gb Speicher ist ja hier wohl nicht relevant.
Es könnte daran liegen, das diese AMD CPU 6 MB Level III Cache hat, aber dies kann nicht soviel ausmachen, schließlich durchsuchst Du in 103 ms einen nicht vorhandenen String und ich brauche 69 ms, bei doppelter CPU-frequenz.
Müßig darüber nachzudenken, Du hast ja noch etwas schnelleres gefunden.

Gruß Horst
P.S.
Heute morgen bei mir mal http://www.delphipraxis.net/attachme...tring_test.zip getestet, aber die Funktion an eine CPU gekettet.
Das bringt aber fast nichts, die Messwerte schwanken etwas weniger.Ich klicke 4..5 mal schnell auf die Start Test Schaltfläche und nehme die letzte Ausgabe.

Delphi-Quellcode:

procedure TForm1.Button2Click(Sender: TObject); //Test starten
var
  Filestream: TFileStream;
  SuchWort, SuchText: string;
  i, Ergebnis, Durchlaeufe: integer;

  samask, pamask, tamask: NativeUInt;
begin
    // Thread auf 1 CPU fixieren
  GetProcessAffinityMask(GetCurrentProcess, pamask, samask);
  if pamask = 0 then
    exit;
  tamask := 1;
  while tamask and pamask = 0 do
    tamask := tamask shl 1;
  SetThreadAffinityMask(GetCurrentThread, tamask);
..

Ausgabe:

Code:

"Taxi"
BMH Count:         100000 in 313ms
SP Search Count: 100000 in 549ms
Asm AmatProf:    100000 in 444ms
QSSearch Count: 100000 in 280ms
Asm himitsu:       100000 in 273ms
Std PosEx Count: 100000 in 329ms

" Taxi"
BMH Count:         100000 in 275ms
SP Search Count: 100000 in 524ms
Asm AmatProf:    100000 in 638ms
QSSearch Count: 100000 in 248ms
Asm himitsu:       100000 in 729ms
Std PosEx Count: 100000 in 1000ms

zuvor , man sieht Asm Count= Asm Amateur Profi jetzt 20% schneller ist, wie kann das sein, der selbst Code, der selbe Compiler (Laz 1.08/FPC 2.6.2) ?

//" Taxi" // Ein häufiger Buchstabe vorne
//Asm       Count: 100000 in 819ms
// BMH Count:       100000 in 284ms <---
// SP Search Count: 100000 in 544ms
// Std PosEx Count: 100000 in 1021ms
// himitsu Count:   100000 in 745ms