AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Sprachen und Entwicklungsumgebungen Object-Pascal / Delphi-Language Delphi Schnellster Stringmatching-Algorithmus in ASM übersetzen

Schnellster Stringmatching-Algorithmus in ASM übersetzen

Offene Frage von "Sereby"
Ein Thema von alzaimar · begonnen am 5. Dez 2007 · letzter Beitrag vom 3. Jul 2008
Antwort Antwort
Seite 5 von 8   « Erste     345 67     Letzte » 
Amateurprofi

Registriert seit: 17. Nov 2005
Ort: Hamburg
1.076 Beiträge
 
Delphi XE2 Professional
 
#41

Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen

  Alt 8. Dez 2007, 17:58
@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.
Gruß, Klaus
Die Titanic wurde von Profis gebaut,
die Arche Noah von einem Amateur.
... Und dieser Beitrag vom Amateurprofi....
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

Registriert seit: 6. Mai 2005
Ort: Berlin
4.956 Beiträge
 
Delphi 2007 Enterprise
 
#42

Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen

  Alt 8. Dez 2007, 20:08
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.
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

Registriert seit: 6. Mai 2005
Ort: Berlin
4.956 Beiträge
 
Delphi 2007 Enterprise
 
#43

Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen

  Alt 8. Dez 2007, 20:55
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.
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
Prototypjack

Registriert seit: 2. Feb 2003
611 Beiträge
 
Delphi 2009 Professional
 
#44

Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen

  Alt 8. Dez 2007, 21:30
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
Max
„If you have any great suggestions, feel free to mail me, and I'll probably feel free to ignore you.“ . Linus Torvalds
  Mit Zitat antworten Zitat
Benutzerbild von sirius
sirius

Registriert seit: 3. Jan 2007
Ort: Dresden
3.443 Beiträge
 
Delphi 7 Enterprise
 
#45

Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen

  Alt 8. Dez 2007, 21:36
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?
Dieser Beitrag ist für Jugendliche unter 18 Jahren nicht geeignet.
  Mit Zitat antworten Zitat
Amateurprofi

Registriert seit: 17. Nov 2005
Ort: Hamburg
1.076 Beiträge
 
Delphi XE2 Professional
 
#46

Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen

  Alt 8. Dez 2007, 21:51
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.
Gruß, Klaus
Die Titanic wurde von Profis gebaut,
die Arche Noah von einem Amateur.
... Und dieser Beitrag vom Amateurprofi....
  Mit Zitat antworten Zitat
Amateurprofi

Registriert seit: 17. Nov 2005
Ort: Hamburg
1.076 Beiträge
 
Delphi XE2 Professional
 
#47

Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen

  Alt 8. Dez 2007, 22:17
Zitat von sirius:
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?
@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.
Gruß, Klaus
Die Titanic wurde von Profis gebaut,
die Arche Noah von einem Amateur.
... Und dieser Beitrag vom Amateurprofi....
  Mit Zitat antworten Zitat
Muetze1
(Gast)

n/a Beiträge
 
#48

Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen

  Alt 9. Dez 2007, 00:43
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.
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

Registriert seit: 6. Mai 2005
Ort: Berlin
4.956 Beiträge
 
Delphi 2007 Enterprise
 
#49

Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen

  Alt 9. Dez 2007, 11:20
Zitat von Amateurprofi:
@alzaimar:
Keine Einwände.
Danke
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.
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
Amateurprofi

Registriert seit: 17. Nov 2005
Ort: Hamburg
1.076 Beiträge
 
Delphi XE2 Professional
 
#50

Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen

  Alt 9. Dez 2007, 22:20
Zitat von Muetze1:
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.
@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;
Gruß, Klaus
Die Titanic wurde von Profis gebaut,
die Arche Noah von einem Amateur.
... Und dieser Beitrag vom Amateurprofi....
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 19:52 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz