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

[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

[Dano]

Zitat:

Zitat von Horst_ (Beitrag 1150075)

Hallo,

wie denn nun?
NetworkSort funktioniert nicht richtig.

NetworkSort funktioniert einwandfrei, nur die variante von Aphton war irgendwie komisch, ich hatte auch das ergebniss das unter bestimmten kombinationen seine funktion nicht richtig sortiert hatte
aber ich fand das nicht schlimm, immerhin war er so freundlich und hat mit viel aufwand versucht mir zu helfen ;) Danke an Aphton :)

Zitat:

Zitat von Horst_ (Beitrag 1150075)

Weniger als sechs Vergleiche, wie soll das gehen:

http://http://psycnet.apa.org/journals/bul/101/2/images/bul_101_2_304_fig2a.gif

hab jetzt kein besseres bild gefunden
aber ich hoffe man erkennt das man bei 4 werten nur 5 vergleiche braucht
und ich konnte es auch nicht gleich umsetzen obwohl das bild soooo einfach aussieht^^

@himitsu
ja, bei MMX gibt es auch vergleiche, aber sehr spartanisch wie ich im wiki sehe^^
http://de.wikipedia.org/wiki/Multi_M...on#Befehlssatz

@Bjoerk
ich hatte vor ein array von fast 2gigabyte(entspricht 5mio von den 4 byte arrays).. so zu sortieren und anschließend zu testen...
ist ein experiment^^
über sinn und unsinn der sache kann man sich streiten ;)
aber ob ich jetzt 10min warte oder 20min warte.. ist für mich schon wichtig
und gerade weil diese sortier-funktion so oft aufgerufen wird, wollte ich sie gerne so gut es geht minimieren
nur als beispiel

Code:

D4SortByteArray2
60876,6357 ms

NetworkSort2
23103,1530 ms

Selectionsort3Down
24522,5872 ms

SelectionsortASM
16770,3178 ms

SelectionsortASM2
15287,7931 ms

60 sek war mein erster versuch... jetzt bin ich bei 15sek angelangt... die steigerung ist enorm... 4 Jahre warten oder nur 1 Jahr :D
dieser test war mit Array: 1,3,2,4 statisch das nach 4,3,2,1 umsortiert wird... (MaxRound:=$7fffffff; =2,14mrd schleifendurchläufe)
je nach algorythmus und array sind die funktionen unterschiedlich schnell, aber ich würde das so erstmal als vorläufige verbesserung bezeichnen
das ist jetzt nur ein test, aber andere array-kombinationen verändern im grunde nichts am gesamten ergebniss der laufzeiten
wollte damit nur mal den grund meiner hilfesuche erläutern ;)

mfg Dano

ps:

Zitat:

Zitat von Aphton (Beitrag 1150202)

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

ja da hast du recht, das ist spannender als alles andere :)

[himitsu]

Bjoerk bezog sich jetzt nur auf den Algo (vermute ich mal).
Ob es nun 15 oder 16 Sekunden dauert, je nach Algo, ist nun kein großer Unterschied. Gegenüber den 60 ist Beides viel schneller.

Bei der restliche Zeit, für das Holen der Daten und für die sonstigen Verarbeitungen ... ob dazu im Verhältnis die paar Millisekunden auffallen, das spielt ja auch noch eine Rolle. :zwinker:


Zum Glück sind hier die Optimierungen, durch einen anderen Algorithmus keine große Angelegenheit, aber ansonsten sollte man eben auch noch abwägen, ob eine Optimierung insgesamt wirklich einen Vorteil mit sich bring.

[Delphi-Laie]

Zitat:

Zitat von Dano (Beitrag 1150187)

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:

Zitat von Dano (Beitrag 1150187)

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

Delphi-Quellcode:

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.

Delphi-Quellcode:

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.