Delphi-PRAXiS - Delphi Schnellster Stringmatching-Algorithmus in ASM übersetzen

Delphi-PRAXiS (https://www.delphipraxis.net/forum.php)

- Object-Pascal / Delphi-Language (https://www.delphipraxis.net/32-object-pascal-delphi-language/)

- - Delphi Schnellster Stringmatching-Algorithmus in ASM übersetzen (https://www.delphipraxis.net/104534-schnellster-stringmatching-algorithmus-asm-uebersetzen.html)

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:

Zitat von Amateurprofi

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 ?

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:

Zitat von alzaimar

Ich finde 7% auch sehr gut und daher wird deine Version -mit deiner Erlaubnis- in meine Unit übernommen.

@alzaimar:
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:

Zitat von sirius

Zitat:

Zitat von Amateurprofi

Tut mir leid, dich enttäuschen zu müssen.
Edit: Kannst du noch etwas anderes, als andere Leute zu kritisieren?

@sirius:
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:

Zitat von Amateurprofi

Ich verwende dagegen den TimeStampCounter, der mit der CPU-Taktfrequenz tickt, was deutlich präzisere Messungen ermöglicht als GetTickCount oder QueryPerformanceCounter.

Der QPC greift intern bei einem vorhandenen TSC auf diesen zu (ausser es wird explizit verboten, u.a. durch den boot.ini switch /usepmtimer). Wenn kein TSC vorhanden ist wird versucht HW Timer2 zu nutzen, aber das ist nicht immer möglich. Von daher kann es sehr gut vorkommen, dass die Funktion false zurück gibt, wenn kein TSC auf der CPU vorhanden ist und der Timer2 benutzt wird.

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 von Amateurprofi

@alzaimar:
Keine Einwände.

Danke

Zitat:

Zitat von Amateurprofi

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.

Falls Du Denkanstöße brauchst, würde ich auch hier die

FastCode-Seite empfehlen. Dort wurde auch ein besseres Comparemem entwickelt.

Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen

Zitat:

Zitat von Muetze1

Zitat:

Zitat von Amateurprofi

Ich verwende dagegen den TimeStampCounter, der mit der CPU-Taktfrequenz tickt, was deutlich präzisere Messungen ermöglicht als GetTickCount oder QueryPerformanceCounter.

@Mütze1:
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;