Hilfe: Schnellste möglichkeit ein 4-Byte Array zu Sortieren

[Dano]

ich habe deine function folgendermaßen kopiert

Delphi-Quellcode:

procedure NetworkSort(var A: ByteArray);
  procedure SwapIfLess(i, j: Byte);
  var h: Byte;
  begin
    if a.a[i] > a.a[j] then begin
      h := a.a[i]; a.a[i] := a.a[j]; a.a[j] := h;
    end
  end;
begin
  SwapIfLess(0, 1);
  SwapIfLess(2, 3);
  SwapIfLess(0, 2);
  SwapIfLess(1, 3);
  SwapIfLess(1, 2);
end;

habe dahingehend nur das was nötig war geändert damit es für "Byte" arbeitet
das diese implementierung so langsam ist kann auch am compiler liegen... hatte die letzten 2 tage da sehr komische erfahrungen gemacht... irgendwie bestimmt er selber wann er auf inline umschaltet und den stackrahmen weglässt... ich kann deine function gernene nochmal mit "register" versuchen... aber ansonst war "NetworkSort" immer eine der langsamsten

so wie du sagst ist es eigentlich logisch das 5 vergleiche schneller sind als 6... ich guck noch mal nach wo es hängt

Delphi-Quellcode:

type  
  ByteArray = packed record
    case Integer of
    1: (A: array[0..3] of Byte);
    2: (Card: Cardinal);
  end;
  D4ByteArray = array of ByteArray;
  BA = array[0..3] of Byte;



procedure D4SortByteArray(var A: ByteArray);
var
  Temp: Byte;
  procedure SwapB(var A,B: Byte);
  begin
    Temp:=A;
    A:=B;
    B:=Temp;
  end;
begin
  // Bubbel-Sort
  if A.A[0] < A.A[1] then SwapB(A.A[0],A.A[1]);
  if A.A[1] < A.A[2] then SwapB(A.A[1],A.A[2]);
  if A.A[2] < A.A[3] then SwapB(A.A[2],A.A[3]);
  if A.A[0] < A.A[1] then SwapB(A.A[0],A.A[1]);
  if A.A[1] < A.A[2] then SwapB(A.A[1],A.A[2]);
  if A.A[2] < A.A[3] then SwapB(A.A[2],A.A[3]);
  if A.A[0] < A.A[1] then SwapB(A.A[0],A.A[1]);
  if A.A[1] < A.A[2] then SwapB(A.A[1],A.A[2]);
  if A.A[2] < A.A[3] then SwapB(A.A[2],A.A[3]);
end;

// fehlerhaft... sortiert nicht richtig
procedure D4SortAphton(var A: ByteArray);
var
  Temp: Byte;
  procedure SwapB(var A,B: Byte);
  begin
    Temp:=A;
    A:=B;
    B:=Temp;
  end;
begin
  if A.A[0] < A.A[1] then SwapB(A.A[0], A.A[1]);
  if A.A[2] < A.A[3] then SwapB(A.A[2], A.A[3]);
  if A.A[0] < A.A[2] then
  begin
    SwapB(A.A[0], A.A[2]);
    SwapB(A.A[1], A.A[3]);
  end;
end;

procedure Selectionsort(var A: ByteArray);
  procedure Exchange(const I, J: Cardinal);
  var
    T: byte;
  begin
    T:= A.A[I];
    A.A[I]:= A.A[J];
    A.A[J]:= T;
  end;
begin
  if A.A[0] > A.A[1] then Exchange(0, 1);
  if A.A[0] > A.A[2] then Exchange(0, 2);
  if A.A[0] > A.A[3] then Exchange(0, 3);
  if A.A[1] > A.A[2] then Exchange(1, 2);
  if A.A[1] > A.A[3] then Exchange(1, 3);
  if A.A[2] > A.A[3] then Exchange(2, 3);
end;

procedure Selectionsort2(var A: ByteArray);
var
  T: Byte;
begin
  if A.A[0] > A.A[1] then begin T:= A.A[0]; A.A[0]:= A.A[1]; A.A[1]:= T; end;
  if A.A[0] > A.A[2] then begin T:= A.A[0]; A.A[0]:= A.A[2]; A.A[2]:= T; end;
  if A.A[0] > A.A[3] then begin T:= A.A[0]; A.A[0]:= A.A[3]; A.A[3]:= T; end;
  if A.A[1] > A.A[2] then begin T:= A.A[1]; A.A[1]:= A.A[2]; A.A[2]:= T; end;
  if A.A[1] > A.A[3] then begin T:= A.A[1]; A.A[1]:= A.A[3]; A.A[3]:= T; end;
  if A.A[2] > A.A[3] then begin T:= A.A[2]; A.A[2]:= A.A[3]; A.A[3]:= T; end;
