MyStrToHex extrem schnell

[PeterPanino]

Hallo! Ich möchte folgende Funktion auf extreme Geschwindigkeit optimieren:

Delphi-Quellcode:

function MyStrToHex(s: string): string;
var
  i: Integer;
begin
  Result := '';
  for i := 1 to Length(s) do
    Result := Result + IntToHex(Ord(s[i]), 4);
end;

Kennt jemand eine Assembler-Version davon?

[Bernhard Geyer]

Du brauchst keine Assembler um zu beschleunigen

1, Ergänze ein const beim Aufrufparameter
2, Verwende den Stringbuilder den es in neueren Delphiversionen gibt.

[PeterPanino]

Meinst etwa so?:

Delphi-Quellcode:

function MyStrToHex(const s: TStringBuilder): TStringBuilder;
var
  i: Integer;
begin
  Result := TStringBuilder.Create;
  for i := 0 to s.Length - 1 do  
    Result.Append(IntToHex(Ord(s.Chars[i]), 4));  
end;

SB := TStringBuilder.Create;
SB.Append('Tᾯest');
SB := MyStrToHex(SB);
Self.Caption := SB.ToString;
SB.Free;

Aber damit scheint der Code nicht schneller, sondern eher langsamer geworden zu sein.

Außerdem mache ich mir Sorgen: Muss die in der Funktion MyStrToHex in Result erzeugte StringBuilder-Instanz nicht irgendwie freigegeben werden?

[Medium]

Wie wäre es damit:

Delphi-Quellcode:

function MyStrToHex(const s: string): string;
var
   i: Integer;
begin
   SetLength(Result, Length(s)*4);
   for i := 0 to Length(s)-1 do
     Move(IntToHex(Ord(s[i+1]), 4), Result[i*4+1], 4);
end;

Ich habe gerade kein Delphi zur Hand, eventuell ließe sich IntToHex() noch effizienter implementieren und inlinen.

[Bernhard Geyer]

Zitat:

Zitat von PeterPanino (Beitrag 1196589)

Meinst etwa so?:

Für die Methodensignatur kannst du weiter Strings nehmen.
Nur beim Zusammenbauen des Strings den Stringbuilder nehmen:

Delphi-Quellcode:

function MyStrToHex(const s: String): String;
var
  i: Integer;
  StrBuilder: TStringBuilder;
begin
  StrBuilder := TStringBuilder.Create;
  try
    for i := 0 to s.Length - 1 do 
      StrBuilder.Append(IntToHex(Ord(s[i]), 4)); 

    result := STrBuilder.ToString;
  finally
    StrBuilder.Free;
  end;
end;

Ansonsten probier Medium's Version.

[Uwe Raabe]

Kein Assembler, aber trotzdem recht schnell:

Delphi-Quellcode:

function MyStrToHex(const s: string): string;
const
  hex: array[0..15] of WideChar = '0123456789ABCDEF';
var
  I: Integer;
  W: WordRec;
  P: PChar;
begin
  SetLength(Result, 4*Length(S));
  P := PChar(Result);
  for I := 1 to Length(S) do
  begin
    W := WordRec(S[I]);
    P[0] := hex[W.Hi shr 4];
    P[1] := hex[W.Hi and $F];
    P[2] := hex[W.Lo shr 4];
    P[3] := hex[W.Lo and $F];
    Inc(P, 4);
  end;
end;

[Furtbichler]

IntToHex sollte sich optimieren lassen, z.B. über eine Lookuptabelle.

[PeterPanino]

Zitat:

Zitat von Bernhard Geyer (Beitrag 1196602)

Zitat:

Zitat von PeterPanino (Beitrag 1196589)

Meinst etwa so?:

Für die Methodensignatur kannst du weiter Strings nehmen.
Nur beim Zusammenbauen des Strings den Stringbuilder nehmen:

Delphi-Quellcode:

function MyStrToHex(const s: String): String;
var
  i: Integer;
  StrBuilder: TStringBuilder;
begin
  StrBuilder := TStringBuilder.Create;
  try
    for i := 0 to s.Length - 1 do 
      StrBuilder.Append(IntToHex(Ord(s[i]), 4)); 

    result := STrBuilder.ToString;
  finally
    StrBuilder.Free;
  end;
end;

Ansonsten probier Medium's Version.

Du meintest wahrscheinlich so:

Delphi-Quellcode:

function MyStrToHex(s: string): string;
var
  i: Integer;
  SB: TStringBuilder;
begin
  Result := '';
  SB := TStringBuilder.Create;
  try
    for i := 1 to Length(s) do
      SB.Append(IntToHex(Ord(s[i]), 4));
    Result := SB.ToString;
  finally
    SB.Free;
  end;
end;

Vielen Dank für den Tipp! Gibt es aber eine Erklärung dafür, wieso TStringBuilder.Append schneller sein soll als das traditionelle Zusammenfügen von Strings mit dem Additionszeichen?

[PeterPanino]

Zitat:

Zitat von Uwe Raabe (Beitrag 1196605)

Kein Assembler, aber trotzdem recht schnell:

Delphi-Quellcode:

function MyStrToHex(const s: string): string;
const
  hex: array[0..15] of WideChar = '0123456789ABCDEF';
var
  I: Integer;
  W: WordRec;
  P: PChar;
begin
  SetLength(Result, 4*Length(S));
  P := PChar(Result);
  for I := 1 to Length(S) do
  begin
    W := WordRec(S[I]);
    P[0] := hex[W.Hi shr 4];
    P[1] := hex[W.Hi and $F];
    P[2] := hex[W.Lo shr 4];
    P[3] := hex[W.Lo and $F];
    Inc(P, 4);
  end;
end;

Vielen Dank für den Tipp! Diese Version ist tatsächlich noch schneller als die StringBuilder-Version!

Ich habe mir auch überlegt, ob man den Schleifeninhalt nicht etwa in eine inline-Funktion auslagern kann, um die Geschwindigkeit nochmal zu steigern, sehe aber keine Möglichkeit dafür.

[PeterPanino]

Für die Umkehrfunktion verwende ich folgende Konstruktion:

Delphi-Quellcode:

function MyStrToIntSafe(const Value: string; const ExceptionResult: Integer): Integer; inline;
begin
  try
    Result := StrToInt(Value);
  except
    Result := ExceptionResult;
  end;
end;

function MyHexToChar(const s: string; const i: Integer): Char; inline;
begin
  Result := Chr(MyStrToIntSafe('$' + Copy(s, i, 4), 63));
end;

function MyHexToStr(s: string): string;
var
  i, L: Integer;
begin
  Result := '';
  L := Length(s);
  i := 1;
  while i < L do
  begin
    Result := Result + MyHexToChar(s, i);
    Inc(i, 4);
  end;
end;

Hier habe ich durch Auslagerung von Schleifeninhalten in inline-Funktionen nochmals eine Geschwindigkeitssteigerung erreicht.

[PeterPanino]

Bzw. hier die StringBuilder-Version mit hinzugefügtem const-Modifier:

Delphi-Quellcode:

function MyHexToStr(const s: string): string;
var
  i, L: Integer;
  SB: TStringBuilder;
begin
  Result := '';
  L := Length(s);
  i := 1;
  SB := TStringBuilder.Create;
  try
    while i < L do
    begin
      SB.Append(MyHexToChar(s, i));
      Inc(i, 4);
    end;
    Result := SB.ToString;
  finally
    SB.Free;
  end;
end;

Scheint nochmals um eine kleine Spur schneller zu sein.

[Furtbichler]

Zitat:

Zitat von Uwe Raabe (Beitrag 1196605)

Kein Assembler, aber trotzdem recht schnell:

Hmm. Bei ungeraden Stringlängen keine gute Lösung.

Edit: Doch doch, alles ok.

[PeterPanino]

Zitat:

Zitat von Furtbichler (Beitrag 1196620)

Zitat:

Zitat von Uwe Raabe (Beitrag 1196605)

Kein Assembler, aber trotzdem recht schnell:

Hmm. Bei ungeraden Stringlängen keine gute Lösung.

Meinst du die Länge des an die Funktion übergebenen Strings s oder die Konstante 4?

[Furtbichler]

Bei ungerader Stringlänge wird der letzte Zugriff auf WordRec(s[i]) über das letzte Zeichen des Strings hinaus gehen.

Edit: Blödsinn, wir reden von WideChars... Ich nehme alles zurück.

[Furtbichler]

