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

[Horst_]

Hallo,

wie denn nun?
NetworkSort funktioniert nicht richtig.

Wenn man den Assemblerausschnitt von freepascal ansieht, erkennt man doch, dass erste Vergleich mit dl gemacht und anschliessend mit cl und einer Kopie in CX in DX, was völlig unnötig ist.
Oft kann mand die Asemblerausgabe als Anregung nutzen.

Der Compiler wird aber wohl kaum auf den Trichter kommen, dass es ein 4 Byte Array ist und das er in einem anderen Register verwursten kann und zum Schluss zurückkopiert.

Weniger als sechs Vergleiche, wie soll das gehen:
( EIne anderen Ansatz von mir, nicht fertig ... )
Seien es vier Byte A,B,C,D , Erg = 0;
z.B A,B in AX und C,D in DX

Dann vergleiche A,B -> Carry gesetzt -> B > A ERG Rol 1
Dann vergleiche A,C -> Carry gesetzt -> C > A ERG Rol 1
Dann vergleiche A,D -> Carry gesetzt -> D > A ERG Rol 1

Dann vergleiche B,C -> Carry gesetzt -> C > B ERG Rol 1
Dann vergleiche B,D -> Carry gesetzt -> D > B ERG Rol 1

Dann vergleiche C,D -> Carry gesetzt -> D > C ERG Rol 1

Wenn A,C,B,D die richtige Reihenfolge ist. Bräuchte ich den letzten Vergleich nicht machen, den dort wäre schon bekannt das A das kleinste ist, und C<B<D , aber um zu testen das B zwischen C und D ist brauche ich auch einen Vergleich.

Gruß Horst

[Dano]

@Furtbichler

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
im prinziep ist der networksort ein shell-sort... ich hatte nur die reihenfolge der vergleiche nicht hinbekommen... (siehe mein 1ten post, ist bischen verkehrt^^)

Delphi-Quellcode:

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;

habe jetzt dahingehen auch deine geniale idee mit CX und DX umgesetzt und da jeweils H und L verwendet
das spart mir ein paar mov's und die ganzen ROL und ROR
der tip war wirklich super

Delphi-Quellcode:

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;

mir fällt jetzt auch nix ein um das noch weiter zu optimieren

Code:

:00468578 668B08                  mov cx, word ptr [eax]
:0046857B 668B5002                mov dx, word ptr [eax+02]
:0046857F 38D6                    cmp dh, dl
:00468581 7302                    jnb 00468585
:00468583 86F2                    xchg dl, dh
:00468585 38CD                    cmp ch, cl
:00468587 7302                    jnb 0046858B
:00468589 86E9                    xchg cl, ch
:0046858B 38EE                    cmp dh, ch
:0046858D 7302                    jnb 00468591
:0046858F 86F5                    xchg ch, dh
:00468591 38CA                    cmp dl, cl
:00468593 7302                    jnb 00468597
:00468595 86D1                    xchg cl, dl
:00468597 38EA                    cmp dl, ch
:00468599 7302                    jnb 0046859D
:0046859B 86D5                    xchg ch, dl
:0046859D 668908                  mov word ptr [eax], cx
:004685A0 66895002                mov word ptr [eax+02], dx
:004685A4 C3                      ret

ich Danke euch allen für die hilfe

mfg Dano

[himitsu]

Kennt MMX eigentlich auch Sortierbefehle?

[Bjoerk]

Ob 4, 5 oder 6 Vergleiche, das kann bei 1.000.000 Durchläufen max. 5 Sekunden ausmachen. Wenn nicht, dann hast du in der Tat Äpfel mit Birnen verglichen.

[Aphton]

Nun, wenn du 4 Vergleiche hast, dann sind das bei 1000 -> 4000
Bei 6 Vergleiche sinds 6000...
Das skaliert dementsprechend mit!
Ich würd das also nicht behaupten!

Edit: Außerdem ist es "romantisch", die beste (perfekte) Variante zu finden!

Edit2: #26 - meine Variante darfste nicht mehr testen, sie ist fehlerhaft - siehe dazu #22

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