end;

procedure Selectionsort3Down(var B: ByteArray);
var
  T: Byte;
begin
  With B do begin
    if A[0] > A[1] then begin T:= A[0]; A[0]:= A[1]; A[1]:= T; end;
    if A[0] > A[2] then begin T:= A[0]; A[0]:= A[2]; A[2]:= T; end;
    if A[0] > A[3] then begin T:= A[0]; A[0]:= A[3]; A[3]:= T; end;
    if A[1] > A[2] then begin T:= A[1]; A[1]:= A[2]; A[2]:= T; end;
    if A[1] > A[3] then begin T:= A[1]; A[1]:= A[3]; A[3]:= T; end;
    if A[2] > A[3] then begin T:= A[2]; A[2]:= A[3]; A[3]:= T; end;
  end;
end;

procedure Selectionsort3Up(var B: ByteArray);
var
  T: Byte;
begin
  With B do begin
    if A[0] < A[1] then begin T:= A[0]; A[0]:= A[1]; A[1]:= T; end;
    if A[0] < A[2] then begin T:= A[0]; A[0]:= A[2]; A[2]:= T; end;
    if A[0] < A[3] then begin T:= A[0]; A[0]:= A[3]; A[3]:= T; end;
    if A[1] < A[2] then begin T:= A[1]; A[1]:= A[2]; A[2]:= T; end;
    if A[1] < A[3] then begin T:= A[1]; A[1]:= A[3]; A[3]:= T; end;
    if A[2] < A[3] then begin T:= A[2]; A[2]:= A[3]; A[3]:= T; end;
  end;
end;

procedure Selectionsort4(var A: BA);
var
  T: Byte;
begin
    if A[0] > A[1] then begin T:= A[0]; A[0]:= A[1]; A[1]:= T; end;
    if A[0] > A[2] then begin T:= A[0]; A[0]:= A[2]; A[2]:= T; end;
    if A[0] > A[3] then begin T:= A[0]; A[0]:= A[3]; A[3]:= T; end;
    if A[1] > A[2] then begin T:= A[1]; A[1]:= A[2]; A[2]:= T; end;
    if A[1] > A[3] then begin T:= A[1]; A[1]:= A[3]; A[3]:= T; end;
    if A[2] > A[3] then begin T:= A[2]; A[2]:= A[3]; A[3]:= T; end;
end;

procedure D4SortByteArray2(var A: ByteArray);
var
  Temp: Byte;
  procedure SwapB(var A,B: Byte);
  begin
    Temp:=A;
    A:=B;
    B:=Temp;
  end;
begin
  // Bubbel-Sort
  if A.A[0] > A.A[1] then SwapB(A.A[0],A.A[1]);
  if A.A[1] > A.A[2] then SwapB(A.A[1],A.A[2]);
  if A.A[2] > A.A[3] then SwapB(A.A[2],A.A[3]);
  if A.A[0] > A.A[1] then SwapB(A.A[0],A.A[1]);
  if A.A[1] > A.A[2] then SwapB(A.A[1],A.A[2]);
  if A.A[2] > A.A[3] then SwapB(A.A[2],A.A[3]);
  if A.A[0] > A.A[1] then SwapB(A.A[0],A.A[1]);
  if A.A[1] > A.A[2] then SwapB(A.A[1],A.A[2]);
  if A.A[2] > A.A[3] then SwapB(A.A[2],A.A[3]);
end;

procedure D4SortByteArray3(var A: ByteArray);
var
  Temp: Byte;
