Anzahl eines Zeichens im String ermitteln

[himitsu]

Zitat von jaenicke:

Wenn es wirklich auf die Performance ankommt, blieben noch spezielle CPU Instruktionen wie repne scasb bzw. repne scasw. Die habe ich auch schon benutzt, aber das macht nur Sinn, wenn es wirklich Not tut. Eben wegen Portabilität usw.

Im Prinzip machen das StrScan, Pos usw. auch schon, um das erste Char des Suchtextes schnell zu finden ... halt mit noch bissl mehr drumrum, da dort ja ganze Zeichenketten gesucht werden.

Zitat von freimatz:

Wegen Portabilität und so: Ihr berücksichtigt keine Unicode Surrogate-Paare.

Also das ist erstmal kein Problem, denn die Surrogates haben ihren eigenen Bereich, also wenn du nach was Anderem suchst, dann findet man nicht ausversehn einen halben Surrogate.

Surrogate selber kann man aber nicht suchen, bzw. eben nur einzeln nach den beiden Hälften.

[EgonHugeist]

@Uwe

Schaut gut aus! No a bizzl kürzer:

Delphi-Quellcode:

function CharCount(const S: string; C: Char): Cardinal;
var
  P, PEnd: PChar;
begin
  Result := 0;
  P := Pointer(S);
  if P = nil then Exit;
  PEnd := P + PLongInt(NativeUInt(P) - SizeOf(LongInt))^;
  while P < PEnd do begin
    Inc(Result, Ord(P^ = C));
    Inc(P);
  end;
end;

[himitsu]

Ein gutes Beispiel für Codes, die in 64 Bit gnadenlos abrauchen.

[EgonHugeist]

Zitat von himitsu:

Ein gutes Beispiel für Codes, die in 64 Bit gnadenlos abrauchen.

Na dann klär mich mal auf! Hättest du FPC anstatt von nur "64 Bit" geschrien dann hättest du meiner bescheidenen Meinung nach recht.
Edit:

Code:

function CharCount(const S: string; C: Char): Cardinal;
var
  P, PEnd: PChar;
begin
  Result := 0;
  P := Pointer(S);
  if P = nil then Exit;
  {$IFNDEF FPC}
  PEnd := P + PLongInt(NativeUInt(P) - SizeOf(LongInt))^;
  {$ELSE}
  PEnd := P + PSizeInt(NativeUInt(P) - SizeOf(SizeInt))^;
  {$ENDIF}
  while P < PEnd do begin
    Inc(Result, Ord(P^ = C));
    Inc(P);
  end;
end;

[himitsu]

Zitat von EgonHugeist:

Na dann klär mich mal auf! Hättest du FPC anstatt von nur "64 Bit" geschrien dann hättest du meiner bescheidenen Meinung nach recht.

Stell dir mal vor demnächst fragt jemand bei Emba an, warum Strings unter 64 Bit nicht mehr als 4 GB groß sein dürfen?
Dann ändert Emba die Struktur und es knallt.

Wenn möglich also immer vordefinierte Casts/Funktion nutzen und nicht gefährlich selber auf interne Strukturen zugreifen.

Ich sehe hier auch keinen Vorteil, weswegen nicht Length verwendet werden kann. Die Funktion hat dann sogar 70% weniger Code.
Und auch für die anderen Informationen gibt es schon seit 9 Jahren fertige Funktionen.

Delphi-Quellcode:

{ string info utilities }
function StringElementSize(const S: UnicodeString): Word; overload; inline;
function StringElementSize(const S: RawByteString): Word; overload; inline;
function StringCodePage(const S: UnicodeString): Word; overload; inline;
function StringCodePage(const S: RawByteString): Word; overload; inline;
function StringRefCount(const S: UnicodeString): Integer; overload; inline;
function StringRefCount(const S: RawByteString): Integer; overload; inline;
{$IFNDEF MSWINDOWS}
function StringElementSize(const S: WideString): Word; overload; inline;
function StringCodePage(const S: WideString): Word; overload; inline;
function StringRefCount(const S: WideString): Integer; overload; inline;
{$ENDIF}

Gut, bissl blöd ist, dass

Delphi-Quellcode:

type
  PStrRec = ^StrRec;
  StrRec = packed record
    codePage: Word;
    elemSize: Word;
    refCnt: Longint;
    length: Longint;
  end;

  PDynArrayRec = ^TDynArrayRec;
  TDynArrayRec = packed record
    RefCnt: LongInt;
    Length: LongInt;
  end;

in der System-Unit nicht öffentlich deklariert sind, sonst könnte man sie direkt zum Casten nehmen.

[EgonHugeist]

Assoooo! Und ich dachte schon ...

