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

Seite 2 von 2

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;

Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen

Hast du (falls du einen Dualcore/HT-Rechner hast) das Programm auch an eine CPU gebunden?

Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen

Zitat:

Zitat von Dax

Hast du (falls du einen Dualcore/HT-Rechner hast) das Programm auch an eine CPU gebunden?

@Dax:
Ich habe keinen DualCore Recher, aber ich bin mir der Problematik, die negaH in diesem

Beitrag beschrieben hat, bewußt.
Das Problem DualCore betrifft m.W. nicht nur den direkten Zugriff auf den TSC ( mit RDTSC ) sondern auch QPC.
Wer also Performancemessungen mit hoher Präzision auf DualCore-Rechnern durchführen will, muß sich Gedanken machen, wie er das Problem löst.
(Warum bei DualCore/QuadCore-Rechnern kein "globaler" TSC verfügbar ist, ist mir schleierhaft)

Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen

Zitat:

Zitat von Amateurprofi

(Warum bei DualCore/QuadCore-Rechnern kein "globaler" TSC verfügbar ist, ist mir schleierhaft)

Wie du selber wohl weisst, wird der TSC mit jedem Takt um eins erhöht. Durch diesen Fakt wird der TSC gerne genutzt, um die Taktrate des Kerns zu ermitteln. Und bei einem Quad- bzw. DualCore kann jeder Kern mit einem eigenen Takt betrieben werden bzw. zum energiesparen herunter getaktet werden. Welcher Takt zählt denn nun bei einem globalen TSC? Der TSC ist bisher in den Cores und somit tritt überhaupt das Problem auf. Deine Lösung/Vorschlag ist auch nicht 100%ig umsetzbar bzw. nachvollziehbar.

Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen

Zitat:

Zitat von Muetze1

Zitat:

Zitat von Amateurprofi

(Warum bei DualCore/QuadCore-Rechnern kein "globaler" TSC verfügbar ist, ist mir schleierhaft)

Ja, da bin ich wohl zu kurz gehopst, über die variable Taktrate der einzelnen Kerne habe ich nicht nachgedacht.

Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen

