|
Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen
@sirius:
du schreibst in der ersten Zeile deiner Tabelle 1641 Ticks, 5904826 Takte Ich vermute, daß du unter "Ticks" die von GetTickCount gelieferten Werte verstehst (das sind Millisekunden). Wenn wir nun die von dir genannten 5904826 Takte durch die 1641 ms teilen kommen wir darauf, daß dein Rechner mit einer Taktfrequez von knapp 3.5 MHz läuft. Kann das sein ? Deine Methode, die Performance zu messen, scheint mir sehr fragwürdig zu sein. Warum: Wenn du eine Routine 100 mal durchlaufen läßt und die Gesamtzeit für diese 100 Drurchläufe misst, dann enthält die Zeit auch die Zeiten, die der Rechner für andere Arbeiten verwendet. Da diese "anderen Zeiten" nicht immer gleich sind, verfälschen sie die Testergebnisse. Ich gehe so vor: Ich lasse eine Routine 5 oder auch 10 mal laufen, messe für jeden Durchlauf die CPU-Ticks und nehme das Minimum als Resultat. So versuche ich sicherzustellen, daß in dieser Zeit tatsächlich nur die von dieser Routine benötigte Zeit enthalten ist. Übrigens : wenn ich schreibe "CPU-Ticks" dann meine ich auch CPU-Ticks und nicht die von QPC gelieferten Werte. |
Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen
Hi Amateurprofi. Natürlich ist meine Testumgebung sicher. Ich erzeuge einen Zufallsstring mit dem Alphabet X. Der Suchstring enthält Zeichen, die nicht in X sind.
Ich finde 7% auch sehr gut und daher wird deine Version -mit deiner Erlaubnis- in meine Unit übernommen. Hier der FastPos-Code für Alle, bei denen der Download nicht klappt.
Delphi-Quellcode:
(******************************************************************************
* FastPos-Unit. Zusammenarbeit der Delphi-Praxis, FastCode-Challenge und * * dem QuickSearch-Algorithmus von Daniel Sunday * * * * Stellt eine Funktion zum Suchen eines Teilstrings in einem String zur * * Verfügung. Dabei wird, in Abhängigkeit der Stringlängen der jeweils beste * * Algorithmus ausgewählt * * Wenn der Suchstring aus einem Zeichen besteht, wird der Gewinner der * * FastCode-Challenge 'CharPos' ([url]www.fastcode.org[/url]) aufgerufen * * * * Wenn der Suchstring aus 2 oder 3 Zeichen besteht, oder der zu durchsuchende* * Text relativ kurz ist, dann wird der Gewinner der FastCode-Challenge 'Pos' * * aufgerufen. * * In allen anderen Fällen wird ein modifizierter QuickSearch-Algorithmus * * verwendet, der mit einer Optimierung von Timo Raita arbeitet. * * * ******************************************************************************) Unit FastPosUnit; Interface Function DPPos(Const sSubStr, sString: String): Integer; Implementation Uses SysUtils; Function QPosEx(SearchFor, SearchIn: String; Start: integer): integer; Asm pushad // Alle Register auf Stack legen sub esp,$400 // Platz für Skiptabelle schaffen // Auf dem Stack liegen folgende Daten // ESP : Skiptabelle // ESP+$400..$410 : EDI, ESI, EBP, ESP, EBX // ESP+$414 : EDX Adresse SearchIn // ESP+$418 : ECX Start // ESP+$41C : EAX Adresse SearchFor // ESP+$420 : EBP // ESP+$424 : Returnadresse // Prüfen, ob SearchFor oder SearchIn leer ist, oder Start negativ ist test eax,eax je @Fail // SearchFor ist leer test edx,edx je @Fail // Searchin ist leer mov ebx,[eax-4] // Länge SearchFor test ebx,ebx je @Fail // SearchFor ist leer test ecx,ecx js @Fail // Start ist negative // Erste und letzte mögliche Fundstelle in ESI bzw. EBP je @1 sub ecx,1 // =Start 0-basierend @1: lea esi,[edx+ecx] // Ab hier soll gesucht werden add edx,[edx-4] mov ebp,edx sub ebp,ebx // Bis hier soll gesucht werden // Prüfen, ob Erste mögliche Fundstelle hinter letzter liegt cmp esi,ebp ja @Fail // Prüfen, ob SearchFor nur 1 Zeichen ist // Dann ist keine SkipTabelle erforderlich cmp ebx,1 je @Search1 // Skiptabelle erstellen // 1) for i:=0 to 255 do Skip[i]:=n+1 mov edi,esp mov ecx,$100 mov eax,ebx add eax,1 // Length(Searchfor)+1 rep stosd // 2) For i:=0 To n-1 Do Skip[SearchFor[i]]:=n-i mov edi,[esp+$41C] // Adresse SearchFor mov eax,ebx // Length(Searchfor) @FillSkip: movzx edx,[edi+ecx] // SearchFor[i] mov [esp+edx*4],eax // Skip[SearchFor[i]]:=n-i add ecx,1 sub eax,1 jne @FillSkip // Erstes und Letztes Zeichen von SearchFor in AL/AH mov al,[edi] // Erstes Zeichen SearchFor mov ah,[edi+ebx-1] // Letzes Zeichen SearchFor // Prüfen, ob Length(SearchFor) > 6 ist cmp ebx,6 ja @SearchX jmp @Vector.Pointer[ebx*4-8] @Vector: dd @Search2 dd @Search3 dd @Search4 dd @Search4 // Länge=5 dd @Search6 // Länge Searchfor > 6 @SearchX: add edi,1 // Auf zweites Zeichen von SearchFor mov [esp+$41C],edi // Merken für CompareMem jmp @Search // Länge SearchFor > 6 @SkipX: mov esi,edx // Aufruf ex CompareMem @Skip: movzx edx,[esi+ebx] add esi,[esp+edx*4] cmp esi,ebp ja @Fail @Search: cmp [esi],al jne @Skip cmp [esi+ebx-1],ah jne @Skip // Zweites bis vorletzten Zeichen von SearchFor prüfen mov edx,esi // ESI retten mov edi,[esp+$41C] // Zeiger zweites Zeichen von SearchFor add esi,1 // Zeiger Text auf nächstes Zeichen mov ecx,ebx // Length(SearchFor) sub ecx,2 // -2 (Erstes und letztes Zeichen) shr ecx,2 // =Anzahl DWords repe cmpsd // DWords vergleichen jne @SkipX // Nicht gleich mov ecx,ebx // Length(SearchFor) sub ecx,2 // -2 (Erstes und letztes Zeichen) and ecx,3 // =Anzahl restliche Bytes repe cmpsb // Bytes vergleichen jne @SkipX // Nicht gleich mov esi,edx // Fundstelle jmp @Found // Länge SearchFor=1 @Search1: mov ecx,ebp // Letzte mögliche Fundstelle sub ecx,esi // - Erste mögliche Fundstelle add ecx,1 // = Anzahl zu prüfende Zeichen neg ecx sub esi,ecx mov al,[eax] // zu suchendes Zeichen @Loop: cmp al,[esi+ecx] je @Found1 add ecx,1 jne @Loop jmp @Fail @Found1: lea esi,[esi+ecx] // ESI auf Fundstelle jmp @Found // Länge SearchFor=2 @Skip2: movzx edx,[esi+ebx] add esi,[esp+edx*4] cmp esi,ebp ja @Fail @Search2: cmp [esi],al jne @Skip2 cmp [esi+ebx-1],ah jne @Skip2 jmp @Found // Länge SearchFor=3 @Skip3: movzx edx,[esi+ebx] add esi,[esp+edx*4] cmp esi,ebp ja @Fail @Search3: cmp [esi],al jne @Skip3 cmp [esi+ebx-1],ah jne @Skip3 mov dx,[edi] cmp dx,[esi] jne @Skip3 jmp @Found // Länge SearchFor=4 oder 5 @Skip4: movzx edx,[esi+ebx] add esi,[esp+edx*4] cmp esi,ebp ja @Fail @Search4: cmp [esi],al jne @Skip4 cmp [esi+ebx-1],ah jne @Skip4 mov edx,[edi] cmp edx,[esi] jne @Skip4 jmp @Found // Länge SearchFor=6 @Skip6: movzx edx,[esi+ebx] add esi,[esp+edx*4] cmp esi,ebp ja @Fail @Search6: cmp [esi],al jne @Skip6 cmp [esi+ebx-1],ah jne @Skip6 mov edx,[edi+1] cmp edx,[esi+1] jne @Skip6 jmp @Found @Found: // Gefunden, Index berechnen sub esi,[esp+$414] add esi,1 jmp @SetRes @Fail: // Nicht gefunden, Result=0 xor esi,esi @SetRes: // Result speichern mov [esp+$41C],esi // Skiptabelle vom Stack nehmen add esp,$400 // Register wieder herstellen, Result in EAX popad End; Function CharPos_JOH_SSE2_1_b(Ch: Char; Const Str: AnsiString): Integer; Asm test edx, edx jz @@NullString mov ecx, [edx-4] push ebx mov ebx, eax cmp ecx, 16 jl @@Small @@NotSmall: mov ah, al {Fill each Byte of XMM1 with AL} movd xmm1, eax pshuflw xmm1, xmm1, 0 pshufd xmm1, xmm1, 0 @@First16: movups xmm0, [edx] {Unaligned} pcmpeqb xmm0, xmm1 {Compare First 16 Characters} pmovmskb eax, xmm0 test eax, eax jnz @@FoundStart {Exit on any Match} cmp ecx, 32 jl @@Medium {If Length(Str) < 32, Check Remainder} @@Align: sub ecx, 16 {Align Block Reads} push ecx mov eax, edx neg eax and eax, 15 add edx, ecx neg ecx add ecx, eax @@Loop: movaps xmm0, [edx+ecx] {Aligned} pcmpeqb xmm0, xmm1 {Compare Next 16 Characters} pmovmskb eax, xmm0 test eax, eax jnz @@Found {Exit on any Match} add ecx, 16 jle @@Loop pop eax {Check Remaining Characters} add edx, 16 add eax, ecx {Count from Last Loop End Position} jmp dword ptr [@@JumpTable2-ecx*4] nop nop @@NullString: xor eax, eax {Result = 0} ret nop @@FoundStart: bsf eax, eax {Get Set Bit} pop ebx inc eax {Set Result} ret nop nop @@Found: pop edx bsf eax, eax {Get Set Bit} add edx, ecx pop ebx lea eax, [eax+edx+1] {Set Result} ret @@Medium: add edx, ecx {End of String} mov eax, 16 {Count from 16} jmp dword ptr [@@JumpTable1-64-ecx*4] nop nop @@Small: add edx, ecx {End of String} xor eax, eax {Count from 0} jmp dword ptr [@@JumpTable1-ecx*4] nop @@JumpTable1: dd @@NotFound, @@01, @@02, @@03, @@04, @@05, @@06, @@07 dd @@08, @@09, @@10, @@11, @@12, @@13, @@14, @@15, @@16 @@JumpTable2: dd @@16, @@15, @@14, @@13, @@12, @@11, @@10, @@09, @@08 dd @@07, @@06, @@05, @@04, @@03, @@02, @@01, @@NotFound @@16: add eax, 1 cmp bl, [edx-16] je @@Done @@15: add eax, 1 cmp bl, [edx-15] je @@Done @@14: add eax, 1 cmp bl, [edx-14] je @@Done @@13: add eax, 1 cmp bl, [edx-13] je @@Done @@12: add eax, 1 cmp bl, [edx-12] je @@Done @@11: add eax, 1 cmp bl, [edx-11] je @@Done @@10: add eax, 1 cmp bl, [edx-10] je @@Done @@09: add eax, 1 cmp bl, [edx-9] je @@Done @@08: add eax, 1 cmp bl, [edx-8] je @@Done @@07: add eax, 1 cmp bl, [edx-7] je @@Done @@06: add eax, 1 cmp bl, [edx-6] je @@Done @@05: add eax, 1 cmp bl, [edx-5] je @@Done @@04: add eax, 1 cmp bl, [edx-4] je @@Done @@03: add eax, 1 cmp bl, [edx-3] je @@Done @@02: add eax, 1 cmp bl, [edx-2] je @@Done @@01: add eax, 1 cmp bl, [edx-1] je @@Done @@NotFound: xor eax, eax pop ebx ret @@Done: pop ebx End; Procedure Filler2; Asm nop End; Function Pos_JOH_IA32_6(Const SubStr: AnsiString; Const Str: AnsiString): Integer; Asm {Slightly Cut-Down version of PosEx_JOH_6} push ebx cmp eax, 1 sbb ebx, ebx {-1 if SubStr = '' else 0} sub edx, 1 {-1 if S = ''} sbb ebx, 0 {Negative if S = '' or SubStr = '' else 0} jl @@InvalidInput push edi push esi push ebp push edx mov edi, [eax-4] {Length(SubStr)} mov esi, [edx-3] {Length(S)} cmp edi, esi jg @@NotFound {Offset to High for a Match} test edi, edi jz @@NotFound {Length(SubStr = 0)} lea ebp, [eax+edi] {Last Character Position in SubStr + 1} add esi, edx {Last Character Position in S} movzx eax, [ebp-1] {Last Character of SubStr} add edx, edi {Search Start Position in S for Last Character} mov ah, al neg edi {-Length(SubStr)} mov ecx, eax shl eax, 16 or ecx, eax {All 4 Bytes = Last Character of SubStr} @@MainLoop: add edx, 4 cmp edx, esi ja @@Remainder {1 to 4 Positions Remaining} mov eax, [edx-4] {Check Next 4 Bytes of S} xor eax, ecx {Zero Byte at each Matching Position} lea ebx, [eax-$01010101] not eax and eax, ebx and eax, $80808080 {Set Byte to $80 at each Match Position else $00} jz @@MainLoop {Loop Until any Match on Last Character Found} bsf eax, eax {Find First Match Bit} shr eax, 3 {Byte Offset of First Match (0..3)} lea edx, [eax+edx-3] {Address of First Match on Last Character + 1} @@Compare: cmp edi, -4 jle @@Large {Lenght(SubStr) >= 4} cmp edi, -1 je @@SetResult {Exit with Match if Lenght(SubStr) = 1} movzx eax, word ptr [ebp+edi] {Last Char Matches - Compare First 2 Chars} cmp ax, [edx+edi] jne @@MainLoop {No Match on First 2 Characters} @@SetResult: {Full Match} lea eax, [edx+edi] {Calculate and Return Result} pop edx pop ebp pop esi pop edi pop ebx sub eax, edx {Subtract Start Position} ret @@NotFound: pop edx {Dump Start Position} pop ebp pop esi pop edi @@InvalidInput: pop ebx xor eax, eax {No Match Found - Return 0} ret @@Remainder: {Check Last 1 to 4 Characters} mov eax, [esi-3] {Last 4 Characters of S - May include Length Bytes} xor eax, ecx {Zero Byte at each Matching Position} lea ebx, [eax-$01010101] not eax and eax, ebx and eax, $80808080 {Set Byte to $80 at each Match Position else $00} jz @@NotFound {No Match Possible} lea eax, [edx-4] {Check Valid Match Positions} cmp cl, [eax] lea edx, [eax+1] je @@Compare cmp edx, esi ja @@NotFound lea edx, [eax+2] cmp cl, [eax+1] je @@Compare cmp edx, esi ja @@NotFound lea edx, [eax+3] cmp cl, [eax+2] je @@Compare cmp edx, esi ja @@NotFound lea edx, [eax+4] jmp @@Compare @@Large: mov eax, [ebp-4] {Compare Last 4 Characters of S and SubStr} cmp eax, [edx-4] jne @@MainLoop {No Match on Last 4 Characters} mov ebx, edi @@CompareLoop: {Compare Remaining Characters} add ebx, 4 {Compare 4 Characters per Loop} jge @@SetResult {All Characters Matched} mov eax, [ebp+ebx-4] cmp eax, [edx+ebx-4] je @@CompareLoop {Match on Next 4 Characters} jmp @@MainLoop {No Match} End; Function DPPos(Const sSubStr, sString: String): Integer; Var i: Integer; c: Char; Begin Case Length(sSubStr) Of 0: Result := 0; 1: Result := CharPos_JOH_SSE2_1_b(sSubStr[1], sString); 2, 3: Result := Pos_JOH_IA32_6(sSubStr, sString); Else If Length(sString) < 1000 Then // 1000 is ne Hausnummer Result := Pos_JOH_IA32_6(sSubStr, sString) Else Result := QPosEx(sSubStr, sString,1); // Dann kann man auf das '(n<3) or' verzichten! End End; End. |
Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen
Leute, Ihr habt erstens gezeigt, das Delphi gut kompiliert, zweitens, das die Wahl des richtigen Algorithmus' entscheidend ist und drittens, das man doch immer wieder etwas herauskitzeln kann, wenn man Assembler verwendet.
Der QuickSearch-Algorithmus ist vom Verfahren her schnell, aber nicht notwendigerweise in der reellen Anwendung. Im echten Leben haben wir es auch mit kurzen Strings zu tun, wo so ein Pos ausreichend ist, da es kaum Overhead produziert. Erst bei langen Strings -wie schon erwähnt- spielt der Algorithmus seine Stärken aus. Der Trick ist -im Gegensatz zu meinen ursprünglichen Ausführungen-, das die Sprungtabelle anhand des NÄCHSTEN Zeichens errechnet wird. Und da kann man -wenn es denn nicht im SuchString vorkommt- ein Zeichen weiter springen, als z.B. beim BM. Was die Messmethoden anbelangt, denke ich, das Amateurprofis Idee sehr gut durchdacht ist, aber den Kern der Diskussion nicht trifft. Performancemessungen sind immer abhängig von den Testdaten ('Shit in, Shit out'). Und wenn man, wie AP, mit 'aaaaa' und 'ab' testet, dann wird ja ständig der optimierte Vergleich angewendet, ergo ist die Steigerung der Performance auch maximal. Ich habe es genau andersherum gemacht und den minimalen Geschwindigkeitszuwachs ermittelt. Und da der nun auch >0.0% ist, kann man sagen (und beweisen), das AP's-Algorithmus immer(!) besser als die Delphi-Variante ist. Der Ansatz, den Vergleich zu optimieren, ist schon sehr gut. Vielleicht solltet ihr bzw. Amateurprofi mal die Fastcode-Seiten bezüglich des besten CompareMem's durchsuchen und diese Lösung in den Code einfließen lassen. Dann ist vielleicht noch mehr rauszuholen. Ich würde vorschlagen, man einigt sich auf ein Einsatzgebiet (z.B. Tags in XML suchen, oder Wörter/Sätze in einem Text) und dann erstellt man repräsentative Testdaten und legt los. Dann kann man eine gesichterte Aussage für genau dieses Einsatzgebiet treffen. Für mich reicht es, zu wissen, das bei kurzen Suchstrings z.B. die FastCode-Routinen besser sind, aber bei längeren dann Sirius/Amateurprofis Varianten loslegen, insofern ist der Hybrid aus den drei Routinen wirklich (für mich) das non-plus-ultra. Ich habe eine inkrementelle Suche in Adressdaten (ca. 1.000.000 Adressen) und da ist so ein FastPos schon eine saugeile Verbesserung, denn derzeit hat man minimale Verzögerungen beim Tippen, insbesondere, wenn der Suchstring noch kurz ist. |
Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen
Moin,
Schöne Funktion habt ihr da gebaut, Respekt! Aber mal was ganze anderes: Ich denke aus dem Header Unit sollte in irgendeiner Weise hervorgehen, welche Lizenz benutzt wird, bzw. was man damit darf und was nicht (Denn ich denke zumindest des FastCode hat eine Lizenz)? Grüße, Max |
Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen
Zitat:
 Tut mir leid, dich enttäuschen zu müssen.Edit: Kannst du noch etwas anderes, als andere Leute zu kritisieren? |
Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen
Zitat:
Keine Einwände. Ich habe die Routinen für SearchFors mit Längen bis 6 Zeichen etwas optimiert und bin zur Zeit dabei die Routine für SearchFors mit größeren Längen noch etwas schneller zu machen. Last not least wird die nächste Version auch rückwärts suchen können. Und, du hast Recht, daß ich (sehr bewußt) den worst case getestet habe, also erstes und letztes Zeichen von SearchFor ist immer gleich und es muß ein CompareMem durchgeführt werden. In der Praxis ist das natürlich nicht so. Mal sehen, vielleicht schreibe ich auch noch eine AnsiPosEx-Version, die nicht case sensitiv ist. |
Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen
Zitat:
Zu "Tut mir leid, dich enttäuschen zu müssen" Ich bin nicht enttäuscht. Mir war schon klar, daß du unter "Takte" die von QPC gelieferten Werte meintest. Ich verwende dagegen den TimeStampCounter, der mit der CPU-Taktfrequenz tickt, was deutlich präzisere Messungen ermöglicht als GetTickCount oder QueryPerformanceCounter. zu "Kannst du noch etwas anderes, als andere Leute zu kritisieren?" Ja, kann ich. Merksatz : Wer Kritik nicht hören möchte, sollte sich so verhalten, daß Kritik nicht laut wird. Ich habe schlicht und einfach eine Routine veröffentlicht und Messwerte. Zudem habe ich auch erklärt, wie die Testbedingungen waren und zusätzlich auch daß Programm, daß die Messungen durchführt, veröffentlicht. Alles war also für jeden nachvollziehbar und vor allem auch reproduzierbar. Wenn dann von dir ein Kommentar kommt wie "Keine Ahnung, wo du deine Zahlen hernimmst", dann solltest du dich nicht wundern, wenn darauf etwas pissig reagiert wird. |
Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen
Zitat:
Timer1 wird (warum auch immer) weiterhin seit IBM's Massenverkauf mit seinen 18,2 IRQs pro Sekunde. |
Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen
Zitat:
Zitat:
FastCode-Seite empfehlen. Dort wurde auch ein besseres Comparemem entwickelt. |
Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen
Zitat:
Ja, das mag so sein. Das ändert aber nichts an der Richtigkeit meiner Aussage, daß der TSC deutlich schneller tickt, als QPC. qpc tickt (auf meinem Rechner) mit ca. 3.58 MTicks/s tsc tickt (auf meinem Rechner) mit ca. 2.65 GTicks/s, also 740 mal so schnell wie qpc
Delphi-Quellcode:
PROCEDURE TMain.Test;
var tick,tick1:cardinal; tsc,tsc1,qpc,qpc1:int64; FUNCTION TimeStamp:int64; asm rdtsc end; begin queryperformancecounter(qpc); tsc:=timestamp; tick:=GetTickCount; sleep(2000); tick1:=GetTickCount; tsc1:=timestamp; queryperformancecounter(qpc1); tick:=tick1-tick; tsc:=tsc1-tsc; qpc:=qpc1-qpc; ShowMessage('ticks '+IntToStr(tick)+#13+ 'qpc '+IntToStr(qpc)+' '+IntToStr(qpc*1000 div tick)+' ticks/s'#13+ 'tsc '+IntToStr(tsc)+' '+IntToStr(tsc*1000 div tick)+' ticks/s'); end; |
| Alle Zeitangaben in WEZ +1. Es ist jetzt 16:58 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-2025 by Thomas Breitkreuz