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

[BUG]

Zitat:

Zitat von Horst_ (Beitrag 1150448)

Enorm, was ein einziger falscher Sprung kostet, das müssen ja 20 Takte sein.

Tja, im Zweifelsfall muss halt die gesamte Pipeline weggeworfen werden.

[Dano]

Zitat:

Zitat von Horst_ (Beitrag 1150256)

@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

[himitsu]

Delphi-Quellcode:

const 
  Values: array[0..23] of LongWord = (
    $04030201, $03040201, $04020301, $02040301, $03020401, $02030401,
    $04030102, $03040102, $04010302, $01040302, $03010402, $01030402,
    $04020103, $02040103, $04010203, $01040203, $02010403, $01020403,
    $03020104, $02030104, $03010204, $01030204, $02010304, $01020304);

Temp.Card := Vaules[Count mod 24];

Die 64 Bit Befehle sollen wieder mitfesten Takten arbeiten, wenn ich das richtig verstanden hab.

[Horst_]

Hallo,

@dano:
den Quelltext in seiner ganzen "Schönheit" kann man auch anhängen ;-)
Ich habe es auf Lazarus umgemünzt.
Dummy gibt als Funktionswert einfach das richtige Ergebnis zurück, um die Zeit des reinen aufrufens rauszurechnen.
Ich habe die Unit mal angehängt, sollte auch mit Delphi funktionieren, damit Du einen Vergleich starten kannst.

Delphi-Quellcode:

MaxRound 1000000000

Tests mit Dummy
 Anzahl: 1000000000 Ticks: 13437923 ms: 4311,708
Tests mit Selectionsort3Down
 Anzahl: 1000000000 Ticks: 85371524 ms: 27392,338
Tests mit NetworkSort2
 Anzahl: 1000000000 Ticks: 79294972 ms: 25442,618
Tests mit SelectionsortASMDown
 Anzahl: 1000000000 Ticks: 45523858 ms: 14606,808
Tests mit SelectionsortASMDown2
 Anzahl: 1000000000 Ticks: 51604629 ms: 16557,888
Tests mit SelectionsortASMDown2Horst
 Anzahl: 1000000000 Ticks: 44724554 ms: 14350,338
Tests mit SelectionsortASMDown3Horst
 Anzahl: 1000000000 Ticks: 18670531 ms: 5990,638

Wie Du siehst ist meine Variante3 bei mir erheblich schneller, das heisst aber nicht, dass bei Dir andere Varianten nicht noch schneller sind/sein können.

Gruß Horst

P.S.

Delphi-Quellcode:

Temp.Card := Vaules[Count mod 24];

wäre mir zu langsam und zu regelmässig.
Ich habe mal die Testliste/Values auf 24 beschränkt.
In Wahrheit: Weil dann Tests mit SelectionsortASMDown gewinnt ;-)

Delphi-Quellcode:

MaxRound 99999984 ( 1e8 DIV 24 )

Tests mit Dummy
 Anzahl: 99999984 Ticks: 1146723 ms: 367,948.3
Tests mit Selectionsort3Down
 Anzahl: 99999984 Ticks: 5331997 ms: 1710,838.3
Tests mit NetworkSort2
 Anzahl: 99999984 Ticks: 5032214 ms: 1614,648.3
Tests mit SelectionsortASMDown
 Anzahl: 99999984 Ticks: 1316565 ms: 422,438.3
Tests mit SelectionsortASMDown2
 Anzahl: 99999984 Ticks: 2397344 ms: 769,218.3
Tests mit SelectionsortASMDown2Horst
 Anzahl: 99999984 Ticks: 2410761 ms: 773,528.3
Tests mit SelectionsortASMDown3Horst
 Anzahl: 99999984 Ticks: 1563923 ms: 501,808.3

[himitsu]

joar, MOD gefällt mir auch nicht, aber 24 ist soein blöder Wert :cry:

Aber da du ja eh die Aufrufe rausrechnen wolltest, isses doch egal. :mrgreen:

Nur was hast du gegen regelmäßig?

Ob man nun das 24-stel mit dem ersten Wert uws. machen würde, oder die 24 Werte immer hintereinander oder alles unregelmäig durcheinander (könntest ja via Random jeweils einen Wert reisholen), aber so, daß alle Wert gleichmäßig oft vorkommen ... ist doch egal.
Hauptsache es kommen alle Werte vor und jeder bekommt die selben Testdaten.

[Bjoerk]

Also, mit deinen 15 sec. kann was nicht stimmen, hab eben mal meine selectionsort 5 Mio mal durchlaufen lassen. < 0,5 s.

Wie reagiert denn deine aufrufende procedure auf das Onchange von A. Eventuell den Sort dann besser als function?

[Horst_]

Hallo,

wie denn, wo denn, was denn?
0,5 Sekunden für 5e6 Aufrufe sind 100 ns / Aufruf ~ 320 Takte bei mir.
Was soll den mit 15 Sekunden nicht stimmen, zu langsam / zu schnell ?

Ladet doch die unit runter und schaut in den Quelltext.

