AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Programmierung allgemein Algorithmen, Datenstrukturen und Klassendesign Hilfe: Schnellste möglichkeit ein 4-Byte Array zu Sortieren

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

Ein Thema von Dano · begonnen am 4. Feb 2012 · letzter Beitrag vom 18. Feb 2012
Antwort Antwort
Seite 7 von 7   « Erste     567
Horst_

Registriert seit: 22. Jul 2004
Ort: Münster Osnabrück
116 Beiträge
 
#61

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

  Alt 14. Feb 2012, 18:18
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
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu

Registriert seit: 11. Okt 2003
Ort: Elbflorenz
40.503 Beiträge
 
Delphi 11 Alexandria
 
#62

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

  Alt 14. Feb 2012, 21:48
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
Garbage Collector ... Delphianer erzeugen keinen Müll, also brauchen sie auch keinen Müllsucher.
my Delphi wish list
  Mit Zitat antworten Zitat
Horst_

Registriert seit: 22. Jul 2004
Ort: Münster Osnabrück
116 Beiträge
 
#63

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

  Alt 15. Feb 2012, 07:51
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
Angehängte Dateien
Dateityp: zip Bjoerk2.zip (2,8 KB, 2x aufgerufen)
  Mit Zitat antworten Zitat
Furtbichler
(Gast)

n/a Beiträge
 
#64

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

  Alt 15. Feb 2012, 08:19
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.
  Mit Zitat antworten Zitat
Horst_

Registriert seit: 22. Jul 2004
Ort: Münster Osnabrück
116 Beiträge
 
#65

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

  Alt 15. Feb 2012, 09:30
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
  Mit Zitat antworten Zitat
Bjoerk

Registriert seit: 28. Feb 2011
Ort: Mannheim
1.384 Beiträge
 
Delphi 10.4 Sydney
 
#66

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

  Alt 15. Feb 2012, 10:26
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

Geändert von Bjoerk (15. Feb 2012 um 11:00 Uhr) Grund: Zusammenfassung:
  Mit Zitat antworten Zitat
Horst_

Registriert seit: 22. Jul 2004
Ort: Münster Osnabrück
116 Beiträge
 
#67

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

  Alt 15. Feb 2012, 21:48
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
Angehängte Dateien
Dateityp: zip TestVier.zip (38,3 KB, 1x aufgerufen)

Geändert von Horst_ (16. Feb 2012 um 20:08 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von Dano
Dano

Registriert seit: 12. Aug 2004
49 Beiträge
 
#68

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

  Alt 18. Feb 2012, 05:19
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
  Mit Zitat antworten Zitat
Benutzerbild von Dano
Dano

Registriert seit: 12. Aug 2004
49 Beiträge
 
#69

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

  Alt 18. Feb 2012, 05:45
@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
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 09:33 Uhr.
Powered by vBulletin® Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2021 by Daniel R. Wolf