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

[Delphi-Laie]

Zitat von Dano:

ich habe heute dein networksort noch mal überarbeitet, so wie du schon gepostet hattest, und natürlich ist er schneller. ca. 10-20% gegenüber dem Selectionsort3

Wen (ver)wundert das? Mich jedenfalls nicht!

Zitat von Dano:

im prinziep ist der networksort ein shell-sort...

Richtig, und das verlinkte Bild zeigt eines mit der (ungünstigen) Indexabstandsfolge: 2,4,8.....

Shellsort fällt als günstiger Sortieralgorithmus aus. Bei so wenigen Elementen fallen allerdings die Sortieralgorithmen immer mehr zusammen, so daß man einen ohne Kenntnis der Sortieralgorithmen entwerfen kann, indem man alle Vergleiche und optionalen (Ver)Tauschungen expliziert und in die richtige Reihenfolge bringt.

Furtbichlers Idee gefiel mir jedenfalls seit Anbeginn am besten, er/sie verteitigte diese Idee m.E. auch am plausibelsten.

[Horst_]

Hallo,

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

Gruß Horst
Bei mir braucht die ASM Variante von Network2 mit konstantem Wert /*TestArr.Card := $01030204;*/
28 Takte und die Pascal Variante 59 Takte.
Bei einem randomisierten Feld sind 60 zu 82 Takte.
Also bringt die Sprungvorhersage recht viel.

[himitsu]

Zum Testen ein Array of ByteArray nehmen, mit unsterschiedlichen und Kombinationen befüllen (alle Möglchen).
Und dann alle Testes immer auf die selben Daten loslassen.

dynamische Arrays kann man oftmals mit Copy (ohne) Längenangabe kopieren.

Wie sieht denn dein Testumfelt aktuell aus?

Entweder das Array mit Zufallszahlen befüllen (*1) oder einfach hintereinander unsotiert alle möglichen Kombinationen.
1: Natürlich beachten, daß 1 bis 4 jeweils nur einmal vorkommen.
So, jetzt hätte man ein vergleichbares Umfelt geschaffen.

Delphi-Quellcode:

procedure BubbleSort(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[1] > A[2] then begin T:= A[1]; A[1]:= A[2]; A[2]:= T; end;
    if A[2] > A[3] then begin T:= A[2]; A[2]:= A[3]; A[3]:= T; end;
    if A[0] > A[1] then begin T:= A[0]; A[0]:= A[1]; A[1]:= T; end;
    if A[1] > A[2] then begin T:= A[1]; A[1]:= A[2]; A[2]:= T; end;
    if A[2] > A[3] then begin T:= A[2]; A[2]:= A[3]; A[3]:= T; end;
    if A[0] > A[1] then begin T:= A[0]; A[0]:= A[1]; A[1]:= T; end;
    if A[1] > A[2] then begin T:= A[1]; A[1]:= A[2]; A[2]:= T; end;
    if A[2] > A[3] then begin T:= A[2]; A[2]:= A[3]; A[3]:= T; end;
  end;
end;

procedure NetworkSort(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;

procedure z;
var
  X, Y: array of ByteArray;
  i:    Integer;
begin

  //XXX befüllen

  // einfach nur irgendwas machen, um dynamisch getacktete CPUs hochzufahren
  X := Copy(XXX);  // X := XXX; kann man vergessen, wegen eine echt blöden Laufzeitoptimeren seitens Borland/Codeegear/Embarcadero :wall:
  for i := High(X) downto 0
    NetworkSort(X[i]);

  X := Copy(XXX);
  // start merken
  for i := High(X) downto 0
    BubbleSort(X[i]);
  // zeit berechnen

  X := Copy(XXX);
  // start merken
  for i := High(X) downto 0
    NetworkSort(X[i]);
  // zeit berechnen

  ...

end;

[Horst_]

Hallo,

das Testumfeld habe ich ja schon geschaffen gehabt.
http://www.delphipraxis.net/1149984-post26.html TestVier.zip

Bei der Assembler Variante müsste man noch die Sprünge vermeiden.
Mit cmovc geht es ja zu Beginn.
Das spart bei randomisierten Daten etwa 9 Takte.
Vielleicht müsste man dan DX,CX zusammenfassen 'DL,DH'+'CH,CL'(<-xchg) und dann um ein byte schieben und in 'DH,CH' + 'CL,DL' wieder aufteilen.

Delphi-Quellcode:

procedure SelectionsortASMDown2(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;

end;
[/DELPHI]

[Furtbichler]

Zur Information: Der 'Network sort' bedient sich dem minimalen Netzwerk, um 4 Elemente zu sortieren. Die Aufgabe ist nicht trivial, denn sie besteht darin die minimale Anzahl von Vergleichen bei gleichzeitig maximaler Parallelität zu ermitteln. Interessanterweise sind nur für N<=10 optimale Netzwerke bekannt.

Daraus ergibt sich dann ein Netzwerk (daher der Name), das aus N Leitungen sowie M Vergleichsbausteinen besteh. Ein Vergleichsbaustein hat jeweils 2 Ein- und Ausgänge. Wird der Eingang mit (A B) beschaltet und ist A>B, steht am Ausgang (B A) an.

Anwendung finden diese Netzwerke u.a. in GPU-Hardware.

Der Shellsort -mit den richtigen Gaps- liefert hier auch 5 Vergleiche und ein ähnliches Netzwerk.

[Horst_]

Hallo,

Diese Parallelität hat ja auch auf der CPU Vorteile, da Teile
auf die verschiedenen mehrfach vorhandenen Arbeiteinheiten verteilt werden können.

Jetzt habe ich noch einen Sprung drin und die anderen durch CMOV ersetzt.
Das bringt eine Verlangsamung bei einem immer konstanten Wert , aber eine erhebliche Beschleunigung bei zufälligen werten.
Momentan ~35 Takte für immer gleichen Wert und ~42 für zufällige Daten.
Zuvor: SelectionsortASMDown2
--Bei einem konstanten Feld 28 Takte
--Bei einem randomisierten Feld 60 Takte.

Lasse ich jetzt weg..siehe unten Vielleicht sollte man EBX zusätzlich nutzen und dort DX bearbeiten.

Gruß Horst
EDIT:
Ich hatte mal im Hinterkopf, dass AMD-Chips es einem unheimlich übel nehmen, wenn man im Speicher/Cache auf DWOrd Daten plötzlich word-mäßig zugreift.
Das scheint zu stimmen.

Delphi-Quellcode:

procedure SelectionsortASMDown3(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;

Jetzt sind es:
~14 Takte für ein konstanten Wert und
~24 Takte für randomisierte Werte, gegenüber 60 schon eine Verbesserung.
Enorm, was ein einziger falscher Sprung kostet, das müssen ja 20 Takte sein.
Es sind 31 Assemblerbefehle, da ist doch eine gewisse parallele Verarbeitung am Werk.

[BUG]

Zitat von Horst_:

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

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

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