Delphi-Quellcode:

procedure TLInit;
var
   i : longInt;
begin
  setlength(TL,FeldGroesse);
  randomize;
  TL[0].card := $04030201;
  TL[1].card := $03040201;
  TL[2].card := $04020301;
  TL[3].card := $02040301;
  TL[4].card := $03020401;
  TL[5].card := $02030401;

  TL[6].card := $04030102;
  TL[7].card := $03040102;
  TL[8].card := $04010302;
  TL[9].card := $01040302;
  TL[10].card := $03010402;
  TL[11].card := $01030402;

  TL[12].card := $04020103;
  TL[13].card := $02040103;
  TL[14].card := $04010203;
  TL[15].card := $01040203;
  TL[16].card := $02010403;
  TL[17].card := $01020403;

  TL[18].card := $03020104;
  TL[19].card := $02030104;
  TL[20].card := $03010204;
  TL[21].card := $01030204;
  TL[22].card := $02010304;
  TL[23].card := $01020304;

  For i := 24 to high(TL) do
    TL[i] := TL[random(24)];
end;

Die obere Ausgabe bezieht sich auf 1e9 (= 1e5*1e4) Aufrufe.
Also Runden = 100000 (1e5) mal wird ein High(TL)+1=10000 (1e4)elementiges Testfeld mit zufälligen Werten abgefragt.

Delphi-Quellcode:

  StartTimer;
  For j := 1 to RUNDEN do
  For i := High(TL) Downto 0 do
    begin
    TestWert.Card := TL[i].card;
    Test(TestWert);
    // Prüfen auf Fehler
    IF TestWert.card <> Res then
      begin
      EXIT;
      end;
    end;
  StoppTimer;

Die unter Ausgabe bezieht sich auf 1e8 DIV 24 Aufrufe.
Also Runden = 4'166'666 mal wird ein High(TL)+1=24 elementiges Testfeld mit allen Möglichkeiten abgefragt.

Rein zufällige Werte sind also eine Bremse.

Gruß Horst

[Bjoerk]

Hallo Horst,

ich bezog mich hier auf die in #15 von TE angegeben Rechenzeiten. Sind alle viel zu groß. Deshalb auch meine Frage bezüglich der aufrufenden procedure.

// Edit: Dort gings noch um 5 mill. Durchläufe..

[Horst_]

Hallo,

mit konstantem Wert getestet wie TE Dano un verglichen.
Die Laufzeitunterschiede sind ja gewaltig von der CPU abhängig.
Selbst wenn ich die Dummy-Zeiten draufaddiere, was ja so auch nicht ganz richtig ist, aber auch bei der Anzahl der Durchläufe wohl auch nicht bemerkbar ist, ergeben sich gewaltige Unterschiede, die über die Prozessortaktfrequenzunterschiede von 4% weit hinausgehen.
In Rot AMD x% schneller in schwarz AMD x% langsamer.

http://www.delphipraxis.net/attachme...2&d=1329052892

Gruß Horst

[himitsu]

Mit einem konstanten Wert bevorteilst und benachteilst du bestimmte Algortihmen, welche gerade bei diesem Wert ihre meisten Verleiche und Verschiebeaktionen hätten.
Die Resultate sind also absolut nicht aussafähig, denn schließlich hat du damit ja 95,8333% aller Möglichkeiten ignoriert.

Die Variante vorher ein Array mit Testwerten zu erstellen, hatte ich ja schonmal vorgeschlagen, das würde allen Algorithmen die selben Testwerte geben, ohne sie live zu berechnen.

[Bjoerk]

Horst, kannst du hier mal die asm routinen einbauen und testen? Wenn du mehr als 1 bis 2 Sekunden einsparst, wäre das m.E. schon ziemlich genial.

Delphi-Quellcode:

unit uArrayOfByteList;

interface

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

type
  TArrayOfByte = packed record
    case boolean of
      true: (A: array[0..3] of Byte);
      false: (Card: Cardinal);
  end;

  TArrayOfByteList = class(TList)
  private
    function GetItem(Index: integer): TArrayOfByte;
    procedure SetItem(Index: integer; const Value: TArrayOfByte);
  public
    procedure AddItem(const Value: TArrayOfByte);
    procedure DelItem(Index: integer);
    function Networksort(Index: integer): TArrayOfByte;
    function Selectionsort(Index: integer): TArrayOfByte;
    procedure SelectionsortASM(var A: TArrayOfByte);
    procedure SelectionsortASM2(var A: TArrayOfByte);
    procedure SelectionsortASM2Horst(var A: TArrayOfByte);
    procedure SelectionsortASM3Horst(var A: TArrayOfByte);
    property Item[Index: integer]: TArrayOfByte read GetItem write SetItem; default;
    destructor Destroy; override;
  end;

  TWaitTime = class
  private
    FStartTime: TDateTime;
    FWaitTime: int64;
  public
    procedure Start;
    procedure Stop;
    property WaitTime: int64 read FWaitTime;
  end;

  TForm1 = class(TForm)
    Button1: TButton;
    Button2: TButton;
    Button3: TButton;
    Button4: TButton;
    Button5: TButton;
    Button6: TButton;
    procedure Button1Click(Sender: TObject);
    procedure Button2Click(Sender: TObject);
    procedure FormCreate(Sender: TObject);
    procedure FormDestroy(Sender: TObject);
    procedure Button3Click(Sender: TObject);
    procedure Button4Click(Sender: TObject);
    procedure Button5Click(Sender: TObject);
    procedure Button6Click(Sender: TObject);
  end;

var
  Form1: TForm1;
  ArrayOfByteList: TArrayOfByteList;
  WaitTime: TWaitTime;

implementation

{$R *.dfm}

{ TArrayOfByteList }

function TArrayOfByteList.GetItem(Index: integer): TArrayOfByte;
var
  P: ^TArrayOfByte;
begin
  P:= Items[Index];
  Result:= P^;
end;

procedure TArrayOfByteList.SetItem(Index: integer; const Value: TArrayOfByte);
var
  P: ^TArrayOfByte;
begin
  P:= Items[Index];
  P^:= Value;
end;

procedure TArrayOfByteList.AddItem(const Value: TArrayOfByte);
var
  P: ^TArrayOfByte;
begin
  New(P);
  P^:= Value;
  Add(P);
end;

procedure TArrayOfByteList.DelItem(Index: integer);
var
  P: ^TArrayOfByte;
begin
  P:= Items[Index];
  Dispose(P);
  Delete(Index);
end;

destructor TArrayOfByteList.Destroy;
begin
  while Count > 0 do DelItem(Count-1);
  inherited Destroy;
end;

function TArrayOfByteList.Selectionsort(Index: integer): TArrayOfByte;
  procedure Exchange(const I, J: integer);
  var
    T: byte;
  begin
    T:= Result.A[I];
    Result.A[I]:= Result.A[J];
    Result.A[J]:= T;
  end;
begin
  Result:= Item[Index];
  if Result.A[0] < Result.A[1] then Exchange(0, 1);
  if Result.A[0] < Result.A[2] then Exchange(0, 2);
  if Result.A[0] < Result.A[3] then Exchange(0, 3);
  if Result.A[1] < Result.A[2] then Exchange(1, 2);
  if Result.A[1] < Result.A[3] then Exchange(1, 3);
  if Result.A[2] < Result.A[3] then Exchange(2, 3);
end;

function TArrayOfByteList.Networksort(Index: integer): TArrayOfByte;
  procedure Exchange(const I, J: integer);
  var
    T: byte;
  begin
    T:= Result.A[I];
    Result.A[I]:= Result.A[J];
    Result.A[J]:= T;
  end;
begin
  Result:= Item[Index];
  if Result.A[0] < Result.A[1] then Exchange(0, 1);
  if Result.A[2] < Result.A[3] then Exchange(2, 3);
  if Result.A[0] < Result.A[2] then Exchange(0, 2);
  if Result.A[1] < Result.A[3] then Exchange(1, 3);
  if Result.A[1] < Result.A[2] then Exchange(1, 2);
end;

procedure TArrayOfByteList.SelectionsortASM(var A: TArrayOfByte); assembler;
asm
  //
end;

procedure TArrayOfByteList.SelectionsortASM2(var A: TArrayOfByte); assembler;
asm
  //
end;

procedure TArrayOfByteList.SelectionsortASM2Horst(var A: TArrayOfByte); assembler;
asm
  //
end;

procedure TArrayOfByteList.SelectionsortASM3Horst(var A: TArrayOfByte); assembler;
asm
  //
end;

{ TWaitTime }

procedure TWaitTime.Start;
begin
  FStartTime:= Now;
end;

procedure TWaitTime.Stop;
var
  Hour, Min, Sec, MSec: Word;
begin
  DecodeTime(Now - FStartTime, Hour, Min, Sec, MSec);
  FWaitTime:= MSec + Sec * 1000 + Min * 60000 + Hour * 3600000;
end;

{ TForm1 }

procedure TForm1.Button1Click(Sender: TObject);
var
  I: integer;
  A: TArrayOfByte;
begin
  WaitTime.Start;
  for I:= 0 to ArrayOfByteList.Count-1 do
    A:= ArrayOfByteList.Selectionsort(I);
  WaitTime.Stop;
  ShowMessage('Selectionsort: '+IntToStr(WaitTime.WaitTime)+' ms');
end;

procedure TForm1.Button2Click(Sender: TObject);
var
  I: integer;
  A: TArrayOfByte;
begin
  WaitTime.Start;
  for I:= 0 to ArrayOfByteList.Count-1 do
    A:= ArrayOfByteList.Networksort(I);
  WaitTime.Stop;
  ShowMessage('Networksort: '+IntToStr(WaitTime.WaitTime)+' ms');
end;

procedure TForm1.Button3Click(Sender: TObject);
var
  I: integer;
  A: TArrayOfByte;
