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

[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

[Horst_]

Hallo,

das erstellen der zufälligen Werte in der Liste dauert doch 1400 ms, bis dahin ist wohl jede CPU auf die höchste Taktzahl hochgefahren.
Ich kann die unterschiedlichen Zeiten nicht bestätigen.Ich habe die Routinen mal richtig umbenannt.
Natürlich sind die Werte nicht festgenagelt und schwanken bei jedem Durchlauf:
Networksort: 594 ms-> Networksort: 578 ms Aber kann ja alles mögliche dazwischen gekommen sein, bei einer so "langen" Laufzeit.
Aber die anderen Laufzeiten sind erschreckend konstant.

Code:

Ausgabe auf AMD Phenom X4 II 3,2 Ghz 
 
Erstellen der Werte: 1421 ms
 
1.ter Durchgang
DummySort: 188 ms
Selectionsort: 609 ms
Ntworksort2: 422 ms
Networksort: 594 ms
SelectionsortASM: 328 ms
NetworkSortASM2: 344 ms
NetworkSortASM2Horst: 312 ms
NetworkSortASM3Horst: 250 ms

2.ter Durchgang
DummySort: 188 ms
Selectionsort: 625 ms
Networksort: 578 ms
SelectionsortASM: 328 ms
NetworkSortASM2: 343 ms
NetworkSortASM2Horst: 313 ms
NetworkSortASM3Horst: 250 ms
Ntworksort2: 422 ms

Gruß Horst

[Furtbichler]

Wieso testet ihr eigentlich immer noch Birnen und Äpfel? Die Signaturen der Prozeduren sollten identisch sein, sind sie aber nicht.

Delphi-Quellcode:

function Selectionsort(Index: integer): TArrayOfByte;
// vs.
procedure Networksort2(var A: TArrayOfByte); register;
// vs.
procedure NetworksortASM(var A: TArrayOfByte); assembler;

Macht den Kohl nicht fett, ist aber unschön.

[Horst_]

Hallo,

schlimm! Das habe ich doch kritiklos von Bjoerk's Vorgabe übernommen.
Natürlich macht es was aus, ob in dummy der Wert A vorher belegt ist oder erst innnerhalb der Funktion.( Zugriff auf Klasse-> Tlist ->dort das Element mit Zeiger auf den Wert ->und dann den Wert holen )

Code:

Erstellen der Werte: 1437 ms
...
2.ter Durchgang
DummySort: 187 ms
Selectionsort: 549 ms , zuvor Selectionsort: 609 ms,625 ms
Networksort: 516 ms, zuvor Networksort: 594 ms,578 ms
SelectionsortASM: 357 ms
NetworkSortASM2: 340 ms
NetworkSortASM2Horst: 328 ms
NetworkSortASM3Horst: 250 ms
Ntworksort2: 422 ms

Aber was soll es. Dank TList kann man es sowieso in die Tonne treten.Es geht hier um 10e7 Werte. Bei mir dauert also allein der Zugriff auf ein Tlist-Element innerhalb der Funktion etwa 70ms/1e7*3,2e9 ~ 22 Takte.
Die proceduren sind hier nicht schneller oder langsamer als bei TestVier.pas.

Gruß Horst

[Bjoerk]

Zitat von Horst_:

Hallo,

schlimm! Das habe ich doch kritiklos von Bjoerk's Vorgabe übernommen.
Gruß Horst

Horst, das hast du mit Sicherheit nicht von mir übernommen.

BTW, wenn du etwas postest, dann nenn die Dateien bitte ncht Bjoerk*.zip. Danke.

Zusammenfassung: Von mir: #8 #51, Nicht von mir: Bjoerk*.zip

[Horst_]

Hallo,

Die Variante mit Sprungtabelle ist fertig.
Die braucht bei mir 38 Takte, ein JMP bremst enorm.
Das wäre gegenüber ASM3, mit durchschnittlich 32 Takte, langsamer.
Vielleicht wäre es für INTEL Chips, da bei Dano Core2 die schnellste Version ASM3 45 Takte braucht.
Ich habe die Gesamtzeit angeben. Die Overhead braucht ja immer, ausser man schafft es inline, was bei meinem Test so nicht ging.

Gruß Horst

Code:

MaxRound 100004884 , F_CPU =  3.2 Ghz

Tests mit Dummy/ Overhead des Aufrufs
 Anzahl: 100004884 t   224,092 ms:    7,171 CPU-Takte
Tests mit Selectionsort3Down
 Anzahl: 100004884 t  3008,814 ms:   96,277 CPU-Takte
Tests mit NetworkSort2
 Anzahl: 100004884 t  2597,955 ms:   83,130 CPU-Takte
Tests mit NetworkSortAsmDown
 Anzahl: 100004884 t  1795,201 ms:   57,444 CPU-Takte
Tests mit NetworkSortAsmDown2
 Anzahl: 100004884 t  1841,396 ms:   58,922 CPU-Takte
Tests mit NetworkSortAsmDown2Horst
 Anzahl: 100004884 t  1548,641 ms:   49,554 CPU-Takte
Tests mit NetworkSortAsmDown3
 Anzahl: 100004884 t   989,808 ms:   31,672 CPU-Takte
Tests mit SORTSprungTabelle
 Anzahl: 100004884 t  1194,537 ms:   38,223 CPU-Takte

[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

[Dano]

@Horst
da sind einige interessante dinge in deinen letzten beiträgen, also was die laufzeit optimiert (bzw könnte)
ich habe mit meinen tests erstmal abgeschlossen
durch die hilfe von euch konnte ich die zeit im verhältniss von 5:1 kürzen
nach bischen mehr als 24h war der rechner fertig... aber leider war das ergebniss nicht so wie gehofft^^
also neue idee muß her^^

mfg Dano