-
Forum: Algorithmen, Datenstrukturen und Klassendesign
by Horst_,
15. Feb 2012
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...
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
by Horst_,
15. Feb 2012
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 )
Erstellen der Werte: 1437 ms
...
2.ter Durchgang
DummySort: 187 ms
Selectionsort: 549 ms , zuvor...
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
by Horst_,
15. Feb 2012
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...
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
by Horst_,
14. Feb 2012
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 ,...
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
by Horst_,
14. Feb 2012
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.
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
by Horst_,
14. Feb 2012
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 ),...
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
by Horst_,
13. Feb 2012
Hallo,
anbei die Konsolenversion.Ich habe hier alternativ nur Lazarus am Werk.
Gruß Horst
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
by Horst_,
13. Feb 2012
Hallo,
@bjoerk:
In Post 44 ist das doch in der Unit1.zip eingebaut.
Wie dano schrieb, wie er seine Ergebnisse bekam, habe ich ein eine Form1 mit einem Button1 und einem memo1 zusammengeklickt und dann die entstehende unit1 durch diese ersetzt.Dort sind doch die asm Varianten schon drin.
@dano:
Wie ich schon vorher bemerkt habe kann man ab und an durch cmovc Sprünge einsparen.
Wie BUG...
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
by Horst_,
12. Feb 2012
Hallo,
mit konstantem Wert getestet wie TE Dano un verglichen.
Die Laufzeitunterschiede sind ja gewaltig von der CPU abhängig.
Selbst wenn ich die Dummy-Zeiten draufaddiere, was ja so auch nicht ganz richtig ist, aber auch bei der Anzahl der Durchläufe wohl auch nicht bemerkbar ist, ergeben sich gewaltige Unterschiede, die über die Prozessortaktfrequenzunterschiede von 4% weit hinausgehen....
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
by Horst_,
12. Feb 2012
Hallo,
wie denn, wo denn, was denn?
0,5 Sekunden für 5e6 Aufrufe sind 100 ns / Aufruf ~ 320 Takte bei mir.
Was soll den mit 15 Sekunden nicht stimmen, zu langsam / zu schnell ?
Ladet doch die unit runter und schaut in den Quelltext.
procedure TLInit;
var
i : longInt;
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
by Horst_,
12. Feb 2012
Hallo,
@dano:
den Quelltext in seiner ganzen "Schönheit" kann man auch anhängen ;-)
Ich habe es auf Lazarus umgemünzt.
Dummy gibt als Funktionswert einfach das richtige Ergebnis zurück, um die Zeit des reinen aufrufens rauszurechnen.
Ich habe die Unit mal angehängt, sollte auch mit Delphi funktionieren, damit Du einen Vergleich starten kannst.
MaxRound 1000000000
Tests mit Dummy
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
by Horst_,
11. Feb 2012
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...
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
by Horst_,
10. Feb 2012
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' +...
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
by Horst_,
10. Feb 2012
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,...
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
by Horst_,
9. Feb 2012
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...
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
by Horst_,
8. Feb 2012
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.
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
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
by Horst_,
7. Feb 2012
Hallo,
@Aphton
Mit 3 Vergleichen wäre ja schön, aber nicht möglich.
Seien AB und CD jeweils aufwärts sortiert,(A<B und C<D)
Dann könnte A>D sein-> CDAB
Dann könnte B<C sein-> ABCD
aber was ist mit Möglichkeiten:
ACBD,ACDB oder CABD und CADB
Wobei immer A<B UND C<D ist.