Anzahl eines Zeichens im String ermitteln

[KodeZwerg]

Hier schau mal selbst, das ist mit nur 50000 Zeichen/Bytes, achte auf den Ydobon Zeitwert. Katastrophal bei mir.
Diese Ergebnisse sind nicht unter optimalen Voraussetzungen entstanden da alle Kerne mit was anderem ausgelastet sind.

Zitat:

KodeZwerg's custom Benchmark - DP CountCharInString Edition

Benchmark: Sleep(500)
501037 Nanoseconds wasted. As closer this is to 500000 more accurate Results are given.

Benchmark: Generate Random Data String (50000 chars) Charset: [aA0-zZ9]
609 Nanoseconds wasted.

Benchmark: 1234588 miep(Data, 'X')
141 Nanoseconds wasted. (found X = 748 times)

Benchmark: Ydobon Length(Data)-Length(StringReplace(Data, 'X', '', [rfReplaceAll]))
21149 Nanoseconds wasted. (found X = 748 times)

Benchmark: marabu Occurs(Data, 'X')
201 Nanoseconds wasted. (found X = 748 times)

Benchmark: Missionar cCount(Data, 'X')
139 Nanoseconds wasted. (found X = 748 times)

Benchmark: alzaimar IFCount(Data, 'X')
122 Nanoseconds wasted. (found X = 748 times)

Benchmark: Uwe Raabe StringCountChar(Data, 'X')
122 Nanoseconds wasted. (found X = 748 times)

Benchmark: KodeZwerg CountCharInString(Data, 'X')
160 Nanoseconds wasted. (found X = 748 times)

Benchmark: KodeZwerg CharInStringA(Data, 'X')
253 Nanoseconds wasted. (found X = 748 times)

Benchmark: Uwe Raabe CharCount(Data, 'X')
89 Nanoseconds wasted. (found X = 748 times)

Benchmark: Uwe Raabe CharCount2(Data, 'X')
58 Nanoseconds wasted. (found X = 748 times)

Benchmark: EgonHugeist CharCount3(Data, 'X')
74 Nanoseconds wasted. (found X = 748 times)

Benchmark: Neutral General CharCountAsm(Data, 'X', Length(Data))
115 Nanoseconds wasted. (found X = 748 times)

Benchmark: EgonHugeist EH_CharCount4(Data, 'X')
76 Nanoseconds wasted. (found X = 748 times)

Benchmark: StrScanFast(Data, 'X')
1 Nanoseconds wasted. (found X = 49895 times)

Benchmark: Generate Random Binary Data String (50000 bytes)
324 Nanoseconds wasted.

Benchmark: 1234588 miep(Data, 'X')
109 Nanoseconds wasted. (found X = 180 times)

Benchmark: Ydobon Length(Data)-Length(StringReplace(Data, 'X', '', [rfReplaceAll]))
5814 Nanoseconds wasted. (found X = 180 times)

Benchmark: marabu Occurs(Data, 'X')
204 Nanoseconds wasted. (found X = 180 times)

Benchmark: Missionar cCount(Data, 'X')
131 Nanoseconds wasted. (found X = 180 times)

Benchmark: alzaimar IFCount(Data, 'X')
108 Nanoseconds wasted. (found X = 180 times)

Benchmark: Uwe Raabe StringCountChar(Data, 'X')
109 Nanoseconds wasted. (found X = 180 times)

Benchmark: KodeZwerg CountCharInString(Data, 'X')
1 Nanoseconds wasted. (found X = 1 times)

Benchmark: KodeZwerg CharInStringA(Data, 'X')
71 Nanoseconds wasted. (found X = 1 times)

Benchmark: Uwe Raabe CharCount(Data, 'X')
1 Nanoseconds wasted. (found X = 1 times)

Benchmark: Uwe Raabe CharCount2(Data, 'X')
63 Nanoseconds wasted. (found X = 180 times)

Benchmark: EgonHugeist CharCount3(Data, 'X')
59 Nanoseconds wasted. (found X = 180 times)

Benchmark: Neutral General CharCountAsm(Data, 'X', Length(Data))
154 Nanoseconds wasted. (found X = 180 times)

Benchmark: EgonHugeist EH_CharCount4(Data, 'X')
67 Nanoseconds wasted. (found X = 180 times)

Benchmark: StrScanFast(Data, 'X')
1 Nanoseconds wasted. (found X = 75 times)

[jaenicke]

Delphi 2009 war ja die erste Version mit Unicode. Vermutlich war dort die Umsetzung von StringReplace schlicht noch nicht so gut.

[KodeZwerg]

Screenshot - 15_07.jpgSo in etwa würde neue GUI aussehen.
Wem noch mehr sinnvolle Optionen einfallen, bitte melden.

Edit
Ps: Ein Cancel Button ist nun vorhanden

[Harry Stahl]

Zitat von KodeZwerg:

Anhang 49520So in etwa würde neue GUI aussehen.
Wem noch mehr sinnvolle Optionen einfallen, bitte melden.

Edit
Ps: Ein Cancel Button ist nun vorhanden

Wenn man die zu startenden Funktionen in einer Checklist-Box zuvor auswählen könnte, fände ich gut (evtl. über Popup-Menü mit Einträgen für alle abwählen und alle anwählen). Denn wenn man an einer Funktion evtl. selber noch was rumschrauben wollte, müsste man nicht alle Tests durchlaufen lassen...

Ansonsten:

[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 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

[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.

[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!