Hier ist mein Beitrag; 5x schneller als die Variante von Uwe Raabe. Das Ende der Fahnenstange ist bestimmt noch nicht erreicht.

Delphi-Quellcode:

Type
  THexLookup = Array [WideChar] Of Integer;
Var
  HexLookup  : ^THexLookup;

Procedure BuildHexLookup;
Var
  w : Word;
  s : String;

Begin
  New(HexLookup);
  for w := 0 to 65535 do begin
    s := IntToHex(w,4);
    Move(s[1], HexLookup^[WideChar(w)],4);
  end;
End;

function FurtbichlerStrToHex(const s: Widestring): string;
var
   i : Integer;
   p : PIntegerArray;

begin
   SetLength(Result, 4*Length(s));
   p := @Result[1];
   for i := 1 to Length(s) do 
     p^[i-1] := HexLookup^[s[i]];

end;

...
initialization
  BuildHexLookup;

[Bernhard Geyer]

Und wenn man dann auch noch Rangechecks & Co nur für diese Funktion immer abschaltet bekommt man noch ein paar Prozent raus.

[Uwe Raabe]

Zitat:

Zitat von PeterPanino (Beitrag 1196611)

Ich habe mir auch überlegt, ob man den Schleifeninhalt nicht etwa in eine inline-Funktion auslagern kann, um die Geschwindigkeit nochmal zu steigern, sehe aber keine Möglichkeit dafür.

Inline bedeutet ja nur, daß der Compiler für dich den Code an den jeweiligen Aufrufen einfügt. Solange du den Schleifeninhalt nicht noch anderweitig verwendest, gewinnst du damit gar nichts.

[PeterPanino]

Zitat:

Zitat von Uwe Raabe (Beitrag 1196633)

Zitat:

Zitat von PeterPanino (Beitrag 1196611)

Ich habe mir auch überlegt, ob man den Schleifeninhalt nicht etwa in eine inline-Funktion auslagern kann, um die Geschwindigkeit nochmal zu steigern, sehe aber keine Möglichkeit dafür.

Inline bedeutet ja nur, daß der Compiler für dich den Code an den jeweiligen Aufrufen einfügt. Solange du den Schleifeninhalt nicht noch anderweitig verwendest, gewinnst du damit gar nichts.

Ich dachte, mit inline kann man Funktionen beschleunigen, die sehr oft aufgerufen werden?

[Uwe Raabe]

Zitat:

Zitat von PeterPanino (Beitrag 1196636)

Ich dachte, mit inline kann man Funktionen beschleunigen, die sehr oft aufgerufen werden?

Bei einem normalen Funktionsaufruf werden die Parameter auf dem Stack übergeben und ein echter Aufruf ausgeführt. Ist eine Methode als inline deklariert, fügt der Compiler den Code aus der Methode bei jedem Aufruf direkt an der Stelle ein, an der die Funktion aufgerufen wird. Es ist faktisch dasselbe als wenn man selbst die Funktion jedesmal an die Aufrufstelle kopiert.

Delphi-Quellcode:

procedure Step(var A, B: Integer); inline;
begin
  Inc(A);
  Inc(B);
end;

var
  I, J, N: Integer;
begin
  I := 0;
  J := I + 1;
  for N := 1 to 10 do 
    Step(I, J);
end;

Ist also vom Compilat her identisch mit

Delphi-Quellcode:

var
  I, J, N: Integer;
begin
  I := 0;
  J := I + 1;
  for N := 1 to 10 do begin 
    Inc(I);
    Inc(J);
  end;
end;

Natürlich ist das schneller als der Funktionsaufruf ohne inline, da einige zusätzliche Befehle eingespart werden. Man kann also mit inline einen Funktionsaufruf schneller machen, aber nur wenn tatsächlich ein Aufruf stattfindet.

[PeterPanino]

Zitat:

Zitat von Furtbichler (Beitrag 1196630)

Hier ist mein Beitrag; 5x schneller als die Variante von Uwe Raabe. Das Ende der Fahnenstange ist bestimmt noch nicht erreicht.

Delphi-Quellcode:

Type
  THexLookup = Array [WideChar] Of Integer;
Var
  HexLookup  : ^THexLookup;

Procedure BuildHexLookup;
Var
  w : Word;
  s : String;