Allerdings muß man dazu sagen, das sich die Problematik mit den verschiedenen TSC in den Cores eigentlich nicht mehr stellt. Zum einen gibt es von M$ bereits einen Fix zu diesem Thema (damals flippten verschiedene Games eben wegen dieser doppelten TSC's aus) - ich hab das nicht analysiert, mich würde es aber nicht wundern, wenn M$ die API-Routinen für QPC auf Core 0 (der immer existiert) lenkt.

Zum zweiten kann man auch dafür sorgen, das das Meßprogramm nur auf einem Core läuft.

@amateurprofi: Die Routine "test2" zum Beweis der differenz zwischen QPC und TSC würde ich nochmal genauer beäugen. Bei der QPC-Messung mißt du sämtlichen Laufzeit-Overhead von GetTickCount z.B. mit. Kein Wunder, das sich hier Differenzen auftun. Besser wäre:

Delphi-Quellcode:

			   queryperformancecounter(qpc);

   sleep(2000);

   queryperformancecounter(qpc1);

Und dies für die anderen Meßmethoden genauso.

Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen

Zitat:

Zitat von OlafSt

@amateurprofi: Die Routine "test2" zum Beweis der differenz zwischen QPC und TSC würde ich nochmal genauer beäugen. Bei der QPC-Messung mißt du sämtlichen Laufzeit-Overhead von GetTickCount z.B. mit. Kein Wunder, das sich hier Differenzen auftun. Besser wäre:

Delphi-Quellcode:

			   queryperformancecounter(qpc);

   sleep(2000);

   queryperformancecounter(qpc1);

Und dies für die anderen Meßmethoden genauso.

@OlafSt:
Welche Unterschiede würdest du denn da erwarten ?
Hast du das denn mal ausprobiert ?

Der "sämtliche Laufzeit-Overhead von GetTickCount" beträgt ganze 12 CPU-Ticks.
Glaubst du enrsthaft, diese 12 Ticks verfälschen die Differenz wenn QPC im MHz-Bereich und TSC im GHz-Bereich tickt.
Ich würde das noch mal genauer beäugen (deine Worte)......

Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen

Delphi-Quellcode:

			   queryperformancecounter(qpc);

   tsc:=timestamp;

   tick:=GetTickCount;

   sleep(2000);

   queryperformancecounter(qpc1); 

   tsc1:=timestamp;

   tick1:=GetTickCount;

so wäre es besser. Der Meßfehler von GetTickCount(), TimeStamp und QPC nivelliert sich so ein bischen, relativ zueinander gesehen.
Einzelmessungen der art

Delphi-Quellcode:

			   queryperformancecounter(qpc);

   sleep(2000);

   queryperformancecounter(qpc1); 

   tsc:=timestamp;

   sleep(2000);

   tsc1:=timestamp;

   tick:=GetTickCount;

   sleep(2000);

   tick1:=GetTickCount;

wären dagegen falsch. Der Aufrufoverhead jeder Funktion verursacht einen wesentlich kleineren Meßfehler als das Sleep(2000). Dieses kann +-20ms bedeuten.

Noch besser ist es so:

Delphi-Quellcode:

			   sleep(0);

   queryperformancecounter(qpc);

   tsc:=timestamp;

   tick:=GetTickCount;

   sleep(2000);

   queryperformancecounter(qpc1); 

   tsc1:=timestamp;

   tick1:=GetTickCount;

Das Sleep(0) "erzwingt" einen anstehenden Task/Threadswitch und so reduziert sich die Wahrscheinlichkeit drastisch das innerhalb den nachfolgenden drei Funktionsaufrufen dieser anstehende Switch durchgeführt wird. Dieser würde dann dafür sorgen das die Messung komplett untauglich ist.

Gruß Hagen

Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen

@negaH:

Hagen, jetzt auch noch du ?

Es ging nicht darum, zu prüfen, ob der TSC einige Ticks/s mehr bringt als der QPC sondern er ging darum, aufzuzeigen, daß QPC im einstelligen MegaHertz-Bereich tickt, TSC aber im einstelligen GigaHertz Bereich.
In diesem Zusammenhang ist die Anordung völlig irrelevant.
Und glaube mir, ich habe mir schon Gedanken gemacht, in welcher Reihenfolge ich die verschiedenen Counter aufrufe.
Was bewirkt meine Anordung ?!
1) Für QPC wird das Ergebnis etwas begünstigt.
2) TSC (mein Kandidat) wird etwas benachteiligt.
Genau diese unsinnige Diskussion, die jetzt aufkam, wollte ich damit vermeiden......

Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen

Naja, das kannst du einfacher haben, einfach QueryPerformanceFrequency() aufrufen und in einer MessageBox anzeigen, zb. in MHz. Dann aus der Registry die Taktfrequenz der Cores auslesen und ebenfalls anzeigen. Der QPC sollte um die 3.6MHz anzeigen, so wars bei mir bisher.

Allerdings, und das ist entscheidend, sagt dies nichts darüber aus woher der QPC seine Zeitbasis nimmt. Es könnte auch der Timestamp sein den das OS runterskaliert auf 3.6Mhz.
Auf meinem Laptop läuft der TSC im Verhältnis synchon zum QPC, und das auch wenn ich per APC die Prozessoren manuell verlangsamme. Ergo: QPC bezieht seine Timebasis aus dem Timestamp und wird skaliert.

Hm :) und nun fragt sich welche der beiden Diskussionen ist flüssiger als Luft ?
Ich wollte nur aufzeigen wie man die besten Meßresultate erreicht unabhängig davon was man damit später macht :)

Gruß Hagen

Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen

ich will auch ... ich will auch ...

Bei mir läuft der TSC ja mit'm Prozessortakt und was dabei ganz nett ist ...
mein Prozessor ist dynamisch getacktet (hohe CPU-Auslastung = hohe Taktfrequenz und niedrige CPU-Auslastung = kleine Taktfrequenz).

Und jetzt rate mal was der TSC da für einen "Mist" messen kann, wenn sich die TSC-Frequenz ständig ändert. :zwinker:

[add]
Ach ja und noch mehr Spaß hast du auf Multiprozessorsystemen.
Standardmäßig legst du ja nicht fest auf welchem Prozessor dein Programm laufen soll, also kann es sein daß der Startwert auf Einer und der Endwert auf einer anderen CPU gemessen wird.

Jede CPU hat ja (war doch so?) ihren eigenen TSC und somit ihre eigene Zeit.

Es könnte also sozusagen passieren das die Differenz aus zwei verschiedenen Uhren errechnet wird.

Code:

			Start = Uhrzeit_in_Deutschland

5 Minuten Warten

Dauer = Uhrzeit_in_Japan - Uhrzeit_in_Deutschland

Dauer wird da bestimmt nichtmal annähernd 5 Minuten ergeben

Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen

Hallo,

doch geht, siehe

http://www.fastcodeproject.org/

Allein das Schreiben in Assembler bringt aber noch keinen Vorteil.
Mit Assembler kann ich auch langsamen Code schreiben.
NOP, NOP, NOP. ;)

Heiko

Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen

Zitat:

Ich habe hier einen wirklich schnellen Stringmatching-Algorithmus (also, sowas wie 'POS'), der aber wesentlich schneller als POS ist (2-20x).

alllsooo :-)

bevor man mit ASM optimiert, von dem ich sowieso keine Ahnung habe *grien* .. muss man sich erst einmal fragen, was man tun möchte, damit man nicht auf eine falsche Fährte gelockt wird.

Ein Bayer Moore Algorithmus hat ja immer noch die Laufzeit O(m/n).
m ist die Länge des zu durchsuchenden Textes und n die Länge des Suchstrings. Die Laufzeit wird also besser, je länger der zu suchende String ist.
Eine Laufzeit O(m) zum Beispiel wäre ja eine lineare Abhängigkeit der Laufzeit vom zu durchsuchendem Text. (Wenn der Text doppelt so lang wird, brauch ich doppelt so lange Zeit zum Suchen)
Wenn also m=n wäre und der Suchtext gleich lang dem zu durchzuchendem Text, dann hättest Du eine Laufzeit von O(1) .. egal wie lang der Text wäre, der Algorithmus wäre gleich schnell (weil Du wahrscheinlich nur das erste und letzte Zeichen vergleichen könntest)

Der Bayer Moor Algorithmus wäre also bei Aufgaben interessant, wenn man die gesamte Festplatte unindiziert nach Vorkommen eines bestimmten Wortes durchsucht.
Das macht Windows irgendwie in annehmbarer Zeit, naja ... geht so :-). Jetzt wäre also die Frage, wie oft will und braucht man das ...
Vor allen Dingen, weil in der realen Umsetzung bei Deiner explode Funktion der Algorithmus gar nicht das wahre Nadelöhr ist, sondern die häufigen String-Kopien..

http://www.delphipraxis.net/internal...=849704#849704

Wenn man eine einfache Suche mit Deiner Explode Funktion intelligent programmiert und noch etwas umgeschrieben in die eigene Klasse bastelt, hat man die Daten in der doppelten Geschwindigkeit verarbeitet, wie man braucht, um sie nur roh von der Festplatte zu lesen. (lesen von CSV Dateien)
750 ms als Beispiel um 100 MB Daten von der Festplatte zu lesen, und weitere 750 ms um sie auseinander zu dividieren.

Ich finde, dafür ist es nicht wert, den Algorithmus noch stark auf ASM zu optimieren. Gut, dann würen man irgendwann fast mit Festplattengeschwindigkeit. hmmm .. na gut, mir fällt dazu im Moment kein Anwendungsfall ein.

