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

[Dano]

Zitat von Horst_:

@Dano:
jetzt verrat mir mal wieviel CPU-Takte denn 15287,7931 ms = 1,5287 e10 ns entsprechen?
Wenn Du 2^31-1 Umsortierungen schaffts, sind das 7,118 ns pro Umsortierung.
Meine CPU "macht" 3,2 Ghz ( Phenom II X4 ).
Dann wären das 22,8 CPU-Takte.
Mit meinem rondomisiertem Feld komme ich aber auf knapp 50 CPU-Takte mit der Asm-Version von NetworkSort2 die jetzt auf 72 CPU-Takte, gegenüber 82 mit 6 Vergleichen, kommt.
Ich teste es mal mit immer konstantem Wert.

habe mal mein versuchsaufbau in einfacher form aus allen units zusammenkopiert

Delphi-Quellcode:

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls;

type
  TForm1 = class(TForm)
    Memo1: TMemo;
    Button1: TButton;
    procedure Button1Click(Sender: TObject);
  private
    { Private-Deklarationen }
  public
    { Public-Deklarationen }
  end;

var
  Form1: TForm1;
  gTimer1,gTimer2,gFrequenz: Int64;

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

implementation

{$R *.dfm}

procedure Show1(S: String); overload;
begin
  Form1.Memo1.Lines.Add(S);
end;

procedure Show1(S: String; N: Cardinal); overload;
begin
  Form1.Memo1.Lines.Add(S+IntToStr(N));
end;

procedure StartTimer; overload;
begin
  QueryPerformanceCounter(gTimer1);
  gTimer2:=0;
end;

procedure ShowTimer; overload;
begin
  QueryPerformanceCounter(gTimer2);
  Form1.Memo1.Lines.Add(FormatFloat('0.0000', (gTimer2 - gTimer1) * 1000 / gFrequenz) + ' ms');
  Form1.Memo1.Lines.Add(IntToStr(gTimer2 - gTimer1)+ ' Tick');
end;

