HexToDec optimieren

[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

[himitsu]

Ich hatte das auch schon länger laufen lassen.

Aber ich hatte natürlich auch schon das verhalten, daß bei mehreren Durchgängen heute teilweise andere Ergebnisse rauskommen, als vor ein paar Stunden.


Außer beim Math sollten die Werte der jeweiligen 3 und B-Durchläufe im Durchschnitt gleich sein und Random im gleichen Verhältnis ein bissl ansteigen.
Und bei Math kommt es dann auf die CPU an. In einem uralten 8086 würde Dieses bestimmt plötzlich mit großer Sicherheit das Schnellste sein.

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

[Mavarik]

Zitat von 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.

OK dann für jeweils 8 Byte erst mal so..
Denke nicht das es noch schneller geht...

Delphi-Quellcode:

function HexToDec(const s: Array of Byte): AnsiString; overload;
//Sehr grosse Hex-Zahlen Decimal umwandeln
{--------------------------------------------------------------}
var
  a : int64;
  b : array[0..3] of word absolute s;
  c : array[0..3] of word absolute a;
begin
  c[3] := swap(b[0]);
  c[2] := swap(b[1]);
  c[1] := swap(b[2]);
  c[0] := swap(b[3]);
  result := inttostr(a);
end;

Mavarik

[Dejan Vu]

Das soll funktionieren, wenn in s ein String aus Hex-Ziffern steht?

Allgemein würde ich mich zunächst auf ein Format für große Zahlen einigen (BigInt, string etc.). Für das entsprechende Format benötigt man dann nur die Addition und Multiplikation.

Der Rest ist doch trivial:

Delphi-Quellcode:

Type
  IBigInteger = interface 
    Procedure Assign (n : Integer);
    Procedure Add (n : Integer);
    Procedure Multiply (n : Integer);
  end;

Function HexToNumber (aHugeHex : Array Of AnsiChar) : IBigInteger;
Var
  i : Integer;

Begin
  result := CoBigInteger.Create;
  result.Assign(0);
  for i:=high(aHugeHex) downto Low(aHugeHex) do begin
    result.Multiply (16);
    result.Add (hexLookup[aHugeHex[i]]);
  end;
  return result;
end;

Wenn ich es nicht komplett verrissen habe, sollte das doch so funktionieren. Zum Testen kann man ja eine Klasse schreiben, die IBigInteger implementiert und das ganze aber für Int64 umsetzt. Wenn das klappt, passt man das für BigInt oder ein eigenes Format an.

[Mavarik]

Zitat von Dejan Vu:

Das soll funktionieren, wenn in s ein String aus Hex-Ziffern steht?

Zitat von Kostas:

Ich benötige die gleiche function nur als weitere Variante die als Parameter ein "Array of Byte" bekommt.

Oder?

[gammatester]

Hier eine alte Routine für wirklich lange Umwandlungen von Bytearrays in Radix-B-Zahlen, schnell aufgebohrt für die Situation hier. Ist etwas allgemeiner da auch andere Ziel-Basen neben 10 nöglich sind.

Delphi-Quellcode:

function base256_to_baseB(var a: array of byte; n: integer;  B: byte): string;
  {-n byte of big-endian base 256 number to base B string, a is destroyed}
const
  cmap: array[0..61] of char = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz';
var
  i,k,m: integer;
  w: word;
  d: byte;
  s: string;
begin
  s := '';
  {k is index of MSB of a}
  k := low(a);
  m := low(a)+n-1;
  repeat
    {One repeat iteration calculates a := a div B;  d := a mod B}
    {initialize "carry"}
    w := 0;
    for i:=k to m do begin
      {loop invariant: 0 <= w < B}
      w := (w shl 8) or a[i];
      if w>=B then begin
        d := w div B;
        w := w mod B;
      end
      else d:=0;
      a[i] := d;
    end;
    {set d to remainder, w is still < B!}
    d := byte(w);
    {add base R digit to result if d is not out of range}
    if d<sizeof(cmap) then s := cmap[d]+s
    else s := '?'+s;
    {if MSB(a) is zero increment lower bound}
    if a[k]=0 then inc(k);
  until k>m;
  base256_to_baseB := s;
end;

Habe mir nicht die Mühe gemacht, die Routine so zu ändern, daß die Eingabe nicht überschrieben wird. Ein Testprogamm für die Funktion

Delphi-Quellcode:

const
  Test: array[0..24] of byte = (
          $9F,$4F,$27,$26,$17,$9A,$22,$45,$01,$D7,$62,$42,$2C,
          $94,$65,$90,$D9,$10,$00,$00,$00,$00,$00,$00,$2A);
var
  s: string;
  tmp: array[0..100] of byte;
  i: integer;
begin
  {Copy because arg is destroyed}
  for i:=0 to sizeof(Test)-1 do tmp[i] := Test[i];
  s := base256_to_baseB(tmp, sizeof(Test), 10);
  writeln('Decimal number: ', s);
end.

liefert dann Decimal number: 10000000000000000000000000000000000000000000000000 00000000042