Ich denke, viel interessanter ist die Frage, wie durchsucht man einen relativ festen Datenbestand oder einen langen String, nach immer wieder anderen Texten. (Dictionary) (Typischer Anwendungsfall wäre die Suchmaschine Google. Die Zeit für eine Suche ist ja nicht abhängig von der Größe des Internets, also KEINE Laufzeit O(m) sondern nur abhängig von der Länge des Suchbegriffs (also O(n) )
Oder man will alle Vorkommen von Gensequenzen in einem ewig langem String durchsuchen ...

Und dafür gibts sehr moderne Algorithmen, wie Suffix-trees .. oder besser Suffix-Arrays, die zwar ein klein wenig langsamer sind als die Trees, aber dafür nicht soviel Speicher verbraten (bei intelligenter PRogrammierung stehen die Arrays den Trees sogar in nix nach)
Außerdem kann man so einen Suffixarray auf der Festplatte speichern, so einen Baum muss man immer neu aufbauchen.
(eine SuffixArray implementierung in Delphi hab ich leider nicht)

Ich hatte mir mal vor einiger Zeit einen SuffixTree von einem C-Quelltext umgeschrieben. wir könnten das ja mal vergleichen, im direkten Vergleich. Wenn Du Lust hast, können wir uns mal kurzschließen :-)
Aufgabe also: Wie durchsuche ich einen Datenbestand auf alle Vorkommen eines Subtextes, möglichst schnell ... (mit Indizierung)
Nur, wenn Du das für Deinen Anwendungsfall benötigst ...

Gruß stoxx

Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen

Zitat:

Zitat von stoxx

Ein Bayer Moore Algorithmus hat ja immer noch die Laufzeit O(m/n).

Also erstens heißt das Boyer-Moore, und zweitens hat das Ding im Mittel ne Laufzeit von O(log(n)/n * m) (log zur Basis der Alphabetgröße, aber das ist ja egal). Im Worst-Case ist die Laufzeit O(m*n) bzw. O(m), je nachdem welche Boyer-Moore-Variante man nun genau nimmt (Wikipedia nicht fragen, da steht teilweise Stuss.) O(1), wenn m=n ist, ist auch Quatsch - wenn das Muster gleich dem Text ist, muss man das ja überprüfen, man hat also m Schritte im Worst-Case, einen im Best-Case, also O(m) im Mittel. ;-)

Ich habe nicht den ganzen Thread gelesen, aber der Algorithmus ganz oben sieht sehr nach Quicksearch (von Sunday) aus, eine Variante von Boyer-Moore-Horspool. Diese beiden Algorithmen sind in vielen Anwendungsgebieten die schnellsten bekannten Algorithmen (ja, schneller als der Standard-Boyer-Moore!). Zumindest für den Fall, dass man den zu durchsuchenden Text nicht aufbereitet, sondern nur das Suchmuster, aber das ist ja ne ganz andere Herangehensweise.

Für kleine Alphabete (z.B. für eine Suche in DNS-Sequenzen) eignen sich dann allerdings andere Algorithmen besser. Da wären die Faktor-basierten Algorithmen (die auch mit Suffix-Trees arbeiten) besser, oder die sogenannten Faktor-Orakel, die so um 2001 das "erfunden" wurden.

Ansonsten ist der Algorithmus im ersten Beitrag sehr zu empfehlen, und eine Optimierung halte ich im Gegnsatz zu meinem Vorredner für durchaus sinnvoll. :-D

Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen

Zitat:

Zitat von Gausi

Zitat:

Zitat von stoxx

Ein Bayer Moore Algorithmus hat ja immer noch die Laufzeit O(m/n).

hehe .. danke, Du hast Recht mit der Laufzeit O(1) ... war zu kurz nachgedacht.
In der realen Anwendung hats mir halt nix gebracht,.... Wenn es mich sehr viel Zeit kostet,die Daten irgendwo herzubekommen, wie sie dann zu durchsuchen .. (mit dem einfachsten suchalgorithmus beim linearen durchgehen mit einer simplen Pascal Schleife ... hmmm .. dann kann ich höchstens den Faktor 2 sparen. Weil die Daten muss ich ja noch irgendwo beschaffen.
Wenn ich dann noch einmal zuviel kopiere, dann wird noch langsamer ( guck Dir mal die Explode Implementierung an)
und da kann der Algorithmus gar nix mehr machen. Da dauerts einfach drei oder viermal so lange. Nur weil man ihn schlecht umgesetzt hat.
Naja ... waren nur die praktischen Erfahrungen.
Die Theorie eines Algorithmus muss nicht unbedingt in der Praxis zutreffen. Suffix Arrays sind per Definition laut mathematik langsamer als Suffix-Trees. Dennoch gibt es C-implementationen die genauso schnell sind, wie ein Tree ..
So ist das eben :)

Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen

Ich hab ja auch nicht von der Theorie gesprochen, sondern von der Praxis. ;-) In der Theorie ist Knuth-Morris-Pratt super, weil er ne lineare Worst-Case-Laufzeit hat. Praktisch nutzbar ist er nicht. Boyer-Moore kann man prima analysieren, aber wenn man davon den Teil weglässt, der dafür sorgt, dass die Laufzeit auch im Worst-Case linear wird (und nicht n*m), dann wirds in der Praxis fast doppelt so schnell.

Mal ein paar Beispiel-Zeiten von meinen aktuellen Tests, einfache Implementierungen ohne besondere Optimierung (Textlänge: 1MB, Alphabetgröße: 25, Musterlänge: 100 Zeichen, Zufallstexte/-Muster):

Naiver Algorithmus (nicht pos, sondern was selbstgebautes): 4ms
Knuth-Morris-Pratt (standard/verbessert): 5,3ms/3,5ms
Boyer-Moore (standard/verbessert): 520µs/321µs
Quicksearch (das Dingen hier): 318µs
Boyer-Moore-Horspool: 299µs

Die "verbesserten" Varianten setzen die Ideen zu "schnellen Implementierung" aus den entsprechenden Original-Artikeln um. In der Regel sind die letzten drei fast gleichwertig, aber sehr häufig hat der letzte die Nase ein paar µs vorne. Wenn das Nadelöhr allerdings eh woanders liegt, ist das natürlich alles wurscht. :stupid:

Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen

In meinen Tests hat der Horspool schlechter abgeschnitten als Quicksearch. Vielleicht zeigst du mal deine Version, meine Tests beruhten auf den Implementierungen von

Charras & Lecroq.

Einen sehr interessanten Ansatz habe ich

hier entdeckt. Er basiert auf Sundays Arbeit, kann jedoch die Anzahl der Vergleiche halbieren. Leider ist er in der Praxis bei meinen Tests langsamer, was wohl an dem Overhead der indirekten Indizierung liegt. Ein Paradebeispiel, das theoretische Überlegungen nicht immer das Maß aller Dinge ist.

Noch etwas zu Tries, DAWGs etc. Das sind wahre Performancewunder, aber leider verbraten sie so dermaßen viel Speicher, das sie sich in der Praxis nicht zum Suchen in langen Texten eignen. Als Wörterbuch sind sie dagegen wirklich 'kinky'.

Hab ich erwähnt, das ich den QSearch für eine sehr schnelle Adresssuche verwende? Wir haben ca. 500.000 Kundenadressen, und die Disponenten kenn manchmal nicht den vollständigen Kundennamen, sondern nur Teile, oder Straße etc. Mit Quicksearch kann ich eine 'while-you-type' Suche in Echtzeit durchführen. Der Disponent tippt also 'Kassu' ein, das Teil findet 'Dipl. Ing. Kassupke' ,'Die Kassupke Company' etc.

Die gewünschte (und mit FastCode.org erreichte) teilweise drastische Verbesserung hat nur sportliche Aspekte, weil man den Unterschied in meinem Anwendungsfall eh nicht merkt.

Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen

Ich habe den Horspool "ausgerollt". Kann man auch bei Boyer-Moore selbst anwenden, dadurch wird BM in eingen Fällen doppelt so schnell. Der Trick ist, einge Dinge auszulagern. Dafür ändert man das Bad-Character-Array für das letzte Zeichen des Musters ab und kann so in einer "schnellen Schleife" das Muster rüberschieben, bis mal ein passendes Zeichen gefunden wurde. dann geht man aus der schnellen Schleife raus und fängt mit der Überprüfung an.
Dieser Trick funktioniert bei Quicksearch allerdings nicht ;-).

Delphi-Quellcode:

			function PreProcess_BMH_BC(p: String): TBC_IntArray;

var i, m: Integer;

    c: Char;

begin

  m := Length(p);

  for c := low(Char) to High(Char) do

    result[c] := m;

  for i := 1 to m-1 do     

    result[p[i]] := m-i;

end;

// Suche mit Horspool, direkt die unrolled-Variante. Sehr ähnlich zu BM_Unrolled

function Search_BMH_Unrolled(t,p: String): Integer;

var m, n, k, j: Integer;

    BC: TBC_IntArray;

    BC_last: Integer;

    Large: Integer;

begin

  m := Length(p);

  n := Length(t);

  Large := m + n + 1;

  BC := PreProcess_BMH_BC(p);

  // "echten" BC-Shift merken

  BC_last := BC[p[m]];

  // BC(lastCh) mit "Large" überschreiben

  BC[p[m]] := Large;

  k := m;

  result := 0;

  while k <= n do

  begin

      //fast loop

      repeat

        k := k + BC[t[k]];

      until k > n;

      //undo

      if k <= Large then

        //Muster nicht gefunden

        break

      else

        k := k - Large;

      j := 1;

      // slow loop

      while (j < m) and (p[m-j] = t[k-j]) do

        inc(j);

      if j=m then

      begin

        // Muster gefunden

        result := k - j + 1;

        k := k + m; //oder: k+1, oder: break; je nachdem, wie man den Text komplett durchsucht haben will

      end else

      begin

          // Muster verschieben

          if t[k] = p[m] then

            k := k + BC_last    // Hier dann den original-Wert nehmen

          else

            k := k + BC[t[k]];

      end;

  end;

end;

Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen

Zitat:

Noch etwas zu Tries, DAWGs etc. Das sind wahre Performancewunder, aber leider verbraten sie so dermaßen viel Speicher, das sie sich in der Praxis nicht zum Suchen in langen Texten eignen. Als Wörterbuch sind sie dagegen wirklich 'kinky'.

nur zur Info: Suffixarrays brauchen genauso viel Platz, wie die Original Daten selber. Die Daten werden nur geschickt umsortiert. und sind (fast) genauso schnell, wie Suffixtrees ...

Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen

Tut mir leid das alte Thema aus der Versenkung holen zu müssen.
Aber als ich gestern auf da Thema gestoßen bin war ich erstmal begeistert doch heute, als ichs in meinem projekt getestet habe, dann doch etwas enttäuscht denn:

Durch die Funktion "CharPos_JOH_SSE2_1_b" wird irgendwie das Memory Management durcheinandergebracht oder wie auch immer. Denn sobald diese Funktion mit-compiliert wird bekomme ich an einer völlig anderen stelle, die überhaupt nicht mit diesem Pos zu tun hat (beim auslesen eines Streams mit (TMemoryStream).Read), eine "Invalid floating Point Value" Fehlermeldung beim versuch etwa 800kb zu lesen.

Aber erst beim 2. Versuch eine etwas größere Datei zu lesen.
1. Datei ~ 30kb -> liest er anscheinend Problemlos.
2. Datei danach ~ 850KB -> Bums.... Fehlermeldung bei Read!

Wenn die "CharPos_JOH_SSE2_1_b" Funktion nicht mit-compiliert wird funktioniert alles Problemlos!

Zusatzinfo: ich verwende auch die neueste Version von FastMM4

Wer weiss woran es liegt oder ne Ahnung hat: bitte sagts mir :-)

Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen

Das Einzige, was sein könnte, ist die Verwendung spezieller ASM-Befehle. Ich hab die Routine vom den FastCode-Projekt (

www.FastCode.Org). Dort gibt es auche reine Pascal-Routine, die diesbezüglich keine Probleme machen sollte.

Kompiliere das Ganze mal mit 'RangeCheck' und 'Overflowcheck' on (Bereichs- und Überlaufprüfung). Vielleicht ist ja noch ein Korken im Code.

edit: Der genannte Link ist tot, der hier aber nicht

www.fastcodeproject.org

Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen

www.FastCode.Org existiert nichtmehr :/

und ich hab die beiden optionen eingeschaltet im projekt allerdings knallt das genauso wie vorher ohne ne andere meldung. Was sollte da denn passieren?

Ahja wenn ich Set8087CW($133F); benutze, dann knallts nicht aber der anfang (XML datei) ist dann zerschossen mit #0 und € und so

Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen

Zitat:

