![]() |
AW: Hilfe: Schnellste möglichkeit ein 4-Byte Array zu Sortieren
Zitat:
![]() |
AW: Hilfe: Schnellste möglichkeit ein 4-Byte Array zu Sortieren
Zitat:
Delphi-Quellcode:
kurze erklärung
unit Unit1;
interface uses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls; type TForm1 = class(TForm) Memo1: TMemo; Button1: TButton; procedure Button1Click(Sender: TObject); private { Private-Deklarationen } public { Public-Deklarationen } end; var Form1: TForm1; gTimer1,gTimer2,gFrequenz: Int64; type ByteArray = packed record case Integer of 1: (A: array[0..3] of Byte); 2: (Card: Cardinal); end; implementation {$R *.dfm} procedure Show1(S: String); overload; begin Form1.Memo1.Lines.Add(S); end; procedure Show1(S: String; N: Cardinal); overload; begin Form1.Memo1.Lines.Add(S+IntToStr(N)); end; procedure StartTimer; overload; begin QueryPerformanceCounter(gTimer1); gTimer2:=0; end; procedure ShowTimer; overload; begin QueryPerformanceCounter(gTimer2); Form1.Memo1.Lines.Add(FormatFloat('0.0000', (gTimer2 - gTimer1) * 1000 / gFrequenz) + ' ms'); Form1.Memo1.Lines.Add(IntToStr(gTimer2 - gTimer1)+ ' Tick'); end; procedure Show1(A: ByteArray); overload; begin Show1('Array: ' +IntToStr(A.A[3])+',' +IntToStr(A.A[2])+',' +IntToStr(A.A[1])+',' +IntToStr(A.A[0])+' - ' +IntToStr(A.Card)); end; procedure Selectionsort3Down(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[0] > A[2] then begin T:= A[0]; A[0]:= A[2]; A[2]:= T; end; if A[0] > A[3] then begin T:= A[0]; A[0]:= A[3]; A[3]:= T; end; if A[1] > A[2] then begin T:= A[1]; A[1]:= 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[2] > A[3] then begin T:= A[2]; A[2]:= A[3]; A[3]:= T; end; end; end; 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; // Von groß nach klein procedure SelectionsortASMDown(var A: Cardinal); register; label Weiter1,Weiter2,Weiter3,Weiter4,Weiter5,Weiter6; 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 ECX,[EAX]; // A in ECX mov DL,CL; rol ECX,8; // init fertig // if A[0] > A[1] then begin T:= A[0]; A[0]:= A[1]; A[1]:= T; end; cmp DL,CL; jnb Weiter1; xchg DL,CL; Weiter1: // if A[0] > A[2] then begin T:= A[0]; A[0]:= A[1]; A[1]:= T; end; rol ECX,8 cmp DL,CL; jnb Weiter2; xchg DL,CL; Weiter2: // if A[0] > A[3] then begin T:= A[0]; A[0]:= A[1]; A[1]:= T; end; rol ECX,8; cmp DL,CL; jnb Weiter3; xchg DL,CL; Weiter3: // if A[1] > A[3] then begin T:= A[1]; A[1]:= A[2]; A[2]:= T; end; rol EDX,8; mov DL,CL; ror ECX,8; 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; ror ECX,8; cmp DL,CL; jnb Weiter5; xchg DL,CL; Weiter5: // if A[2] > A[3] then begin T:= A[2]; A[2]:= A[3]; A[3]:= T; end; rol EDX,8; mov DL,CL; rol ECX,8; cmp DL,CL; jnb Weiter6; xchg DL,CL; Weiter6: rol EDX,8; mov DL,CL; mov [EAX],EDX; end; // Von groß nach klein 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; procedure SelectionsortASMDown2Horst(var A: ByteArray); register; label 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. PUSH EAX; mov CX,[EAX]; mov DX,[EAX+$02]; mov AX,DX // tauscht DL,DH Xchg AH,AL // // init fertig // if A[0] > A[1] then begin T:= A[0]; A[0]:= A[1]; A[1]:= T; end; cmp DH,DL; cmovc dx,ax mov AX,CX // tauscht CL,CH Xchg AH,AL // if A[2] > A[3] then begin T:= A[0]; A[0]:= A[2]; A[2]:= T; end; cmp CH,CL; cmovc cx,ax // 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: POP EAX mov [EAX],CX; mov [EAX+$02],DX; end; procedure SelectionsortASMDown3Horst(var A: ByteArray); register; label 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. PUSH EAX; PUSh EBX; mov EAX,[EAX]; MOV BX,AX Xchg BH,BL //1 tauscht CL,CH MOV CX,AX; SHR EAX,16; MOV DX,AX Xchg AH,AL //2 tauscht DL,DH cmp CH,CL; cmovc cx,bx cmp DH,DL; cmovc dx,ax Xchg CL,DH; //CX(L,H) : DH,CH ,DX(L,H) : DL,CL mov BX,CX mov AX,DX cmp CL,CH; Xchg BH,BL // Veraendert Carry nicht Xchg AH,AL cmovc cx,bx cmp DL,DH; cmovc dx,ax Xchg CL,DH; // Zurücktauschen cmp DL,CH; jnb Weiter5; xchg DL,CH; Weiter5: POP EBX SHL EDX,16 MOV DX,CX POP EAX mov [EAX],EDX; end; procedure TForm1.Button1Click(Sender: TObject); var Temp: ByteArray; Count, Vaule, MaxRound: Cardinal; begin MaxRound:=$7fffffff; Memo1.Clear; //Vaule:= $01020304; //Vaule:= $02010403; //Vaule:= $01030204; Vaule:= $01040302; Temp.Card:=Vaule; Show1(Temp); Show1('MaxRound ',MaxRound); Show1(''); Show1('Selectionsort3Down'); StartTimer; for Count:=0 to MaxRound do begin Temp.Card:=Vaule; Selectionsort3Down(Temp); end; ShowTimer; Show1(Temp); Show1(''); Show1('NetworkSort2'); StartTimer; for Count:=0 to MaxRound do begin Temp.Card:=Vaule; NetworkSort2(Temp); end; ShowTimer; Show1(Temp); Show1(''); Show1('SelectionsortASMDown'); StartTimer; for Count:=0 to MaxRound do begin Temp.Card:=Vaule; SelectionsortASMDown(Temp.Card); end; ShowTimer; Show1(Temp); Show1(''); Show1('SelectionsortASMDown2'); StartTimer; for Count:=0 to MaxRound do begin Temp.Card:=Vaule; SelectionsortASMDown2(Temp.Card); end; ShowTimer; Show1(Temp); Show1(''); Show1('SelectionsortASMDown2Horst'); StartTimer; for Count:=0 to MaxRound do begin Temp.Card:=Vaule; SelectionsortASMDown2Horst(Temp); end; ShowTimer; Show1(Temp); Show1(''); Show1('SelectionsortASMDown3Horst'); StartTimer; for Count:=0 to MaxRound do begin Temp.Card:=Vaule; SelectionsortASMDown3Horst(Temp); end; ShowTimer; Show1(Temp); end; initialization QueryPerformanceFrequency(gFrequenz); end. die Form hat nur 1 Button und ein Memo MaxRound ist die rundenanzahl jedes test's Vaule ist das array das zum testen genommen wird das array wird auch immer neu gesetzt in jedem durchlauf das "Show1" und "StartTimer" sind rudimentäre funktionen damit ich mir nicht jedes mal "Form1.Memo1.Lines.Add" antun muß.... sind in meiner lib die ich einbinde soweit so gut, hab das wirklich mit vielen sinvollen kombinationen von "Vaule" versucht... aber im schnitt war bis jetzt "SelectionsortASMDown2" der schnellste optimal müßte ich jetzt noch eine function schreiben wo alle N = 24! versucht werden aber den ehrgeiz hatte ich noch nicht^^ so wie oben gepostet mit "Vaule:= $01040302;" habe ich auf "Core 2 Duo E8600 @3,33GHz" NICHT übertaktet
Code:
an deine letzten beiden geposteten ASM-Functionen habe ich "horst" zur erkennung angehängt
Array: 1,4,3,2 - 17040130
MaxRound 2147483647 Selectionsort3Down 21224,7471 ms 70881316380 Tick Array: 4,3,2,1 - 67305985 NetworkSort2 25555,0185 ms 85342517680 Tick Array: 4,3,2,1 - 67305985 SelectionsortASMDown 16764,6979 ms 55986714570 Tick Array: 4,3,2,1 - 67305985 SelectionsortASMDown2 13761,6837 ms 45957968490 Tick Array: 4,3,2,1 - 67305985 SelectionsortASMDown2Horst 20686,4956 ms 69083793090 Tick Array: 4,3,2,1 - 67305985 SelectionsortASMDown3Horst 27085,5254 ms 90453737140 Tick Array: 4,3,2,1 - 67305985 da der test als single-thread läuft und ich auch die cpu-auslastungen im auge habe, denke ich nicht das irgendeine hintergrund anwendung großartig einfluss nimmt... den hardware IO mit der festplatte usw beachte ich auch... ich weiß nicht genau ob dieser alte Core 2 Duo schon runtertaktet bei wärme.... aber so einen Boost (der den takt anhebt kurzzeitig bis das wärme-limit erreicht ist) hat er noch nicht... womit dann die ersten 5 sek mit höherem takt laufen und die erste funktion die ich teste einen vorteil hätte... soweit zu den dingen die den test verfälschen könnten horst benutzt den FPC wenn ich richtig gelesen habe.. (PS: die vielen "%"-zeichen in deinem ersten ASM-auszug haben mir angst gemacht^^) kann natürlich sein das die compiler mit den schleifen unterschiedlichen code erzeugen aber im verhältniss zueinander sollte wieder alles in etwa richtig sein auf die sache mit den takte für eine einzelne ASM-anweisung... durch pipeline, branch prediction(Sprungvorhersage) und den cash-pages... bin ich selber nicht mehr im stande eine vorhersage zu treffen welch funktion schneller läuft... also bleibt mir nur testen im sinne des contents in dem die funktion läuft zu 486er zeiten hatte jeder befehl noch takte die er brauch... glaube seit pentium ist das kein fester wert mit dem man rechnen kann ok, soweit von mir TODO: um den test wasserdicht zu machen müßte jede sortierfunktion mit allen 24 kombinationen getestet werden mfg Dano |
AW: Hilfe: Schnellste möglichkeit ein 4-Byte Array zu Sortieren
Delphi-Quellcode:
Die 64 Bit Befehle sollen wieder mitfesten Takten arbeiten, wenn ich das richtig verstanden hab.
const
Values: array[0..23] of LongWord = ( $04030201, $03040201, $04020301, $02040301, $03020401, $02030401, $04030102, $03040102, $04010302, $01040302, $03010402, $01030402, $04020103, $02040103, $04010203, $01040203, $02010403, $01020403, $03020104, $02030104, $03010204, $01030204, $02010304, $01020304); Temp.Card := Vaules[Count mod 24]; |
AW: Hilfe: Schnellste möglichkeit ein 4-Byte Array zu Sortieren
Liste der Anhänge anzeigen (Anzahl: 1)
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.
Delphi-Quellcode:
Wie Du siehst ist meine Variante3 bei mir erheblich schneller, das heisst aber nicht, dass bei Dir andere Varianten nicht noch schneller sind/sein können.
MaxRound 1000000000
Tests mit Dummy Anzahl: 1000000000 Ticks: 13437923 ms: 4311,708 Tests mit Selectionsort3Down Anzahl: 1000000000 Ticks: 85371524 ms: 27392,338 Tests mit NetworkSort2 Anzahl: 1000000000 Ticks: 79294972 ms: 25442,618 Tests mit SelectionsortASMDown Anzahl: 1000000000 Ticks: 45523858 ms: 14606,808 Tests mit SelectionsortASMDown2 Anzahl: 1000000000 Ticks: 51604629 ms: 16557,888 Tests mit SelectionsortASMDown2Horst Anzahl: 1000000000 Ticks: 44724554 ms: 14350,338 Tests mit SelectionsortASMDown3Horst Anzahl: 1000000000 Ticks: 18670531 ms: 5990,638 Gruß Horst P.S.
Delphi-Quellcode:
wäre mir zu langsam und zu regelmässig.
Temp.Card := Vaules[Count mod 24];
Ich habe mal die Testliste/Values auf 24 beschränkt. In Wahrheit: Weil dann Tests mit SelectionsortASMDown gewinnt ;-)
Delphi-Quellcode:
MaxRound 99999984 ( 1e8 DIV 24 )
Tests mit Dummy Anzahl: 99999984 Ticks: 1146723 ms: 367,948.3 Tests mit Selectionsort3Down Anzahl: 99999984 Ticks: 5331997 ms: 1710,838.3 Tests mit NetworkSort2 Anzahl: 99999984 Ticks: 5032214 ms: 1614,648.3 Tests mit SelectionsortASMDown Anzahl: 99999984 Ticks: 1316565 ms: 422,438.3 Tests mit SelectionsortASMDown2 Anzahl: 99999984 Ticks: 2397344 ms: 769,218.3 Tests mit SelectionsortASMDown2Horst Anzahl: 99999984 Ticks: 2410761 ms: 773,528.3 Tests mit SelectionsortASMDown3Horst Anzahl: 99999984 Ticks: 1563923 ms: 501,808.3 |
AW: Hilfe: Schnellste möglichkeit ein 4-Byte Array zu Sortieren
joar, MOD gefällt mir auch nicht, aber 24 ist soein blöder Wert :cry:
Aber da du ja eh die Aufrufe rausrechnen wolltest, isses doch egal. :mrgreen: Nur was hast du gegen regelmäßig? Ob man nun das 24-stel mit dem ersten Wert uws. machen würde, oder die 24 Werte immer hintereinander oder alles unregelmäig durcheinander (könntest ja via Random jeweils einen Wert reisholen), aber so, daß alle Wert gleichmäßig oft vorkommen ... ist doch egal. Hauptsache es kommen alle Werte vor und jeder bekommt die selben Testdaten. |
AW: Hilfe: Schnellste möglichkeit ein 4-Byte Array zu Sortieren
Also, mit deinen 15 sec. kann was nicht stimmen, hab eben mal meine selectionsort 5 Mio mal durchlaufen lassen. < 0,5 s.
Wie reagiert denn deine aufrufende procedure auf das Onchange von A. Eventuell den Sort dann besser als function? |
AW: Hilfe: Schnellste möglichkeit ein 4-Byte Array zu Sortieren
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.
Delphi-Quellcode:
Die obere Ausgabe bezieht sich auf 1e9 (= 1e5*1e4) Aufrufe.
procedure TLInit;
var i : longInt; begin setlength(TL,FeldGroesse); randomize; TL[0].card := $04030201; TL[1].card := $03040201; TL[2].card := $04020301; TL[3].card := $02040301; TL[4].card := $03020401; TL[5].card := $02030401; TL[6].card := $04030102; TL[7].card := $03040102; TL[8].card := $04010302; TL[9].card := $01040302; TL[10].card := $03010402; TL[11].card := $01030402; TL[12].card := $04020103; TL[13].card := $02040103; TL[14].card := $04010203; TL[15].card := $01040203; TL[16].card := $02010403; TL[17].card := $01020403; TL[18].card := $03020104; TL[19].card := $02030104; TL[20].card := $03010204; TL[21].card := $01030204; TL[22].card := $02010304; TL[23].card := $01020304; For i := 24 to high(TL) do TL[i] := TL[random(24)]; end; Also Runden = 100000 (1e5) mal wird ein High(TL)+1=10000 (1e4)elementiges Testfeld mit zufälligen Werten abgefragt.
Delphi-Quellcode:
Die unter Ausgabe bezieht sich auf 1e8 DIV 24 Aufrufe.
StartTimer;
For j := 1 to RUNDEN do For i := High(TL) Downto 0 do begin TestWert.Card := TL[i].card; Test(TestWert); // Prüfen auf Fehler IF TestWert.card <> Res then begin EXIT; end; end; StoppTimer; Also Runden = 4'166'666 mal wird ein High(TL)+1=24 elementiges Testfeld mit allen Möglichkeiten abgefragt. Rein zufällige Werte sind also eine Bremse. Gruß Horst |
AW: Hilfe: Schnellste möglichkeit ein 4-Byte Array zu Sortieren
Hallo Horst,
ich bezog mich hier auf die in #15 von TE angegeben Rechenzeiten. Sind alle viel zu groß. Deshalb auch meine Frage bezüglich der aufrufenden procedure. // Edit: Dort gings noch um 5 mill. Durchläufe.. |
AW: Hilfe: Schnellste möglichkeit ein 4-Byte Array zu Sortieren
Liste der Anhänge anzeigen (Anzahl: 1)
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. In Rot AMD x% schneller in schwarz AMD x% langsamer. http://www.delphipraxis.net/attachme...2&d=1329052892 Gruß Horst |
AW: Hilfe: Schnellste möglichkeit ein 4-Byte Array zu Sortieren
Mit einem konstanten Wert bevorteilst und benachteilst du bestimmte Algortihmen, welche gerade bei diesem Wert ihre meisten Verleiche und Verschiebeaktionen hätten.
Die Resultate sind also absolut nicht aussafähig, denn schließlich hat du damit ja 95,8333% aller Möglichkeiten ignoriert. Die Variante vorher ein Array mit Testwerten zu erstellen, hatte ich ja schonmal vorgeschlagen, das würde allen Algorithmen die selben Testwerte geben, ohne sie live zu berechnen. |
Alle Zeitangaben in WEZ +1. Es ist jetzt 09:56 Uhr. |
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz