![]() |
AW: Boyer Moore Algorithmus
Zitat:
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. |
AW: Boyer Moore Algorithmus
Hallo,
ich habe mal himitsu's Version geändert, welche bei mir nicht übel abschneidet.
Delphi-Quellcode:
Der Suchtext besteht aus 100000 Zeilen.Gesamtlänge 6.2 Mio Zeichen
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;
Code:
Gruß Horst
"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 |
AW: Boyer Moore Algorithmus
Liste der Anhänge anzeigen (Anzahl: 1)
Moin,
Bei mir sieht das ganz anders aus ?! Ich hab mal noch hier den dazu genommen ![]()
Code:
50 Durchläufe/Test. Datei 100000 Zeilen.
"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 |
AW: Boyer Moore Algorithmus
Zitat:
Zitat:
|
AW: Boyer Moore Algorithmus
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:
und der unbekannten CPU von Ginko:
" 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
Code:
Da liegen ja Welten bei BMH /Std PosEx zwischen bei mir 284/1021=0,278 und bei Ginko 423/3643 = 0,116.
" 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 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 |
AW: Boyer Moore Algorithmus
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. |
AW: Boyer Moore Algorithmus
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 ![]() 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:
Ausgabe:
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); ..
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 |
Alle Zeitangaben in WEZ +1. Es ist jetzt 02:16 Uhr. |
Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz