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

[Bjoerk]

Zitat von Horst_:

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 von Iwo Asnet:

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

[Dano]

Zitat von Iwo Asnet:

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