begin
  WaitTime.Start;
  for I:= 0 to ArrayOfByteList.Count-1 do
  begin
    A:= ArrayOfByteList[I];
    ArrayOfByteList.SelectionsortASM(A);
  end;
  WaitTime.Stop;
  ShowMessage('SelectionsortASM: '+IntToStr(WaitTime.WaitTime)+' ms');
end;

procedure TForm1.Button4Click(Sender: TObject);
var
  I: integer;
  A: TArrayOfByte;
begin
  WaitTime.Start;
  for I:= 0 to ArrayOfByteList.Count-1 do
  begin
    A:= ArrayOfByteList[I];
    ArrayOfByteList.SelectionsortASM2(A);
  end;
  WaitTime.Stop;
  ShowMessage('SelectionsortASM2: '+IntToStr(WaitTime.WaitTime)+' ms');
end;

procedure TForm1.Button5Click(Sender: TObject);
var
  I: integer;
  A: TArrayOfByte;
begin
  WaitTime.Start;
  for I:= 0 to ArrayOfByteList.Count-1 do
  begin
    A:= ArrayOfByteList[I];
    ArrayOfByteList.SelectionsortASM2Horst(A);
  end;
  WaitTime.Stop;
  ShowMessage('SelectionsortASM2Horst: '+IntToStr(WaitTime.WaitTime)+' ms');
end;

procedure TForm1.Button6Click(Sender: TObject);
var
  I: integer;
  A: TArrayOfByte;
begin
  WaitTime.Start;
  for I:= 0 to ArrayOfByteList.Count-1 do
  begin
    A:= ArrayOfByteList[I];
    ArrayOfByteList.SelectionsortASM3Horst(A);
  end;
  WaitTime.Stop;
  ShowMessage('SelectionsortASM3Horst: '+IntToStr(WaitTime.WaitTime)+' ms');
end;

procedure TForm1.FormCreate(Sender: TObject);
var
  I, J: integer;
  A: TArrayOfByte;
begin
  Randomize;
  WaitTime:= TWaitTime.Create;
  ArrayOfByteList:= TArrayOfByteList.Create;
  for I:= 1 to MaxInt div 32 do
  begin
    for J:= 0 to 3 do
      A.A[J]:= Random(256);
    ArrayOfByteList.AddItem(A);
  end;
end;

procedure TForm1.FormDestroy(Sender: TObject);
begin
  ArrayOfByteList.Free;
  WaitTime.Free;
end;

end.

[Dano]

Delphi-Quellcode:

procedure SelectionsortASMDown(var A: Cardinal); register;

vieleicht kannst du die proceduren mal mit "register" angeben, weil dann der compiler vor dem aufruf der procedur ein LEA (Load Effective Adress) nach EAX macht... und dann sollten die geposteten ASM-Proceduren eigentlich funktionieren

Delphi-Quellcode:

procedure TArrayOfByteList.SelectionsortASM(var A: TArrayOfByte); 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;

hab es selber noch nicht getestet
aber wäre mir jetzt so aufgefallen... nicht das er die var über den stack übergibt

mov ECX,[EAX]; // A in ECX
sagt das er die varieable die an der speicherstelle steht auf die eax zeigt nach ECX kopieren soll... darum [eax]... ist immer eine dereferenzierung so wie bei zeigern/pointern

mfg Dano

[Dano]

@horst

hab deine angehängte zip mal zum laufen gebracht

Code:

MaxRound 100000000

Tests mit Dummy
 Anzahl: 100000000 Ticks: 704506120 ms: 210,968.3
Tests mit Selectionsort3Down
 Anzahl: 100000000 Ticks: 8187710850 ms: 2451,738.3
Tests mit NetworkSort2
 Anzahl: 100000000 Ticks: 7469487830 ms: 2236,678.3
Tests mit SelectionsortASMDown
 Anzahl: 100000000 Ticks: 6598611390 ms: 1975,898.3
Tests mit SelectionsortASMDown2
 Anzahl: 100000000 Ticks: 6523360900 ms: 1953,368.3
Tests mit SelectionsortASMDown2Horst
 Anzahl: 100000000 Ticks: 6242008250 ms: 1869,118.3
Tests mit SelectionsortASMDown3Horst
 Anzahl: 100000000 Ticks: 4513095900 ms: 1351,408.3

ich frag mich jetzt warum deine foo wieder so viel schneller ist^^

[Horst_]

Hallo,

@bjoerk:
In Post 44 ist das doch in der Unit1.zip eingebaut.
Wie dano schrieb, wie er seine Ergebnisse bekam, habe ich ein eine Form1 mit einem Button1 und einem memo1 zusammengeklickt und dann die entstehende unit1 durch diese ersetzt.Dort sind doch die asm Varianten schon drin.