Der code ist mir klar. Auch die möglicherweise begleitenden Probleme die sich durch den Anruf bei Emba ergeben könnten.
Wenn man so mit dem Speicher spielt, sollte das auch klar sein.

Da greift man auch anders an:

Delphi-Quellcode:

type 
  //zentral deklariert
  PStrLenInt ^StrLenInt;
  StrLenInt = {$IFDEF FPC}SizeInt{$ELSE}LongInt{$ENDIF};
// sollte Delphi den speicher bereich über 2/4GB wie FPC-64 jemals erweitern, würde da ein weiteres Property-Based define den richtigen Type declarieren.
// somit schaut der code so aus:

function CharCount(const S: string; C: Char): Cardinal;
var
  P, PEnd: PChar;
begin
  Result := 0;
  P := Pointer(S);
  if P = nil then Exit;
  PEnd := P + PStrLenInt(NativeUInt(P) - SizeOf(StrLenInt))^;
  while P < PEnd do begin
    if P^ = C then
      Inc(Result);
    Inc(P);
  end;
end;

Das gewöhnt man sich an, wenn gleicher code von D2...XE10.2 laufen soll, jedoch inline code erst seit D2005 möglich ist und jeder call 50cycles verschwended, wie mir Uwe so schön gezeigt hat.

Bedenken hin oder her, wo jedoch ist das CPU64 Problem? Oder gibt es doch keins?

Edit
PS.: 4GB sind yuch nur für den UnicodeString verfügbar, da ElementSize = 2 ist, theoretische 8GB für einen UCS4String (wenn es den gibt unter Delphi?) und nur 2GB für all SingleByte-Long-Strings.

Edit2: Selbst wenn StrRec/PStrRec definiert wären wie soll denn dann der Cast ausschauen? Du hast nur einen Speichblock mit n-Bytes. Eine cast über PStrRec müßte auch rückwärts (SizeOf(StrRec))gerechnet werden.

[Neutral General]

Ich poste meine Assembler Version einfach mal.

Delphi-Quellcode:

function CharCountAsm(AStr: PChar { eax }; AChar: Char { dx }; len: Integer { ecx }): Integer;
label loop_start, loop_ende, ende; 
asm
  // Danke gammatester! - sorgt dafür dass scasw vorwärts und nicht rückwärts sucht
  cld 
  // edi + ax für scasw initialisieren
  mov edi, eax  
  mov ax, dx
  // edx = char count := 0
  xor edx, edx  
loop_start:
  repnz scasw    // bis zum nächsten Vorkommen "vorspulen"
  jcxz loop_ende // Wenn String zu Ende, aus Schleife springen
  inc edx        // Vorkommen des Chars mitzählen
  jmp loop_start
loop_ende:
  jnz ende     
  inc edx         // Falls der letzte Buchstabe noch ein Treffer war
ende:
  mov result, edx
end;

i := CharCountAsm(@Data[1], 'X', Length(Data));

Damit erreiche ich momentan den 2. Platz im Benchmark (CountCharInString gewinnt).

ACHTUNG: Da scheint auch noch irgendwo ein kleiner Denkfehler drin zu sein
In (relativ) seltenen Fällen zählt mein Code aus irgendeinem Grund falsch.
Falls jemand eine Idee hat wo der Fehler ist oder wie man den Code generell noch verbessern/verschnellern kann wäre das super!

64-Bit ginge natürlich auch, aber habe wenig Erfahrung mit 64 Bit Assembler, deswegen lasse ichs erst mal.

[gammatester]

Zitat von Neutral General:

ACHTUNG: Da scheint auch noch irgendwo ein kleiner Denkfehler drin zu sein

Da scheint auch noch ein grundsätzlicher Fehler drin zu sein, da Du nirgends das Directionflag mit cld auf 0 setzt. Ich würde mich zumindest nicht darauf verlassen.

[KodeZwerg]

Man kann ja auch die RandomString() seperat aufrufen um damit eine feste Datei erzeugen.
Ich wollte den Traffic sparen und fand hier in DP diese nützliche Unit um Strings beliebiger Länge zu generieren in dem moment praktikabler aber der Replikation und Schwankungen zur Folge hast Du Recht, so ist es nur eine objektive Momentaufnahme.
Bei Tokyo ist ja TStopWatch enthalten, die Timing-Funktion kann man damit auch ersetzen/erweitern, ob damit andere/bessere Ergebnisse rauskommen?

[Uwe Raabe]

Zitat von KodeZwerg:

Bei Tokyo ist ja TStopWatch enthalten, die Timing-Funktion kann man damit auch ersetzen/erweitern, ob damit andere/bessere Ergebnisse rauskommen?

Im Wesentlichen macht TStopWatch ja auch nichts anderes. Es geht ja auch nicht um die absoluten Werte, sondern um die Vergleichbarkeit.