HexToDec optimieren

[himitsu]

Das Setup kann man weglassen, wenn man stattdessen eine Konstente verwendet.
Aber zumindestens kann man mit 2 Schleifen das Var-Array befüllen.

Oder besser man macht das als Konstante, wobei es, wenn man davon ausgehen würde, daß immer nur Hex-Werte im String stehen, das Array nicht komplett von #0 bis #255 (AnsiChar) groß sein muß.
array['0'..'z'] oder array['0'..'Z'] wenn nur Großbuchstaben (array[48..122] oder array[48..90])

[Dejan Vu]

Zitat von himitsu:

Das Setup kann man weglassen, wenn man stattdessen eine Konstente verwendet.
Aber zumindestens kann man mit 2 Schleifen das Var-Array befüllen.

Klar. Muss man aber nicht.

Deine zweite Idee (array ['0'..z']) würde ich nicht machen, weil der Compiler dann unnötigerweise eine Subtraktion bei jedem Arrayzugriff einfügt, und wir wollen das ja optimal schnell haben. Da denke ich, sind die paar Bytes zu verschmerzen, die man da vergeudet.

Zitat von Kostas:

@Dejan Vu
wie ist das gemeint? es reicht nicht Bytes einzeln in Dezimal umzuwandeln und als String auszugeben.
Bei den Hex-Zahlen "01 77 72 D6 29 D6 8F" soll danach 412810079753871 herauskommen.

Delphi-Quellcode:

Function FasterHexToInt (hexString : String) : LongInt; // Besser : TBigInt
Var i : Integer;
Begin
  result := 0;
  for i:=1 to length(hexString) do result*16+hexLookup[hexString[i]];
end;

So ist das gemeint. Wenn Du beliebig lange Zahlen willst, dann nimm einen Datentyp für beliebig lange Zahlen z.B. BigInt o.ä. Such mal. Findest Du schon.

[himitsu]

Es kommt drauf an, wie der Compiler der Zugriff optimiert, denn durch verschieben des Offsets (genauer der Startadresse des Arrays, für die Berechnung der Indexposition) kann man diese Substraction entfernen.
Aber man kann ja das Array auch nur hinten kürzen.

Wobei diese kleine Offset-Berechnung am Ende eh nicht auffallen würde, falls Delphi das nicht wegoptimiert, da der restliche Code dennoch wesentlich größer ist.



für 0-9 und A-F:

Delphi-Quellcode:

i := Ord(s[i]) - 48;
if i > 10 then Dec(i, 17);

ShowMessage(IntToStr(i));

PS: Oftmals arbeitet übrigens das CASE genau auf die gleiche Weise.

[Dejan Vu]

Zitat von himitsu:

für 0-9 und A-F:
[DELPHI]i := Ord(s[i]) - 48;
if i > 10 then Dec(i, 17);

Ist langsamer als ein Arrayzugriff. Egal, ob als Konstante oder mit Setup gefüllt. Bezüglich der anderen Frage: Probiere es doch einfach mal aus

[himitsu]

Nja, eigentlich ist ein INC innerhalb der Register schneller, als ein Aufruf, der sich erst an den RAM wendet.

Aber heutzutage darf man sich oftmals nicht mit mehr nur mit den Taktzyklen eines Befehls auseinandersetzen.
Vorallem da in Richtung ARM oftmals versucht wird alle Befehle möglichst gleich lange laufen zu lassen.

Und dazu kommen dann auch noch Optimierungen beim Codepfad, welches krasse auswirkungen zeigen kann, welche es früher nicht gab.
So versucht die CPU schon vorher zu bestimmen, wo der Programmcode lang läuft, steuert entsprechend die Codecache und wenn das Programm dann doch oftmals wo anders lang geht, als das Programm dachte...... siehe das letzte Messergebnis

Delphi-Quellcode:

const
  HexB0: array[#0..'F'] of Byte =  // ist egal, daß es nicht bis 255 geht
   (0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
    2, 3, 4, 5, 6, 7, 8, 9, 0, 0,
    0, 0, 0, 0, 0, 10, 11, 12, 13, 14,
    15);
  HexB1: array['0'..'F'] of Byte =
   (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 0, 0, 0, 0, 0, 0, 10, 11, 12, 13, 14, 15);

  HexI0: array[#0..'F'] of Integer =
   (0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
    2, 3, 4, 5, 6, 7, 8, 9, 0, 0,
    0, 0, 0, 0, 0, 10, 11, 12, 13, 14,
    15);
  HexI1: array['0'..'F'] of Integer =
   (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 0, 0, 0, 0, 0, 0, 10, 11, 12, 13, 14, 15);
  HexX: array[0..15] of AnsiChar = '0123456789ABCDEF';

var
  HexS: array[AnsiChar] of Byte;
  HexD: array of Byte;

procedure TForm22.FormCreate(Sender: TObject);
var
  C: AnsiChar;
  T: Cardinal;
  i, X, L, A, B: Integer;
  S: AnsiString;
  P: PAnsiChar;

begin
  A := 300000000;
  B := 300000000;

  // Hochheizen
  for i := A * 3 downto 0 do ;

  SetLength(HexD, 256);
  for i := 0 to 255 do begin
    HexS[AnsiChar(i)] := 0;
    HexD[         i ] := 0;
  end;
  for i := 0 to 9 do begin
    HexS[AnsiChar(Ord('0') + i)] := i;
    HexD[         Ord('0') + i ] := i;
  end;
  for i := 0 to 5 do begin
    HexS[AnsiChar(Ord('A') + i)] := i + 10;
    HexD[         Ord('A') + i ] := i + 10;
  end;

  SetLength(S, B);
  for i := 1 to B do
    S[i] := HexX[Random(16)];
  P := PAnsiChar(S);

  for L := 0 to 1 do begin
    if L = 0 then Tag := Ord('3') else Tag := Ord('B');
    Memo1.Lines.Add('');
    Memo1.Lines.Add(Chr(Tag) + ':');
    Memo1.Lines.Add('');

    C := AnsiChar(Tag);
    T := GetTickCount;
    for i := A downto 0 do begin
      X := HexB0[C];
      if X = 0 then ;
    end;
    Memo1.Lines.Add('HexB0 = ' + IntToStr(GetTickCount - T));

    C := AnsiChar(Tag);
    T := GetTickCount;
    for i := A downto 0 do begin
      X := HexB1[C];
      if X = 0 then ;
    end;
    Memo1.Lines.Add('HexB1 = ' + IntToStr(GetTickCount - T));

    C := AnsiChar(Tag);
    T := GetTickCount;
    for i := A downto 0 do begin
      X := HexI0[C];
      if X = 0 then ;
    end;
    Memo1.Lines.Add('HexI0 = ' + IntToStr(GetTickCount - T));

    C := AnsiChar(Tag);
    T := GetTickCount;
    for i := A downto 0 do begin
      X := HexI1[C];
      if X = 0 then ;
    end;
    Memo1.Lines.Add('HexI1 = ' + IntToStr(GetTickCount - T));

    C := AnsiChar(Tag);
    T := GetTickCount;
    for i := A downto 0 do begin
      X := HexS[C];
      if X = 0 then ;
    end;
    Memo1.Lines.Add('HexS = ' + IntToStr(GetTickCount - T));

    C := AnsiChar(Tag);
    T := GetTickCount;
    for i := A downto 0 do begin
      X := HexD[Ord(C)];
      if X = 0 then ;
    end;
    Memo1.Lines.Add('HexD = ' + IntToStr(GetTickCount - T));

    C := AnsiChar(Tag);
    T := GetTickCount;
    for i := A downto 0 do begin
      X := Ord(C) - 48;
      if X > 10 then Dec(X, 17);
      if X = 0 then ;
    end;
    Memo1.Lines.Add('Math = ' + IntToStr(GetTickCount - T));
  end;

  begin
    Memo1.Lines.Add('');
    Memo1.Lines.Add('Random:');
    Memo1.Lines.Add('');

    T := GetTickCount;
    for i := B downto 0 do begin
      X := HexB0[P[i]];
      if X = 0 then ;
    end;
    Memo1.Lines.Add('HexB0 = ' + IntToStr(GetTickCount - T));

    T := GetTickCount;
    for i := B downto 0 do begin
      X := HexB1[P[i]];
      if X = 0 then ;
    end;
    Memo1.Lines.Add('HexB1 = ' + IntToStr(GetTickCount - T));

    T := GetTickCount;
    for i := B downto 0 do begin
      X := HexI0[P[i]];
      if X = 0 then ;
    end;
    Memo1.Lines.Add('HexI0 = ' + IntToStr(GetTickCount - T));

    T := GetTickCount;
    for i := B downto 0 do begin
      X := HexI1[P[i]];
      if X = 0 then ;
    end;
    Memo1.Lines.Add('HexI1 = ' + IntToStr(GetTickCount - T));

    T := GetTickCount;
    for i := B downto 0 do begin
      X := HexS[P[i]];
      if X = 0 then ;
    end;
    Memo1.Lines.Add('HexS = ' + IntToStr(GetTickCount - T));

    T := GetTickCount;
    for i := B downto 0 do begin
      X := HexD[Ord(P[i])];
      if X = 0 then ;
    end;
    Memo1.Lines.Add('HexD = ' + IntToStr(GetTickCount - T));

    T := GetTickCount;
    for i := B downto 0 do begin
      X := Ord(P[i]) - 48;
      if X > 10 then Dec(X, 17);
      if X = 0 then ;
    end;
    Memo1.Lines.Add('Math = ' + IntToStr(GetTickCount - T));
  end;
end;

[Dejan Vu]

Ich gebe mich in allen belangen und ausnahmslos geschlagen.

[himitsu]

Daß die Varianten mit und ohne Ofset gleich schnell sind, hatte ich fast erwartet, wobei das früher aber auch mal von der größe des Offsets abhing, da kleinere Vielfache von 2 direkt in einem Index-Befehl kombiniert werden können.

Aber daß nun Byte und Integer gleich schnell sind, war bissl überraschen, aber das liegt wohl an der Ivy-Architektur.
Eigentlich sind ja zusätzliche umkopieroperationen nötig, um nochmal aus den Byte einen Integer zu machen.

Vorallem war ich etwas überascht, daß Zugriffe auf ein dynamisches Array manchmal schneller waren, als auf ein statisches Array, und selbst bei aktivierter Indexprüfung nicht viel langsamer wurden.

> i7

Code:

3:

HexB0 = 219
HexB1 = 203
HexI0 = 218
HexI1 = 218
HexS = 219
HexD = 327
Math = 312

B:

HexB0 = 203
HexB1 = 219
HexI0 = 218
HexI1 = 203
HexS = 203
HexD = 312
Math = 421

Random:

HexB0 = 234
HexB1 = 234
HexI0 = 219
HexI1 = 234
HexS = 218
HexD = 343
Math = 1529

Rein logisch sollte doch das Ergbnis im Random der Durchschnitt aus 3 und 8 sein, was beim Math bedeutet JUMP oder nicht JUMP und stattdessen DEC,
also 10/16-tel von 3 und 6/16-tel vom B.



Und wir hatten hier über die Jahre schon oftmals den Fall, wo man zwanghaft versuchte den Code via Assembler selber zu optimieren.
Abgesehn davon, daß man jetzt den Spaß hat und sich nicht mehr nur überlegen muß "Windows" und später auch noch "Windows 64" und dann bei speziallfällen noch Intel, AMD und welche Revision davon usw.
Jetzt auch noch OSx, iOS, Android, welcher Handyhersteller, .........

Aber das Krasseste war, daß oft sogar die Codeoptimierung vom Delphi schon so gut war, daß man manchmal nichtmal 'ne Millisekunde rausholen konnte.

[Dejan Vu]

Sehr schön, wenn man das einfach ausprobiert. Alles unter 5% würde ich als Rauschen erachten. Bei der Messdauer von 200ms pro Durchlauf bist Du aber bei einer Genauigkeit von +-18ms, sodaß ich hier die Anzahl der Durchläufe so erhöhen würde das ein Durchlauf mindestens 1-2 Sekunden dauert.

Ferner würde ich den Zugriff an die Erfordernisse anpassen, also nicht konstant immer auf den selben Array-Index zugreifen (man sieht sehr schön, wie Cache und Prediction hier zuschlagen) sondern eben z.B. zufällig.

Ich habe die Durchlaufzahl verdreifacht und bei mir kommt dann raus:

Code:

3:
HexB0 = 1467
HexB1 = 1450
HexI0 = 1046
HexI1 = 920
HexS = 905
HexD = 920
Math = 921

B:
HexB0 = 904
HexB1 = 921
HexI0 = 920
HexI1 = 905
HexS = 920
HexD = 921
Math = 1061

Random:
HexB0 = 999
HexB1 = 1372
HexI0 = 1576
HexI1 = 1560
HexS = 1560
HexD = 1779
Math = 7644

[Mavarik]

hmm

Delphi-Quellcode:

{--------------------------------------------------------------}
function HexToDec(const s: Array of Byte): AnsiString; overload;
//Sehr grosse Hex-Zahlen Decimal umwandeln
{--------------------------------------------------------------}
var
    total : Int64;
    i,n: Integer;
begin
  total := 0;

  if length(s) > 8 then
    Exit; 

  for i := 0 to high(s)-1 do
    begin
      total := total or S[i];
      total := total shl 8;   
    end;
    total := total or S[7];

  Result := inttostr(total);
end;

Oder habe ich etwas falsch verstanden?

Mavarik

[himitsu]

Ja, denn er braucht auch mal mehr, als nur 64 Bit.

Binär könnte man das über mehrere Int64 lösen, aber die Umwandlung nach Dezimal wird dann ein bissl umständlicher.