@dano:
Wie ich schon vorher bemerkt habe kann man ab und an durch cmovc Sprünge einsparen.
Wie BUG auch schrieb, kann ein miss"ge"ratener Sprung die ganzen vorgearbeiten Anweisungen (Befehls-pipeline) über den Haufen werfen, dass bedeutet die CPU muss nach dem Sprung von vorne mit der Arbeit beginnen und schon sind 20 Takte weg.
Der Ersatz durch cmov macht aber nur Sinn, wenn der Sprung nicht vorhersagbar, also ohne kurzes Muster, ist.
Ausserdem können die 80586 und später CPUs auf mehrere parallelen Arbeitssträngen arbeiten, wenn man sie lässt.
Beispielsweise:

Delphi-Quellcode:

 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

Der Befehl
MOV BX,AX
Xchg BH,BL //1 tauscht CL,CH
hat bis
cmovc cx,bx
Zeit, ausgeführt zu werden, da sind noch 5 andere Befehle dazwischen.
Die Anordnung der Befehle ist dann von großem Einfluss.

Wenn der Sprung vorhersagbar ist, wenn man zum Beispiel immer den selben Wert verarbeitet, saust die Verarbeitung den richtigen Weg lang, dann ist bei mir asmdown die schnellste Variante, trotz dreier Sprünge.

Mein Bruder hat jetzt einen i5-2500 mit 3,4 Ghz, der hat bei konstanten Wert fast identische Werte wie der Core2 3,33 Ghz von Dir ( Ok skype lief nebenbei, aber das sollten 4 Kernen doch locker schaffen )

Was mich aber wundert, dass die Laufzeit auf Intel und AMD so unterschiedlich sind.
Meist ist doch AMD langsamer.
Bei Dir: 1351 e-3 / 1e8 = 1.351e-8 s pro Aufruf = 1.351e-8 [s]*3,33e9 [Hz] = 45 Cpu Takte.
Ich brauche Anzahl: 2147483646 ms: 14825,648.3 => 14825,64/2147483646*3,2e9 =22 Takte.

Vielleicht hat ja jemand anderer noch eine AMD CPU.
Es kann natürlich sein, dass eine Umstellung der Befehle für die Intel CPU von Vorteil ist.

Zudem könnte man denn letzten Sprung auch noch durch cmovc ersetzen, da die "Strafe" für einen falschen Sprung 20 Takte ist.Bei einer 50/50 Chance der Sprungvorhersage, kann man ruhig noch 8 Takte verbraten

Ich hatte Dir aber schon geschrieben das es mit 6 Vergleichen und der Auswertung des Carry Flags durch eine Sprungtabelle noch schneller sein müsste:

Delphi-Quellcode:

procedure Testvariante(var A: ByteArray);assembler;
{  I  D  C  B  A ECX 
   0  4  3  2  1  63  00111111   ..
   6  4  3  1  2  55  00110111   tausche BA
   2  4  2  3  1  59  00111011   tausche CB
  14  4  1  2  3  35  00100011   tausche CA
  12  4  2  1  3  39  00100111   tausche CA ,BA
   8  4  1  3  2  43  00101011   tausche CB ,BA

   1  3  4  2  1  62  00111110   tausche DC
   4  3  2  4  1  57  00111001   tausche DC ,CB
   7  3  4  1  2  54  00110110   tausche DC ,BA   
  10  3  1  4  2  41  00101001   tausche DC ,BA, DA   
  18  3  2  1  4   7  00000111   tausche DC ,BA, DB
  20  3  1  2  4   3  00000011   tausche DC ,BA, DA

   5  2  3  4  1  56  00111000   
   3  2  4  3  1  60  00111100
  13  2  4  1  3  22  00010110
  16  2  1  4  3   9  00001001
  19  2  3  1  4   6  00000110
  22  2  1  3  4   1  00000001   BSWAP tausche BA


  17  1  2  4  3   8  00001000   BSWAP tausche DC 
  21  1  3  2  4   4  00000100   BSWAP tausche CB
  23  1  2  3  4   0  00000000   BSWAP
   9  1  4  3  2  28  00011100
  11  1  3  4  2  24  00011000
  15  1  4  2  3  20  00010100}
ASM

  PUSH EAX;
  MOV  EAX,Dword PTR [EAX];//  A,B,C,D
  
  MOV  EDX,EAX;        //EDX  A,B ,C,D  DL = A; DH = B
  BSWAP EAX;           //EAX  D,C ,B,A  AL = D; AH = C  
  XOR  ECX,ECX;
    
  CMP  DL,AL;          //A<D  
  RCL  CL,1;
  CMP  DL,AH;          //A<C
  RCL  CL,1;
  CMP  DL,DH;          //A<B
  RCL  CL,1;

  CMP  DH,AH;          //B<C
  RCL  CL,1;
  CMP  DH,AL;          //B<D  
  RCL  CL,1;
  
  CMP  AH,AL;          //C<D
  RCL  CL,1;

  XOR ECX,ECX; // Test
  // Berechneter Sprung
  JMP DWORD PTR [@SprungTabelle+4*ECX]

@L0:
  POP EAX;  
  MOV Dword Ptr[EAX],EDX;
  Ret;
@L1:;//
@L3:;//
//.....
@L63:;//....

@Sprungtabelle:
  DD  @L0,@L1,0,@L3
 .....
end;

Gruß Horst.

[Bjoerk]

Zitat:

Zitat von Horst_ (Beitrag 1150677)

Hallo,

@bjoerk:
In Post 44 ist das doch in der Unit1.zip eingebaut.

Die laufen nicht...

[Horst_]

Hallo,

anbei die Konsolenversion.Ich habe hier alternativ nur Lazarus am Werk.
Gruß Horst

[Bjoerk]

Hallo Horst,

mir das ja eigentlich wurscht, weil dieser Thread mit dem Netorksort von Furtbichler eh schon lange gelöst ist. Auch ist Delphi nicht gerade dafür bekannt, mit Integers langsam zu sein. Bau' halt mal die asm’s in eine echte Testsituation ein (wie z.B. meine von oben), dann wirst du nur sehr geringe Unterschiede in den Rechenzeiten erhalten und auch feststellen, daß die asm’s so manches Speicherloch produzieren, was sich spätestens beim Close der Form, wenn TList.Free ausgeführt wird, zeigt.

Viele liebe Grüße
Thomas

[Horst_]

Hallo,

Ja, die Sache ist schon lange durch Furtbichler gelöst.

Jetzt geht es doch nur noch um etwas Fantasie und Ehrgeiz ;-)

Aber es ging doch dano darum zu wissen, warum die Asm Varianten so unterschiedlich schnell bei zufälligen Daten sind.
Zumal auf dano's Core2 ist der Unterschied bei zufälligen Daten recht groß
1e8 Aufrufe:
2236,67 (Networksort2) zu 1351,40 (ASM Version 3 ), -> asm wesentlich schneller
bei einem konstanten Wert Daten war es ja
DWord(1 shl 31)-1 = MaxInt Aufrufe
25550 (Networksort2) zu 27085 (ASM Version 3 ). asm etwas langsamer


Ich weiß jetzt nicht, wo ich Speicherlöcher erzeuge, wo ich doch keinen Speicher in den ASM Routinen anfordere.
Erstelle doch auch eine Konsolen-Variante, warum soll ich jetzt irgendwelche Buttons auf einem Formular erzeugen, die dann nur in Lazarus kompilieren.
Es geht doch nur um den Algorithmus und dessen Umsetzung.
Das ist kompakt, auch als EXE und wesentlich portabler.

Gruß Horst
P.S.:
Hast Du meine Variante im Post zuvor ans laufen bringen können und wie waren dann Deine Erbegnisse?

[Horst_]

Hallo,

so eine Erkältung macht wohl wirr...
In Beitrag #26 habe ich die Assemblerausgabe angehängt gehabt, aua, da kann ja niemand etwas mit anfangen.

@Bjoerk:
Warum funktioneren die Assembler Varianten bei Dir nicht?
Nach etwas suchen, habe ich es gefunden.
Weil du eine Klasse von TList genommen hast und dort auch die Funktionen definiert hast.

Code:

 Var A located in register edx
# Var $self located in register eax !

Jetzt sind alle Assembler-Versionen davon ausgegangen, dass der Zeiger auf A in EAX steht, jetzt wird aber innerhalb der Klasse "self" in EAX übergeben.
Scheinbar habe ich falsch herum sortiert, ein BSWAP beseitigt das auf die Schnelle.

Wie himitsu schon angedeutet hat, kann man durch ganz andere Dinge die Performance so verschlechtern, das eine geschickte Sortierung völlig untergeht.

Wenn networkSort2 2236,67 ms für 1e8 Elemente/LongInt braucht sind dass 4*1e2/2,23667 = 178 MByte/s also noch gerade so schneller als eine heutige Festplatte.

miT tList statt eines einfachen Feldes sind die Zeiten sowieso egal.
Für 1e7 Werte ergab sich:

Code:

Erstellen der Werte: 1459 ms
DummySort: 188 ms
Selectionsort: 625 ms
Networksort: 601 ms
SelectionsortASM: 342 ms
SelectionsortASM2: 346 ms
SelectionsortASM2Horst: 328 ms
SelectionsortASM3Horst: 267 ms
Drücken Sie eine beliebige Taste . . .

Wenn der Zugriff auf die Daten schon DummySort: 188 ms dauert , geht der Rest darin unter.
SelectionsortASM3Horst: 267 ms-188 ms = 79 ms für das Sortieren.

Gruß Horst
P.S.
In Testvier halte ich die Datenmenge mit 32767 Elementen recht klein, es werden eben entsprechend viele Runden gemacht.
Ein dynamisches Array hätte 380 MByte gebraucht.

Das Anlegen einer Liste von 1e8 Werten braucht 2 GB an Platz und ist etwas zeitaufwändig.

Code:

Erstellen der Werte: 14684 ms
DummySort: 1828 ms
Selectionsort: 6188 ms
Networksort: 5994 ms
SelectionsortASM: 3425 ms
SelectionsortASM2: 3428 ms
SelectionsortASM2Horst: 3172 ms
SelectionsortASM3Horst: 2627 ms

[Iwo Asnet]

Lustig, wenn man das hier noch einbaut

Delphi-Quellcode:

procedure TArrayOfByteList.Networksort2(var A: TArrayOfByte); register;
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[2] < A.A[3] then begin T:=A.A[2]; A.A[2] := A.A[3]; A.A[3] := 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[1] < A.A[3] then begin T:=A.A[1]; A.A[1] := 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[3] := T end;
end;

Und die Testroutine nach Button2Click aufruft, werden alle folgenden Aufrufe langsamer, packt man den letzten Aufruf an 2.Stelle ist der plötzlich langsamer. Kann es sein, das die CPU sich vielleicht auch warmlaufen muss und diese Tests eh für'n Arm sind?

Mich wundert sowieso, wieso ihr immer dieses 'SelectionSort' optimiert, anstatt den o.g. Code.

Weiterhin sieht es interessant aus, wenn man das TEST-AND-Exchange 'Macro' noch optimiert. Siehe hier ganz unten.

Andere Quellen probieren SSE2-Instruktionen. Bringt das was? Habe ja selbst keine Ahnung von ASM.

[Horst_]

Hallo,

ja, die CPU muss er warm laufen/auf de höhere Taktzahl gebracht werden.
Dass sollte Init oder Formcreate aber schon vollbracht haben.

Soweit ich das sehe, benutzen doch alle ASM-Versionen maximal 5 Tauschungen.
und die ASM Version von NetworkSort2, der Name ist einfach falsch gewählt.
Ich habe es einfach von dano kopiert und dann schrittweise geändert.

Vielleicht kannst Du , Asnet, und andere testvier.zip mal testen und Deine Ergebnisse nennen.

Vielleicht ist TList in Delphi wesentlich schneller implementiert, mit freepascal ist es extrem langsam.
Ein Test mit einem Durchlauf mit einem Feld mit 10e8 Elementen ist genauso schnell wie 3052 mal ein Feld von 32767 Elementen:

Code:

MaxRound 100000000

Tests mit Dummy
 Anzahl: 100000000 Ticks: 1064477 ms:  341,550
Tests mit Selectionsort3Down
 Anzahl: 100000000 Ticks: 9227711 ms: 2960,816
Tests mit NetworkSort2
 Anzahl: 100000000 Ticks: 8071028 ms: 2589,681
Tests mit SelectionsortASMDown
 Anzahl: 100000000 Ticks: 5225017 ms: 1676,506
Tests mit SelectionsortASMDown2
 Anzahl: 100000000 Ticks: 5861757 ms: 1880,811
Tests mit SelectionsortASMDown2Horst
 Anzahl: 100000000 Ticks: 5068068 ms: 1626,147
Tests mit SelectionsortASMDown3Horst
 Anzahl: 100000000 Ticks: 2251951 ms:  722,564

An den angegeben Links wird ja ein Feld von 6 Longint in 31.24 Takten sortiert.
Aber das ist auf einer 64-Bit Maschine getestet, da gibt es ja viel mehr freie Register.

MMX oder SSE Versionen wären vielleicht auch interessant.
Eigentlich frage ich mich nur, wozu man das braucht ;-)

Gruß Horst

[himitsu]

Zitat:

Zitat von Iwo Asnet (Beitrag 1151071)

Und die Testroutine nach Button2Click aufruft, werden alle folgenden Aufrufe langsamer, packt man den letzten Aufruf an 2.Stelle ist der plötzlich langsamer. Kann es sein, das die CPU sich vielleicht auch warmlaufen muss und diese Tests eh für'n Arm sind?

Siehe Kommmentar in Antwort #37

[Horst_]

Hallo,

das erstellen der zufälligen Werte in der Liste dauert doch 1400 ms, bis dahin ist wohl jede CPU auf die höchste Taktzahl hochgefahren.
Ich kann die unterschiedlichen Zeiten nicht bestätigen.Ich habe die Routinen mal richtig umbenannt.
Natürlich sind die Werte nicht festgenagelt und schwanken bei jedem Durchlauf:
Networksort: 594 ms-> Networksort: 578 ms Aber kann ja alles mögliche dazwischen gekommen sein, bei einer so "langen" Laufzeit.
Aber die anderen Laufzeiten sind erschreckend konstant.

Code:

Ausgabe auf AMD Phenom X4 II 3,2 Ghz 
 
Erstellen der Werte: 1421 ms
 
1.ter Durchgang
DummySort: 188 ms
Selectionsort: 609 ms
Ntworksort2: 422 ms
Networksort: 594 ms
SelectionsortASM: 328 ms
NetworkSortASM2: 344 ms
NetworkSortASM2Horst: 312 ms
NetworkSortASM3Horst: 250 ms

2.ter Durchgang
DummySort: 188 ms
Selectionsort: 625 ms
Networksort: 578 ms
SelectionsortASM: 328 ms
NetworkSortASM2: 343 ms
NetworkSortASM2Horst: 313 ms
NetworkSortASM3Horst: 250 ms
Ntworksort2: 422 ms

Gruß Horst