Begin
  New(HexLookup);
  for w := 0 to 65535 do begin
    s := IntToHex(w,4);
    Move(s[1], HexLookup^[WideChar(w)],4);
  end;
End;

function FurtbichlerStrToHex(const s: Widestring): string;
var
   i : Integer;
   p : PIntegerArray;

begin
   SetLength(Result, 4*Length(s));
   p := @Result[1];
   for i := 1 to Length(s) do 
     p^[i-1] := HexLookup^[s[i]];

end;

...
initialization
  BuildHexLookup;

Mhmm, irgendwas scheint da nicht zu funktionieren - das Programm braucht nun ca. 100 mal länger als vorher, um den Code auszuführen. Ich verstehe den Code nicht, deswegen kann ich nicht sagen, wo der Fehler liegt.

[PeterPanino]

Und das Ergebnis ist auch ein völlig anderes:

Delphi-Quellcode:

Self.Caption := FurtbichlerStrToHex('Tᾯest ♀♥♂');
// Ergebnis: 001F00000000262626

Self.Caption := MyStrToHex('Tᾯest ♀♥♂');
// Ergebnis: 00541FAF0065007300740020264026652642

Das Ergebnis von MyStrToHexist korrekt. Ich habe es überprüft, indem ich die Umkehrfunktion auf das Ergebnis angewendet habe, um wieder den Ausgangsstring zu erhalten.

[Furtbichler]

Du must bei mir die 'String' durch 'AnsiString' austauschen. Ich verwende noch so ein altes Delphi. Dann kommt da auch das Gleiche raus.

Die Frage ist aber, ob das so gewollt ist (Rückgabewert AnsiString). Wenn nicht, muss man noch umstricken. Was willst Du eigentlich damit erreichen?

[PeterPanino]

Du hast recht. FurtbichlerStrToHex ist etwa doppelt so schnell wie MyStrToHex. Ich habe es getestet, indem ich die Funktion 1 Million mal ausgeführt habe:

1 Million Ausführungen:

FurtbichlerStrToHex: Ca. 75 Millisekunden
MyStrToHex: Ca. 135 Millisekunden

Ist FurtbichlerStrToHex fehleranfälliger als MyStrToHex?

[PeterPanino]

Zitat:

Zitat von Furtbichler (Beitrag 1196649)

Was willst Du eigentlich damit erreichen?

Bei einem Verfahren, in das ich nicht eingreifen kann, werden Unicode-Zeichen in Strings so encodiert, dass eine nachherige Decodierung extrem umständlich und fehleranfällig ist. Deshalb encodiere ich die Strings nach Hex, was die nachherige Decodierung einfach und fehlerfrei sicherstellt.

[Zacherl]

Zitat:

Zitat von PeterPanino (Beitrag 1196651)

Zitat:

Zitat von Furtbichler (Beitrag 1196649)

Was willst Du eigentlich damit erreichen?

Bei einem Verfahren, in das ich nicht eingreifen kann, werden Unicode-Zeichen in Strings so encodiert, dass eine nachherige Decodierung extrem umständlich und fehleranfällig ist. Deshalb encodiere ich die Strings nach Hex, was die nachherige Decodierung einfach und fehlerfrei sicherstellt.

Dann könnte es sogar sein, dass entsprechende Base64 / MIME64 Libs noch einen Tick geeigneter (und schneller) sind.

[PeterPanino]

Zitat:

Zitat von Zacherl (Beitrag 1196669)

Dann könnte es sogar sein, dass entsprechende Base64 / MIME64 Libs noch einen Tick geeigneter (und schneller) sind.

Welche etwa?

[PeterPanino]

Das Beste, was ich bis jetzt gefunden habe: DCPbase64 aus DCPcrypt v2.0 (Copyright (c) 1999-2002 David Barton):

Delphi-Quellcode:

for i := 1 to 1000000 do // 1 Million
  DCPbase64.Base64DecodeStr(DCPbase64.Base64EncodeStr('Tᾯest ♀♥♂')); // 0,5 Sekunden

Ist wirklich wesentlich schneller als die bisher besprochenen Encodier-Routinen.

Edit: Mit der neuesten Version: 0,2 Sekunden (1 Million Durchläufe der obigen Anweisung)
Edit2: Diese neuste Version ist offenbar fehlerhaft