Boyer Moore Algorithmus

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

[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