Anzahl eines Zeichens im String ermitteln

[KodeZwerg]

Zitat von Harry Stahl:

Denn wenn man an einer Funktion evtl. selber noch was rumschrauben wollte, müsste man...

...in der ComboBox "Run All Tests" sich auf den einen veränderten Festlegen oder selbst alles umschreiben.

Sorry, nach Uwe's Text kann ich gerade nicht daran weiterwerkeln, das wäre vergebene müh. Ich mag ja gerne Kritik annehmen aber umsetzen ohne Zusatz-Komponenten.
Wie es jetzt gerade ist dachte ich eigentlich ist es okay für synthetische und praktische Wertungen.
Da habe ich mir wohl was vorgemacht.

Seis drum, Source ist vorhanden, macht damit was ihr wollt.

Ich würde zu guter Letzt gerne noch Erfahren ob denn meine Berechnung der Avg-Variable korrekt ist oder auch gänzlich falsch?

[jbg]

So und jetzt eine Variante mit SIMD (SSE2, benötigt mindestens Nehalem Prozessorarchitektur von 2008). Sie ist mit Delphi 2009 kompilierbar und dürfte alle bisherigen Funktion "wegblasen".

Zitat:

00000 Calibrate
03279 1234588 miep
05454 Ydobon
02642 marabu
03377 Missionar
03252 alzaimar
02661 Uwe Raabe StringCountChar
02635 Uwe Raabe StringCountCharFor
02346 KodeZwerg CountCharInString
06970 KodeZwerg CharInStringA
03529 Neutral General CharCountAsm
01779 Andreas Hausladen CountCharAsm
00515 Andreas Hausladen CountCharAsmSIMD
01953 Uwe Raabe CharCount
02713 Egon Hugeist CharCount_1
03261 Egon Hugeist CharCount_2
02640 Egon Hugeist CharCount_Double_Sided_3
02695 Egon Hugeist CharCount_Double_Sided_4
03328 Delphi CountChar

Delphi-Quellcode:

function AH_CountCharAsmSIMD(const Str: String; c: Char): Cardinal;
asm
{$IFNDEF CPUX64}
  test eax, eax
  jz @@Empty       // wenn S = '' then gibt es nichts zu tun

  push ebx
  push esi
  mov esi, eax
  xor eax, eax // Rückgabewert auf 0 setzen

  // Stringlänge ermitteln
  //mov ecx, DWORD PTR [esi-skew].StrRec.Length
  mov ecx, DWORD PTR [esi-$04]
  shl ecx, 1 // Auf Byte-Offsets umrechnen
  lea esi, [esi+ecx] // ESI so umrechnen, dass ESI+ECX auf das String-Ende zeigen
  neg ecx
  cmp ecx, -8
  ja @@SingleChars

  // DX in XMM0 als DX:DX:DX:DX:DX:DX:DX:DX verteilen
  movd xmm0, edx
  pshuflw xmm0, xmm0, 0
  pshufd xmm0, xmm0, 0

  // Offset so ändern, damit nicht über das String-Ende hinauslesen gelesen wird
  add ecx, 16
  jc @@RemainingChars
  sub esi, 16

  nop // Alignment
  // 8 Zeichen auf einmal verarbeiten
@@Loop8WideChars:
  movdqu xmm1, [esi+ecx] // 16 Bytes (8 Zeichen) laden
  pcmpeqw xmm1, xmm0 // Vergleichen. in XMM1 steht danach für jedes gefundene Zeichen $FFFF an der WORD Position
  pmovmskb ebx, xmm1 // Das oberste Bit jedes Bytes in XMM1 in EBX als Bit-Maske übertragen
  popcnt ebx, ebx // Anzahl der Bits ermitteln (CPU muss POPCNT unterstützen, Nehalem von 2008)
  shr ebx, 1 // Da PMOVMSKB auf Bytes anstatt auf WORDs arbeitet, haben wir doppelt so viele Bits => div 2
  add eax, ebx

  add ecx, 16
  jz @@Leave
  jnc @@Loop8WideChars

  // Offset für den Einzelzeichen-Vergleich wiederherstellen
  add esi, 16
@@RemainingChars:
  sub ecx, 16
  cmp ecx, -8
  ja @@SingleChars

  // 4 Zeichen auf einmal verarbeiten
  movq xmm1, QWORD PTR [esi+ecx] // 8 Bytes (4 Zeichen) laden
  pcmpeqw xmm1, xmm0 // Vergleichen. In XMM1 steht danach für jedes gefundene Zeichen $FFFF an der WORD Position
  pmovmskb ebx, xmm1 // Das oberste Bit jedes Bytes in XMM1 in EBX als Bit-Maske übertragen
  movzx ebx, bl // Nur die unteren 8 Bits sind korrekt befüllt alle anderen auf 0 setzen
  popcnt bx, bx // Anzahl der Bits ermitteln (CPU muss POPCNT unterstützen, Nehalem von 2008)
  shr ebx, 1 // Da PMOVMSKB auf Bytes anstatt auf WORDs arbeitet, haben wir doppelt so viele Bits => div 2
  add eax, ebx

  add ecx, 8
  jz @@Leave

  nop
@@SingleChars:
  xor ebx, ebx
@@Loop:
  cmp WORD PTR [esi+ecx], dx
  sete bl
  add eax, ebx
  add ecx, 2
  jnz @@Loop

@@Leave:
  pop esi
  pop ebx
@@Empty:
{$ELSE}
  xor rax, rax // Rückgabewert auf 0 setzen

  test rcx, rcx
  jz @@Leave       // wenn S = '' then gibt es nichts zu tun

  mov r8, rcx

  // Stringlänge ermitteln
  //movsxd r9, DWORD PTR [r8-skew].StrRec.Length
  movsxd r9, DWORD PTR [r8-$04]
  shl r9, 1  // Auf Byte-Offsets umrechnen
  lea r8, [r8+r9]  // E8 so umrechnen, dass R8+R9 auf das String-Ende zeigen
  neg r9
  cmp r9, -8
  ja @@SingleChars

  // DX in XMM0 als DX:DX:DX:DX:DX:DX:DX:DX verteilen
  movd xmm0, edx
  pshuflw xmm0, xmm0, 0
  pshufd xmm0, xmm0, 0

  // Offset so ändern, damit nicht über das String-Ende hinauslesen gelesen wird
  add r9, 16
  jc @@RemainingChars
  sub r8, 16

  nop; nop // alignment
  // 8 Zeichen auf einmal verarbeiten
@@Loop8WideChars:
  movdqu xmm1, [r8+r9] // 16 Bytes (8 Zeichen) laden
  pcmpeqw xmm1, xmm0 // Vergleichen. In XMM1 steht danach für jedes gefundene Zeichen $FFFF an der WORD Position
  pmovmskb ecx, xmm1 // Das oberste Bit jedes Bytes in XMM1 in ECX als Bit-Maske übertragen
  popcnt ecx, ecx // Anzahl der Bits ermitteln (CPU muss POPCNT unterstützen, Nehalem von 2008)
  shr ecx, 1 // Da PMOVMSKB auf Bytes anstatt auf WORDs arbeitet, haben wir doppelt so viele Bits => div 2
  add eax, ecx

  add r9, 16
  jz @@Leave
  jnc @@Loop8WideChars

  // Offset für den Einzelzeichen-Vergleich wiederherstellen
  add r8, 16
@@RemainingChars:
  sub r9, 16
  cmp r9, -8
  ja @@SingleChars

  // 4 Zeichen auf einmal verarbeiten
  movq xmm1, QWORD PTR [r8+r9] // 8 Bytes (4 Zeichen) laden
  pcmpeqw xmm1, xmm0 // Vergleichen. in XMM1 steht danach für jedes gefundene Zeichen $FFFF an der WORD Position
  pmovmskb ecx, xmm1 // Das oberste Bit jedes Bytes in XMM1 in ECX als Bit-Maske übertragen
  movzx ecx, cl // Nur die unteren 8 Bits sind korrekt befüllt alle anderen auf 0 setzen
  popcnt cx, cx // Anzahl der Bits ermitteln (CPU muss POPCNT unterstützen, Nehalem von 2008)
  shr ecx, 1 // Da PMOVMSKB auf Bytes anstatt auf WORDs arbeitet, haben wir doppelt so viele Bits => div 2
  add eax, ecx

  add r9, 8
  jz @@Leave

  nop // Alignment
@@SingleChars:
  xor ecx, ecx
@@Loop:
  cmp WORD PTR [r8+r9], dx
  sete cl
  add eax, ecx
  add r9, 2
  jnz @@Loop
@@Leave:
{$ENDIF ~CPUX64}
end;

[KodeZwerg]

Danke Andreas, mit Deinem "{$IFNDEF CPUX64}" fix funktionieren nun alle ASM Varianten, auch die von jaenicke, bei mir. Krasse Ergebnisse, mein lieber Herr Gesangsverein.

[Uwe Raabe]

Zitat von KodeZwerg:

Ich würde zu guter Letzt gerne noch Erfahren ob denn meine Berechnung der Avg-Variable korrekt ist oder auch gänzlich falsch?

So ganz verstehe ich noch nicht, was du mit deine avg-Berechnung genau erreichen willst. Die generelle Vorgehensweise für eine Mittelwertberechnung ergibt sich aus der Definition:

avgn := Sumi:1..n(xi)/N; // xi = Wert bei Iteration i, N Anzahl Iterationen.

Rekursiv ergibt sich daraus:
avgn+1 := (avgn*N + xn+1)/(N+1)

Delphi-Quellcode:

      if Loops = 0 then
      begin
        Last := Curr;
        Min := Curr;
        Max := Curr;
        Avg := Curr;
      end
      else 
      begin
        if Curr < Min then Min := Curr;
        if Curr > Max then Max := Curr;
        Avg := (Loops*Avg + Curr)/(Loops + 1);
        Last := Curr;
      end;

Einfacher wäre aber die Berechnung der Summe innerhalb der Schleife und anschließende Division durch die Anzahl für das avg nach der Schleife.

[Uwe Raabe]

Zitat von jbg:

So und jetzt eine Variante mit SIMD (SSE2, benötigt mindestens Nehalem Prozessorarchitektur von 2008).

Ich erweitere dann mal den Benchmark auf OSX, Linux, Android und iOS

[jbg]

Zitat von Uwe Raabe:

Ich erweitere dann mal den Benchmark auf OSX, Linux, Android und iOS

Für diese Betriebssysteme bzw. eher Platformen nutzt man auch nicht unbedingt Delphi als erste Wahl. Da spuckt einem der entsprechende Compiler schon den tausend mal besseren Code aus.

[KodeZwerg]

Zitat von Uwe Raabe:

So ganz verstehe ich noch nicht, was du mit deine avg-Berechnung genau erreichen willst.

Ich wollte damit den tatsächlichen Durchschnittswert damit ermitteln und nicht die Mitte von Min und Max als Score festlegen.
Dank Deines Links und Text bin ich nun im Bilde.

edit

Delphi-Quellcode:

      if Loops = 0 then
      begin
        Min := Curr;
        Max := Curr;
        Avg := Curr;
      end
      else
      begin
        if Curr < Min then Min := Curr;
        if Curr > Max then Max := Curr;
        Avg := Avg + Curr;
      end;
      if fCancel = True then Break;
    end; // <- hier endet eine For-Schleife (Loops)
    Avg := Avg / Loops;

So habe ich es nun geregelt, sollte overhead reduzieren. Vielen Dank Uwe!

[EgonHugeist]

Kleine Anregungen:

Zitat:

Funktionen von KodeZwerg

CountCharInString, CharInStringA scheitern, wenn #0 im String sind und knallen wenn ein #0 gesucht wird. letzteres sollte mindistens abgefangen und ersteres dokumentiert werden

Zitat:

Funktion AH_CharCountAsm von Andreas aka AHUser aka jbg

ich meine das Result wird nicht initialisiert, wenn der String lehr ist

Zitat:

Aufruf Funktion CharCountAssembler

für CharCountAsm von Neutral General knallte mit {$R+), wenn der String lehr ist. Die function CharCountAsm selber zählt jedoch immer +1 wenn AStr = nil

Zitat:

function IFCount von alzaimar und miep

ist nicht NEXTGEN safe -> falscher Index vom String

Des weiteren muß ich KodeZwerg, wegen der Bemerkung über die Lösung von Ydobon recht geben, zu viele theoretische MemAllocs, welche nicht vergleichbar wären, wenn ... wird den der Code wirklich zu 100%, wie geschrieben, unter XE10.2 ausgeführt??? Weiß der Teufel, wie das zu geht.

im Test selber sollte der gesuchte Char, sowohl die Größe als auch Inhalt des Strings wechseln um alle Ungereimtheiten auszuschließen.

Ansonsten folgende Aufgabe in den Raum gestellt:

Ich bekomme die Aufgabe die Anzahl eines Buchstaben in einem Buch zu finden. Ich soll sie von 1 bis 10000 wiederholen. Buchstabe und Buch wechseln nicht (lt. Uwes Test). Angenommen ihr währed unfehlbar und das Ergebnis steht nach Durchlauf 1 fest ... Wie oft würdet ihr den Job tatsächlich machen?

Die damit verbundene Hypothese: Könnte der Compiler soweit optimiert wurden sein, solch ein Scenario zu erkennen?

Mir kommt Uwes Test a bizzl so vor, als messen wir nur den einmaligen Aufruf-Stack..

Edit:

@@@@jbg

Einfach der Hammer !!! Aber schau mal ob dein Result initialisiert ist, wenn nix zu tun ist!

[Uwe Raabe]

Zitat von EgonHugeist:

Mir kommt Uwes Test a bizzl so vor, als messen wir nur den einmaligen Aufruf-Stack..

Ich hatte bereits probeweise mal die Anzahl Durchläufe auf 100.000 erhöht und auf 1000 erniedrigt. Dabei sind die Zeiten im Bereich der bekannten Schwankungen zwischen verschiedenen Programmstarts ziemlich konsistent um den Faktor 10 verändert worden. Um einen einzelnen Aufruf zu messen reicht die Auflösung meiner Meinung nach einfach nicht aus.
Alles Win32 (die Zeiten für 100000 dauern mir jetzt zu lange):

Zitat von 10000 calls:

00000 Calibrate
03575 1234588 miep
05879 Ydobon
02967 marabu
03797 Missionar
03665 alzaimar
02977 Uwe Raabe StringCountChar
03051 Uwe Raabe StringCountCharFor
02709 KodeZwerg CountCharInString
07248 KodeZwerg CharInStringA
04035 Neutral General CharCountAsm
02026 Andreas Hauladen CharCountAsm
02785 Uwe Raabe CharCount
03052 Egon Hugeist CharCount_1
03648 Egon Hugeist CharCount_2
02899 Egon Hugeist CharCount_3
03226 Egon Hugeist CharCount_4
02464 Egon Hugeist CharCount_5
03382 Egon Hugeist CharCount_6
03693 Delphi CountChar

Zitat von 1000 calls:

00000 Calibrate
00353 1234588 miep
00585 Ydobon
00299 marabu
00373 Missionar
00361 alzaimar
00296 Uwe Raabe StringCountChar
00293 Uwe Raabe StringCountCharFor
00261 KodeZwerg CountCharInString
00681 KodeZwerg CharInStringA
00385 Neutral General CharCountAsm
00199 Andreas Hauladen CharCountAsm
00269 Uwe Raabe CharCount
00300 Egon Hugeist CharCount_1
00357 Egon Hugeist CharCount_2
00283 Egon Hugeist CharCount_3
00299 Egon Hugeist CharCount_4
00229 Egon Hugeist CharCount_5
00334 Egon Hugeist CharCount_6
00366 Delphi CountChar

Es ist auch so, daß die Kalibrierung mit der Fake-Funktion den eigentlichen Funktionsaufruf auch mit berücksichtigt (allein schon, um eine Wegoptimierung der Schleife zu verhindern). Ist aber trotzdem vernachlässigbar.

[EgonHugeist]

@Uwe

ist nur 'ne bescheidene Hypothese. Dennoch sind mir die Ergebnisse von Ydobon viel zu nah an allen anderen. Bist du da mit mir einig? IMO spukt es da ein wenig. Alle sollten sich je nach {$R+} minimal aneinander reihen. Die Theorie die Optimirung von StringReplace ist für mich vom Tisch...