[Furtbichler]

Wieso testet ihr eigentlich immer noch Birnen und Äpfel? Die Signaturen der Prozeduren sollten identisch sein, sind sie aber nicht.

Delphi-Quellcode:

function Selectionsort(Index: integer): TArrayOfByte;
// vs.
procedure Networksort2(var A: TArrayOfByte); register;
// vs.
procedure NetworksortASM(var A: TArrayOfByte); assembler;

Macht den Kohl nicht fett, ist aber unschön.

[Horst_]

Hallo,

schlimm! Das habe ich doch kritiklos von Bjoerk's Vorgabe übernommen.
Natürlich macht es was aus, ob in dummy der Wert A vorher belegt ist oder erst innnerhalb der Funktion.( Zugriff auf Klasse-> Tlist ->dort das Element mit Zeiger auf den Wert ->und dann den Wert holen )

Code:

Erstellen der Werte: 1437 ms
...
2.ter Durchgang
DummySort: 187 ms
Selectionsort: 549 ms , zuvor Selectionsort: 609 ms,625 ms
Networksort: 516 ms, zuvor Networksort: 594 ms,578 ms
SelectionsortASM: 357 ms
NetworkSortASM2: 340 ms
NetworkSortASM2Horst: 328 ms
NetworkSortASM3Horst: 250 ms
Ntworksort2: 422 ms

Aber was soll es. Dank TList kann man es sowieso in die Tonne treten.Es geht hier um 10e7 Werte. Bei mir dauert also allein der Zugriff auf ein Tlist-Element innerhalb der Funktion etwa 70ms/1e7*3,2e9 ~ 22 Takte.
Die proceduren sind hier nicht schneller oder langsamer als bei TestVier.pas.

Gruß Horst

[Bjoerk]

Zitat:

Zitat von Horst_ (Beitrag 1151141)

Hallo,

schlimm! Das habe ich doch kritiklos von Bjoerk's Vorgabe übernommen.
Gruß Horst

Horst, das hast du mit Sicherheit nicht von mir übernommen. :?

BTW, wenn du etwas postest, dann nenn die Dateien bitte ncht Bjoerk*.zip. Danke. :evil:

Zusammenfassung: Von mir: #8 #51, Nicht von mir: Bjoerk*.zip

[Horst_]

Hallo,

Die Variante mit Sprungtabelle ist fertig.
Die braucht bei mir 38 Takte, ein JMP bremst enorm.
Das wäre gegenüber ASM3, mit durchschnittlich 32 Takte, langsamer.
Vielleicht wäre es für INTEL Chips, da bei Dano Core2 die schnellste Version ASM3 45 Takte braucht.
Ich habe die Gesamtzeit angeben. Die Overhead braucht ja immer, ausser man schafft es inline, was bei meinem Test so nicht ging.

Gruß Horst

Code:

MaxRound 100004884 , F_CPU =  3.2 Ghz

Tests mit Dummy/ Overhead des Aufrufs
 Anzahl: 100004884 t   224,092 ms:    7,171 CPU-Takte
Tests mit Selectionsort3Down
 Anzahl: 100004884 t  3008,814 ms:   96,277 CPU-Takte
Tests mit NetworkSort2
 Anzahl: 100004884 t  2597,955 ms:   83,130 CPU-Takte
Tests mit NetworkSortAsmDown
 Anzahl: 100004884 t  1795,201 ms:   57,444 CPU-Takte
Tests mit NetworkSortAsmDown2
 Anzahl: 100004884 t  1841,396 ms:   58,922 CPU-Takte
Tests mit NetworkSortAsmDown2Horst
 Anzahl: 100004884 t  1548,641 ms:   49,554 CPU-Takte
Tests mit NetworkSortAsmDown3
 Anzahl: 100004884 t   989,808 ms:   31,672 CPU-Takte
Tests mit SORTSprungTabelle
 Anzahl: 100004884 t  1194,537 ms:   38,223 CPU-Takte

[Dano]

Zitat:

Zitat von Iwo Asnet (Beitrag 1151071)

Und die Testroutine nach Button2Click aufruft, werden alle folgenden Aufrufe langsamer, packt man den letzten Aufruf an 2.Stelle ist der plötzlich langsamer. Kann es sein, das die CPU sich vielleicht auch warmlaufen muss und diese Tests eh für'n Arm sind?

ja solche ergebnisse hatte ich auch... denke das es dann an dem memorymanager von meinem D7 liegt... mußte aus dem grund einige sachen extrem umbauen um ernsthaft vergleichbare ergebnisse zu erhalten

mfg Dano

[Dano]

@Horst
da sind einige interessante dinge in deinen letzten beiträgen, also was die laufzeit optimiert (bzw könnte)
ich habe mit meinen tests erstmal abgeschlossen
durch die hilfe von euch konnte ich die zeit im verhältniss von 5:1 kürzen :)
nach bischen mehr als 24h war der rechner fertig... aber leider war das ergebniss nicht so wie gehofft^^
also neue idee muß her^^

mfg Dano