begin
  // Bubbel-Sort
  if A.A[0] > A.A[1] then begin Temp:=A.A[0]; A.A[0]:=A.A[1]; A.A[1]:=Temp; end;
  if A.A[1] > A.A[2] then begin Temp:=A.A[1]; A.A[1]:=A.A[2]; A.A[2]:=Temp; end;
  if A.A[2] > A.A[3] then begin Temp:=A.A[2]; A.A[2]:=A.A[3]; A.A[3]:=Temp; end;
  if A.A[0] > A.A[1] then begin Temp:=A.A[0]; A.A[0]:=A.A[1]; A.A[1]:=Temp; end;
  if A.A[1] > A.A[2] then begin Temp:=A.A[1]; A.A[1]:=A.A[2]; A.A[2]:=Temp; end;
  if A.A[2] > A.A[3] then begin Temp:=A.A[2]; A.A[2]:=A.A[3]; A.A[3]:=Temp; end;
  if A.A[0] > A.A[1] then begin Temp:=A.A[0]; A.A[0]:=A.A[1]; A.A[1]:=Temp; end;
  if A.A[1] > A.A[2] then begin Temp:=A.A[1]; A.A[1]:=A.A[2]; A.A[2]:=Temp; end;
  if A.A[2] > A.A[3] then begin Temp:=A.A[2]; A.A[2]:=A.A[3]; A.A[3]:=Temp; end;
end;

der compiler überraschte mich auch bei "Selectionsort" nochmal, wenn er ein array von 4 nullen sortieren soll... nur in dem fall war er schneller als meine ASM-implementierung

ich versuch mal morgen deine version mit 5 vergleichen als ASM zu schreiben... sicher kann ich da noch was rausholen an cpu-zeit

mein ASM von SelectionSort... man sieht schon das es 6 vergleiche sind

Delphi-Quellcode:

// Von groß nach klein
procedure SelectionsortASMDown(var A: Cardinal); register;
label Weiter1,Weiter2,Weiter3,Weiter4,Weiter5,Weiter6;
asm
  // In einer asm-Anweisung muss der Inhalt der Register
  // EDI, ESI, ESP, EBP und EBX erhalten bleiben, während die Register
  // EAX, ECX und EDX beliebig geändert werden können.
  mov ECX,[EAX];         // A in ECX
  mov DL,CL;
  rol ECX,8;
  // init fertig
  // if A[0] > A[1] then begin T:= A[0]; A[0]:= A[1]; A[1]:= T; end;
  cmp DL,CL;
  jnb Weiter1;
  xchg DL,CL;
Weiter1:
  // if A[0] > A[2] then begin T:= A[0]; A[0]:= A[1]; A[1]:= T; end;
  rol ECX,8
  cmp DL,CL;
  jnb Weiter2;
  xchg DL,CL;
Weiter2:
  // if A[0] > A[3] then begin T:= A[0]; A[0]:= A[1]; A[1]:= T; end;
  rol ECX,8;
  cmp DL,CL;
  jnb Weiter3;
  xchg DL,CL;
Weiter3:
  // if A[1] > A[3] then begin T:= A[1]; A[1]:= A[2]; A[2]:= T; end;
  rol EDX,8;
  mov DL,CL;
  ror ECX,8;
  cmp DL,CL;
  jnb Weiter4;
  xchg DL,CL;
Weiter4:
  // if A[1] > A[2] then begin T:= A[1]; A[1]:= A[3]; A[3]:= T; end;
  ror ECX,8;
  cmp DL,CL;
  jnb Weiter5;
  xchg DL,CL;
Weiter5:
  // if A[2] > A[3] then begin T:= A[2]; A[2]:= A[3]; A[3]:= T; end;
  rol EDX,8;
  mov DL,CL;
  rol ECX,8;
  cmp DL,CL;
  jnb Weiter6;
  xchg DL,CL;
Weiter6:
  rol EDX,8;
  mov DL,CL;
  mov [EAX],EDX;
end;

im durchschnit ist die 33-40% schneller

Code:

Array: 1,3,2,4 - 16974340

D4SortByteArray
24088,4160 ms
Array: 1,2,3,4 - 16909060

D4SortByteArray2
57394,2310 ms
Array: 4,3,2,1 - 67305985

D4SortByteArray3
32272,7840 ms
Array: 4,3,2,1 - 67305985

NetworkSort
68764,4704 ms
Array: 4,3,2,1 - 67305985

Selectionsort
85959,2935 ms
Array: 4,3,2,1 - 67305985

Selectionsort2
28372,8937 ms
Array: 4,3,2,1 - 67305985

Selectionsort3
27730,2325 ms
Array: 4,3,2,1 - 67305985

Selectionsort4
27905,9789 ms
Array: 4,3,2,1 - 67305985

SelectionsortASM
16776,6932 ms
Array: 4,3,2,1 - 67305985

aso, ich benutze Delphi 7

mfg Dano