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

[himitsu]

Das Einzige was falschgemacht wurde, ist die Art der Vergleiche.

Wie schon erwähnt, kannst du keine Äpfel mit Birnen vergleichen.

* entweder man vergleich den Algorithmus

* oder man vergleicht die Speicherverwaltung/Programmierung

Beides zusammen kann nichts werden.


Eins ist schonmal sicher, hier sind auf jeden Fall alle möglichen Schleifen nutzlos (bei den wenigen zu sortierenden Werten), also bleibt von den Algos nur noch die Anzahl und Reihenfolge der Vergleiche/Tauschungen übrig.
Also im Prinzip erstmal überall die selbe Implementierung.


Das ist die Programmierung:

Delphi-Quellcode:

if A[0] > A[1] then begin T:= A[0]; A[0]:= A[1]; A[1]:= T; end;

if A.A[0] < A.A[1] then SwapB(A.A[0], A.A[1]);

SwapIfLess(0, 1);

usw.

Sowas vergleicht man mit jeweils dem selben Algo.


Bubbel-Sort, Selection-Sort oder Network-Sort sind Algorithmen und diese vergleich man jeweils mir der selben Speicherverwaltung.
(also alle Algos mit der selben Zeile, wie oben aufgelistet ... natürlich nur mit anderen Zahlen )


Nur so bekommst du auch vergleichbare Werte raus

und wenn du nun von Beidem jeweils das Schnellste zusammenlegst, dann kommt das bekommst du auch die schnellste Gesamtfunktion raus.

[Furtbichler]

Die Idee von Aphton (in ASM) ist aber insofern schon cool, als dass er komplett auf Array-Zugriffe verzichtet, sondern über ROL-Befehle das nächste zu vergleichende Byte holt.

Könnte man nicht die 4 Bytes in z.B CL/CH und DL/DH kopieren, die 5 Vergleiche durchführen, sodaß die Reihenfolge dann CL/CH/DL/DH oder sonst irgendwie ist) und dann einen 32bit-Wert zusammenbasteln?

[Horst_]

Hallo,

Ich habe mal etwas getestet, wie schnell denn die Programme sind und habe mal mit den 4!=24 möglichen Anordnungen von 1,2,3,4 experimentiert.
Bei falscher Sortierung, also <> 4,3,2,1 wird abgebrochen.
Die Ausgabe ist in CPU Takten.

Code:

Tests mit NetworkSort   2  1   1  2   4  4   3  3
24774777.28
Tests mit D4SortAphton   2  4   1  3   4  2   3  1
24774777.92
Tests mit D4SortByteArray   2  4   1  3   4  2   3  1
24774777.92
Tests mit Selectionsort3up   2  4   1  3   4  2   3  1
24774777.92

Tests mit D4SortByteArray2 Anzahl:10000000
    137.92
Tests mit D4SortByteArray3 Anzahl:10000000
     99.20
Tests mit Selectionsort Anzahl:10000000
     86.08
Tests mit Selectionsort2 Anzahl:10000000
     83.84
Tests mit Selectionsort3Down Anzahl:10000000
     83.52
Tests mit Selectionsort4 Anzahl:10000000
     83.52

Wie man sieht haben manche Proceduren ein erstes Problem mit der Folge 2,4,1,3, ist aber Zufall.

Selectionsort4 ist schon schnell.

Ich finde es merkwürdig, wenn irgendwo Laufzeiten in ms runterfallen und man keinen Bezug zur Anzahl der Durchläufe,Testwerte etc. hat.
Bei immer gleichen Werte betrügt ja die Sprungvorhersage.

Gruß Horst
P:S Die Werte variieren, je nachdem ob der Virenscanner/CPU-Wechsel oder sonstwas dazwischen funkt.

Delphi-Quellcode:

P$TESTVIER_SELECTIONSORT4$BYTEARRAY:
# Temps allocated between esp+0 and esp+0
# Var A located in register eax
# Var T located in register dl
# [146] begin
# [148] if A[0] > A[1] then begin T:= A[0]; A[0]:= A[1]; A[1]:= T; end;
   movb   (%eax),%dl
   cmpb   1(%eax),%dl
   jna   .Lj435
   movb   1(%eax),%cl
   movb   %cl,(%eax)
   movb   %dl,1(%eax)
.Lj435:
# [149] if A[0] > A[2] then begin T:= A[0]; A[0]:= A[2]; A[2]:= T; end;
   movb   (%eax),%cl
   cmpb   2(%eax),%cl
   jna   .Lj443
   movl   %ecx,%edx
   movb   2(%eax),%cl
   movb   %cl,(%eax)
   movb   %dl,2(%eax)
.Lj443:
# [150] if A[0] > A[3] then begin T:= A[0]; A[0]:= A[3]; A[3]:= T; end;
   movb   (%eax),%cl
   cmpb   3(%eax),%cl
   jna   .Lj451
   movl   %ecx,%edx
   movb   3(%eax),%cl
   movb   %cl,(%eax)
   movb   %dl,3(%eax)
.Lj451:
# [151] if A[1] > A[2] then begin T:= A[1]; A[1]:= A[2]; A[2]:= T; end;
   movb   1(%eax),%cl
   cmpb   2(%eax),%cl
   jna   .Lj459
   movl   %ecx,%edx
   movb   2(%eax),%cl
   movb   %cl,1(%eax)
   movb   %dl,2(%eax)
.Lj459:
# [152] if A[1] > A[3] then begin T:= A[1]; A[1]:= A[3]; A[3]:= T; end;
   movb   1(%eax),%cl
   cmpb   3(%eax),%cl
   jna   .Lj467
   movl   %ecx,%edx
   movb   3(%eax),%cl
   movb   %cl,1(%eax)
   movb   %dl,3(%eax)
.Lj467:
# [153] if A[2] > A[3] then begin T:= A[2]; A[2]:= A[3]; A[3]:= T; end;
   movb   2(%eax),%cl
   cmpb   3(%eax),%cl
   jna   .Lj475
   movb   3(%eax),%dl
   movb   %dl,2(%eax)
   movb   %cl,3(%eax)
.Lj475:
# [155] end;
   ret

[Furtbichler]

Gut. Ich gebs auf. Du hast das für dich schnellste Verfahren gefunden.

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

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

[Dano]

Zitat von Horst_:

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 von Horst_:

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
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 von Aphton:

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.


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.