procedure Show1(A: ByteArray); overload;
begin
  Show1('Array: '
  +IntToStr(A.A[3])+','
  +IntToStr(A.A[2])+','
  +IntToStr(A.A[1])+','
  +IntToStr(A.A[0])+' - '
  +IntToStr(A.Card));
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 NetworkSort2(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[2] > A[3] then begin T:= A[2]; A[2]:= A[3]; A[3]:= T; end;
    if A[0] > A[2] then begin T:= A[0]; A[0]:= 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[1] > A[2] then begin T:= A[1]; A[1]:= A[2]; A[2]:= T; end;
  end;
end;

// 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;

// Von groß nach klein
procedure SelectionsortASMDown2(var A: Cardinal); register;
label Weiter1,Weiter2,Weiter3,Weiter4,Weiter5;
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 CX,[EAX];
  mov DX,[EAX+$02];
  // init fertig
  // if A[0] > A[1] then begin T:= A[0]; A[0]:= A[1]; A[1]:= T; end;
  cmp DH,DL;
  jnb Weiter1;
  xchg DH,DL;
Weiter1:
  // if A[2] > A[3] then begin T:= A[0]; A[0]:= A[2]; A[2]:= T; end;
  cmp CH,CL;
  jnb Weiter2;
  xchg CH,CL;
Weiter2:
  // if A[0] > A[2] then begin T:= A[0]; A[0]:= A[3]; A[3]:= T; end;
  cmp DH,CH;
  jnb Weiter3;
  xchg DH,CH;
Weiter3:
  // if A[1] > A[3] then begin T:= A[1]; A[1]:= A[2]; A[2]:= T; end;
  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;
  cmp DL,CH;
  jnb Weiter5;
  xchg DL,CH;
Weiter5:
  mov [EAX],CX;
  mov [EAX+$02],DX;
end;

procedure SelectionsortASMDown2Horst(var A: ByteArray); register;
label Weiter3,Weiter4,Weiter5;
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.
 PUSH EAX;
 mov CX,[EAX];
 mov DX,[EAX+$02];
 mov AX,DX // tauscht DL,DH
 Xchg AH,AL //
// init fertig
// if A[0] > A[1] then begin T:= A[0]; A[0]:= A[1]; A[1]:= T; end;
 cmp DH,DL;
 cmovc dx,ax
 mov AX,CX // tauscht CL,CH
 Xchg AH,AL
// if A[2] > A[3] then begin T:= A[0]; A[0]:= A[2]; A[2]:= T; end;
 cmp CH,CL;
 cmovc cx,ax

// if A[0] > A[2] then begin T:= A[0]; A[0]:= A[3]; A[3]:= T; end;
 cmp DH,CH;
 jnb Weiter3;
 xchg DH,CH;
 Weiter3:
// if A[1] > A[3] then begin T:= A[1]; A[1]:= A[2]; A[2]:= T; end;
 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;
 cmp DL,CH;
 jnb Weiter5;
 xchg DL,CH;
 Weiter5:
 POP EAX
 mov [EAX],CX;
 mov [EAX+$02],DX;
end;

procedure SelectionsortASMDown3Horst(var A: ByteArray); register;
label Weiter5;
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.
 PUSH EAX;
 PUSh EBX;
 mov EAX,[EAX];
 MOV BX,AX
 Xchg BH,BL //1 tauscht CL,CH
 
 MOV CX,AX;
 SHR EAX,16;
 MOV DX,AX
 
 Xchg AH,AL //2 tauscht DL,DH

 cmp CH,CL;
 cmovc cx,bx

 cmp DH,DL;
 cmovc dx,ax

 
 Xchg CL,DH; //CX(L,H) : DH,CH ,DX(L,H) : DL,CL

 mov BX,CX
 mov AX,DX

 cmp CL,CH;
 
 Xchg BH,BL // Veraendert Carry nicht
 Xchg AH,AL

 cmovc cx,bx

 cmp DL,DH;
 cmovc dx,ax
 
 Xchg CL,DH; // Zurücktauschen
 
 cmp DL,CH;
 jnb Weiter5;
 xchg DL,CH;
 Weiter5:
 POP EBX
 SHL EDX,16
 MOV DX,CX
 POP EAX
 mov [EAX],EDX;
end;

procedure TForm1.Button1Click(Sender: TObject);
var
  Temp: ByteArray;
  Count, Vaule, MaxRound: Cardinal;
begin
  MaxRound:=$7fffffff;
  Memo1.Clear;

  //Vaule:= $01020304;
  //Vaule:= $02010403;
  //Vaule:= $01030204;
  Vaule:= $01040302; 

  Temp.Card:=Vaule;
  Show1(Temp);
  Show1('MaxRound ',MaxRound);


  Show1('');
  Show1('Selectionsort3Down');
  StartTimer;
  for Count:=0 to MaxRound do begin
    Temp.Card:=Vaule;
    Selectionsort3Down(Temp);
  end;
  ShowTimer;
  Show1(Temp);

  Show1('');
  Show1('NetworkSort2');
  StartTimer;
  for Count:=0 to MaxRound do begin
    Temp.Card:=Vaule;
    NetworkSort2(Temp);
  end;
  ShowTimer;
  Show1(Temp);

  Show1('');
  Show1('SelectionsortASMDown');
  StartTimer;
  for Count:=0 to MaxRound do begin
    Temp.Card:=Vaule;
    SelectionsortASMDown(Temp.Card);
  end;
  ShowTimer;
  Show1(Temp);

  Show1('');
  Show1('SelectionsortASMDown2');
  StartTimer;
  for Count:=0 to MaxRound do begin
    Temp.Card:=Vaule;
    SelectionsortASMDown2(Temp.Card);
  end;
  ShowTimer;
  Show1(Temp);

  Show1('');
  Show1('SelectionsortASMDown2Horst');
  StartTimer;
  for Count:=0 to MaxRound do begin
    Temp.Card:=Vaule;
    SelectionsortASMDown2Horst(Temp);
  end;
  ShowTimer;
  Show1(Temp);

  Show1('');
  Show1('SelectionsortASMDown3Horst');
  StartTimer;
  for Count:=0 to MaxRound do begin
    Temp.Card:=Vaule;
    SelectionsortASMDown3Horst(Temp);
  end;
  ShowTimer;
  Show1(Temp);

end;

initialization
  QueryPerformanceFrequency(gFrequenz);

end.

kurze erklärung
die Form hat nur 1 Button und ein Memo
MaxRound ist die rundenanzahl jedes test's
Vaule ist das array das zum testen genommen wird
das array wird auch immer neu gesetzt in jedem durchlauf
das "Show1" und "StartTimer" sind rudimentäre funktionen damit ich mir nicht jedes mal "Form1.Memo1.Lines.Add" antun muß.... sind in meiner lib die ich einbinde

soweit so gut, hab das wirklich mit vielen sinvollen kombinationen von "Vaule" versucht... aber im schnitt war bis jetzt "SelectionsortASMDown2" der schnellste

optimal müßte ich jetzt noch eine function schreiben wo alle N = 24! versucht werden
aber den ehrgeiz hatte ich noch nicht^^

so wie oben gepostet mit "Vaule:= $01040302;" habe ich auf "Core 2 Duo E8600 @3,33GHz" NICHT übertaktet

Code:

Array: 1,4,3,2 - 17040130
MaxRound 2147483647

Selectionsort3Down
21224,7471 ms
70881316380 Tick
Array: 4,3,2,1 - 67305985

NetworkSort2
25555,0185 ms
85342517680 Tick
Array: 4,3,2,1 - 67305985

SelectionsortASMDown
16764,6979 ms
55986714570 Tick
Array: 4,3,2,1 - 67305985

SelectionsortASMDown2
13761,6837 ms
45957968490 Tick
Array: 4,3,2,1 - 67305985

SelectionsortASMDown2Horst
20686,4956 ms
69083793090 Tick
Array: 4,3,2,1 - 67305985

SelectionsortASMDown3Horst
27085,5254 ms
90453737140 Tick
Array: 4,3,2,1 - 67305985

an deine letzten beiden geposteten ASM-Functionen habe ich "horst" zur erkennung angehängt

da der test als single-thread läuft und ich auch die cpu-auslastungen im auge habe, denke ich nicht das irgendeine hintergrund anwendung großartig einfluss nimmt... den hardware IO mit der festplatte usw beachte ich auch...
ich weiß nicht genau ob dieser alte Core 2 Duo schon runtertaktet bei wärme.... aber so einen Boost (der den takt anhebt kurzzeitig bis das wärme-limit erreicht ist) hat er noch nicht... womit dann die ersten 5 sek mit höherem takt laufen und die erste funktion die ich teste einen vorteil hätte...
soweit zu den dingen die den test verfälschen könnten

horst benutzt den FPC wenn ich richtig gelesen habe.. (PS: die vielen "%"-zeichen in deinem ersten ASM-auszug haben mir angst gemacht^^)
kann natürlich sein das die compiler mit den schleifen unterschiedlichen code erzeugen
aber im verhältniss zueinander sollte wieder alles in etwa richtig sein

auf die sache mit den takte für eine einzelne ASM-anweisung... durch pipeline, branch prediction(Sprungvorhersage) und den cash-pages... bin ich selber nicht mehr im stande eine vorhersage zu treffen welch funktion schneller läuft... also bleibt mir nur testen im sinne des contents in dem die funktion läuft
zu 486er zeiten hatte jeder befehl noch takte die er brauch... glaube seit pentium ist das kein fester wert mit dem man rechnen kann

ok, soweit von mir

TODO: um den test wasserdicht zu machen müßte jede sortierfunktion mit allen 24 kombinationen getestet werden

mfg Dano