Nur um dieses kleine Detail richtig zu stellen, DAWGs also Suffix/prefixtries, sind für Wörterbücher konstruiert und im Gegensatz zu allgmeinen Annahme sind es auch fast perfekte Komprimierungen (sprich sie entfernen Redundanzen in den Wörterebücher besser als viele herkömliche Komprimierungsalgo.) Kurz: die Aussage das sie viel Speicher verbraten gilt nicht generell. DWAGs zb. speichern Wörterbücher so kompakt das manche Zipper verblassen. Und dabei meine ich die real im Speicher liegende Datenstruktur. Eine Wortdatenbank mit 200.000 deutschen Wörtern verbraucht 6 Mb und 800kB als DAWG im Speicher.

Allerdings sollte man nicht Äpfel mit Birnen vergleichen, heist die Zielsetzungen von Tries/DWAGs ist nicht das schnelle Aufsuchen von Phrasen in vorher unbekannten und nicht preprozessierten Texten.

Ich habe aber auch DWAGs für schnelle pseuoparallele Textsuchen, bei denen eine kleine Datenbank von Wörtern per DAWG gespeichert wurde, umgesetzt. Diese Suchmethode dürfte im Vergleich zu den oben besprochenen Verfahren wesentlich effizienter sein, heist um mehrfaches schneller. Aber! das Ziel hat sich abei geändert, nämlich das Durchsuchen von sehr vielen Textdokumenten (Streambasiert) nach sehr vielen Suchbegriffen in parallel, quasi ein Scanner. Wenn man zb. 1000 Schlagworte innerhalb mehrer textbasierter TCP/IP Streams online suchen möchte dann sind solche Verfahren wie Boyer-Moore etc.pp. schlicht ineffizient. Man kann aber DWAGs so umbauen das sie diese 1000 Wörter als Datenbank effizient speichern und dann in parallel damit mehrere Textstreams scannen. Rechnet man das um, in normale Textdateien mit Größe X mal Anzahl Y an Suchbegriffen und vergleicht die sich ergebenende Gesamtkomplexität eines solchen DAWG-basierten Scanners mit einem auf Boyer-Moore Verfahren das ebenfalls nach diesen Schlagwörtern suchen soll, dann habe ich die Erfahrung gemacht das das DWAG weit besser ist. Eine zweite interssante Anwednung dieses Scanners ist es das er kombinatorische online Suchen durchführen kann. Dh. die Wortdatenbank dient als Referenz der Suchworte aber während der Suche können auch effizient Rekombinationen dieser Suchworte (selbst Buchstaben-Permutationen innerhalb der Suchwörter) im Text gefunden werden. Ok, das sind jetzt aber wirklich Äpfel im Vergleich zu Birnen (Boyer-Moore etc.pp :) )

Es hängt also, wie bei jedem hochspezialisierten informationstechnischen Verfahren, ganz entscheidend von den Rahmenbedingungen und Zielsetzungen ab.

Gruß Hagen

Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen

Hi Hagen, danke für die Ausführungen. Dann werde ich meine Kentnisse über DAWGs nochmal auffrischen. Insbesondere die kompakten Datenstrukturen hatte ich in den Implementierungen bisher vergeblich gesucht. Muss aber zugeben, zu schnell aufgegeben zu haben.

Ich dachte immer, die Verkettung pro Buchstabe sei so speicheraufwändig.

Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen

Ja das stimmt ja auch ;) Aber durch die Entfernung der Suffixe/Prefixe spart man das wieder enorm ein. Hängt natürlich vom Inhalt des Wörterbuches selber ab.
Bei meinem DWAG (kannste bei Luckie downloaden) benutze ich 4 Bytes pro Buchstaben und auf dieses treffen auch die 6Mb -> 800Kb -> 200000 deutsche Wörter zu.
Zudem gilt bei Gleichverteilung von 2000000 Wörtern und 26 Buchstaben also pro Buchstabe 7600 Wörter beginnen, 26 Nodes für den Anfangsbuchstaben von 200000 Wörtern. Also für die Basenode "A" sind 7600 Wörter untergeordnet, für 4 Bytes in meinem DWAG also 7600 Worte. Danach wieder 1/26'tel pro Subnode = 290 wörter, dann wieder 1/26'tel pro Subsubnode = 11 Wörter usw. Diese Rechnung ist aber der Worstcase, also wenn die 7600 alle Kombinationen aller Buchstaben enthielten, was aber fern der Realität eines Wörterbuches ist.

Gruß hagen

Seite 2 von 2