Autor |
Beitrag |
Martok
Beiträge: 3661
Erhaltene Danke: 604
Win 8.1, Win 10 x64
Pascal: Lazarus Snapshot, Delphi 7,2007; PHP, JS: WebStorm
|
Verfasst: So 14.07.13 22:14
Hallo!
Diese Unit stellt einen Zufallszahlengenerator zur Verfügung, der auf dem zellulären Automaten der "Rule 30" basiert [MW], [WA], [NKS].
Dieser einfache Automat hat ein stark chaotisches Verhalten unabhängig von seinen initialen Bedingungen und eignet sich deswegen gut als schneller Zufallszahlengenerator. Aus seinem Zustand kann man einfach Bits extrahieren und daraus Ausgabedaten generieren. Genaueres im Kommentarblock in den Units.
Der generator ist Seedbar und nicht im klassischen Sinne ein kryptografisch sicherer Generator (CSPRNG) (auch wenn er die Kriterien tatsächlich formal erfüllt bzw. einfach modifiziert werden kann). Durch die hohe Sensitivität generiert jeder beliebige Ausgangszustand eine andere Sequenz, was durch das verwendete Sampling-Verfahren nochmal verstärkt wird. In der Standardkonfiguration existieren 2^4097 * 5 ~ 1E1234 mögliche Ketten, von denen durch die Art des Seedens allerding nur 2^64 ~ 1.8E19 zugänglich sind. Die Periodendauer ist dabei schon beim relativ kleinen Zustandsraum in Mathematica (~200 Zellen) länger als das Alter des Universums (schreibt Wolfram...), ich hab da etwas übertrieben (~4k Zellen), dürfte also besser sein
Mit einfachen statistische Analysen (Byte-Verteilung, FFT, mehrdimensionale Darstellungen) haben keine Regularität ergeben. Jedes Byte kommt im Mittel mit einer Wahrscheinlichkeit von 1/256+/-0.006% vor. Falls jemand Autokorrelationstests zwecks Perioden implementieren will: bitte, tut es, ich habe davon keine Ahnung
Mit im Paket ist ein einfaches Testprogramm, welches die Verwendung zeigt. Normalerweise wird man die Zustandsbreite nicht mit angeben, sondern nur den Seed (wenn überhaupt).
Beispiel 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12:
| var rng: TRule30Random; begin rng:= TRule30Random.Create(MeinSeedWert, 2047); try ShowMessageFmt('Float (0..1): %f', [rng.NextSingle]); ShowMessageFmt('Ganzzahl: %d', [rng.NextCardinal]); finally FreeAndNil(rng); end; |
Der Generator liefert bei mir ca. 8MB/s zuällige Daten.
Optimierungsbedarf wäre noch in uCellularAutomaton.TRule30Automaton.Step. Offensichtlich ist ja erstmal die Verwendung eines Bitvektors und SIMD (das geht sogar recht gut, hab das hier auf Papier), aber an der Implementation bin ich erstmal gescheitert.
Lizenz: MPL 1.1/GPL 2.0/LGPL 2.1
Historie
R1: Initial
R2: FPC-Anpassungen, Optimierungen von & mit Horst_H
Einloggen, um Attachments anzusehen!
_________________ "The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."
Zuletzt bearbeitet von Martok am Mo 15.07.13 21:14, insgesamt 2-mal bearbeitet
Für diesen Beitrag haben gedankt: DelphiShark, Marc., Narses
|
|
Horst_H
Beiträge: 1653
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Mo 15.07.13 13:46
Hallo,
wenn schon 4 Byte auf einmal verarbeitet werden, dann bitte auch so speichern und um 4 Byte weiter schreiten.Dabei begehe ich eine Grenzüberschreitung, aber das angelegte Feld ist ja 16 kB groß.
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30:
| procedure TRule30Automaton.Step; asm @loop: {$IFDEF ASM_1} mov ebx, dword ptr [ecx + $01] or ebx, dword ptr [ecx + $02] xor ebx, dword ptr [ecx] {$ELSE} mov edx, dword ptr [ecx]
mov ebx, edx shr ebx, 8 or bl, bh
xor ebx, edx {$ENDIF} {$IFDEF ASM_1} mov Dword ptr [eax], ebx ADD eax,4 ADD ecx,4 {$ELSE} mov byte ptr [eax], bl inc eax inc ecx {$ENDIF} cmp eax,esi jbe @loop
end; |
Als Testprogramm habe ich dies hier.
Ich zähle einfach mal die gesetzten Bits, um einen schnellen Vergleich zwischen purepascal und Asm1 zu haben.
deshalb ein konstanter randseed, zumal ich unter Linux kein QueryPerformanceCounter habe und ich wine hier noch nicht installiert habe/werde.
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7: 8:
| constructor TRule30Random.Create; var pc: Int64; begin pc := $471108150007AA55; Create(pc); end; |
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61: 62: 63: 64: 65:
| program Rng30Test; {$IFDEF FPC} {$Mode Delphi} {$ASMMODE Intel} {$OPTIMIZATION ON} {$OPTIMIZATION REGVAR} {$OPTIMIZATION PEEPHOLE} {$OPTIMIZATION CSE} {$OPTIMIZATION ASMCSE} {$ENDIF} uses sysutils,uCellularAutomaton,uRule30Random; function popcount(v :integer) :integer; assembler; asm mov edx, eax ; shr eax, 1 ; and eax, 055555555h ; sub edx, eax ; mov eax, edx ; shr edx, 2 ; and eax, 033333333h ; and edx, 033333333h ; add eax, edx ; ; mov edx, eax ; shr eax, 4 ; add eax, edx ; and eax, 00F0F0F0Fh ; imul eax, 001010101h ; shr eax, 24 ; mov result,EAX end;
function RandomSpeedtest(m : integer):LongWord; var rng: TRule30Random; i: integer; T1,T0 : TDateTime; begin result := 0; rng:= TRule30Random.Create(123456789, 8192); try T0 := time; IF m < 0 then m:= 1000; for i:= 1 to m do inc(result,PopCount(rng.NextCardinal)); T1 := time; Write(Format('%d iterations took',[m])); writeln(Format('%d ms',[round((T1-t0)*86400.0*1000)])); finally FreeAndNil(rng); end; end; begin writeln(RandomSpeedtest(10*1000*1000),' Bits gesetzt'); end. 28423 ms 12246 ms 7897 ms |
Angeblich sollen AMD solche verschobenen Zugriffe +0 +1 +2 nicht so mögen, es könnte also auf Intel-Chips schneller sein.
Gruß Horst
Für diesen Beitrag haben gedankt: Martok
|
|
Martok
Beiträge: 3661
Erhaltene Danke: 604
Win 8.1, Win 10 x64
Pascal: Lazarus Snapshot, Delphi 7,2007; PHP, JS: WebStorm
|
Verfasst: Mo 15.07.13 15:00
Ähm, ASM_1 ist der alte ("erste") Versuch. Da wird nur dword gelesen, weil das auf meinem AMD Windsor (jup, die gibts noch) schneller ist als byte ptr, vermutlich wegen dem rausmaskieren des untersten bytes. War aber alles nix. Aktuell ist der Code ohne alle defines, also dword lesen und im Register verarbeiten. Spart die Addition ein.
Horst_H hat folgendes geschrieben : | Dabei begehe ich eine Grenzüberschreitung, aber das angelegte Feld ist ja 16 kB groß. |
Genau deswegen rummsts bei mir dann auch direkt... der Typ ist nur so deklariert, damit man einfacher debuggen kann (siehe auch in der RTL), es wird nicht mehr reserviert als gebraucht wird.
Horst_H hat folgendes geschrieben : | Ich zähle einfach mal die gesetzten Bits, um einen schnellen Vergleich zwischen purepascal und Asm1 zu haben. |
Ist bei einem halbwegs guten Random ja eher wenig hilfreich...
Ich war auch schonmal soweit, dass ich 4 byte lese und 2 byte schreibe, aber dafür gehen mir aktuell etwas die Register aus. Man könnte noch esp verleiern und den linearen Speicherzugriff per pop machen...
Horst_H hat folgendes geschrieben : | deshalb ein konstanter randseed, zumal ich unter Linux kein QueryPerformanceCounter habe und ich wine hier noch nicht installiert habe/werde. |
Stimmt, die Version mit fpgettimeofday müsste auch mal jemand einbauen.
_________________ "The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."
|
|
Horst_H
Beiträge: 1653
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Mo 15.07.13 15:52
Hallo,
Damit es nicht "rummst" eben 4 byte extra belegen
Die Bits zählte ich, um eben zu kontrollieren ob PurePascal und ASM_1 auch die gleichen Ergebnisse liefern.
was noch enorm bremst ist die Erstellen eines Cardinal in rule30random.pas deshalb mal hier eine Variante,
die es recht schnell macht, wenn man StateSize ausreichend groß wählt.
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61: 62: 63: 64: 65: 66: 67: 68: 69: 70: 71: 72: 73: 74: 75: 76: 77: 78: 79: 80: 81: 82: 83: 84: 85: 86:
| function NextCardNoLoop(pB:pByte;delta:integer): cardinal; begin
result:= 0; result:= (result shl 1 ) OR (pB^); inc(pB,delta); result:= (result shl 1 ) OR (pB^); inc(pB,delta); result:= (result shl 1 ) OR (pB^); inc(pB,delta); result:= (result shl 1 ) OR (pB^); inc(pB,delta); result:= (result shl 1 ) OR (pB^); inc(pB,delta); result:= (result shl 1 ) OR (pB^); inc(pB,delta); result:= (result shl 1 ) OR (pB^); inc(pB,delta); result:= (result shl 1 ) OR (pB^); inc(pB,delta);
result:= (result shl 1 ) OR (pB^); inc(pB,delta); result:= (result shl 1 ) OR (pB^); inc(pB,delta); result:= (result shl 1 ) OR (pB^); inc(pB,delta); result:= (result shl 1 ) OR (pB^); inc(pB,delta); result:= (result shl 1 ) OR (pB^); inc(pB,delta); result:= (result shl 1 ) OR (pB^); inc(pB,delta); result:= (result shl 1 ) OR (pB^); inc(pB,delta); result:= (result shl 1 ) OR (pB^); inc(pB,delta);
result:= (result shl 1 ) OR (pB^); inc(pB,delta); result:= (result shl 1 ) OR (pB^); inc(pB,delta); result:= (result shl 1 ) OR (pB^); inc(pB,delta); result:= (result shl 1 ) OR (pB^); inc(pB,delta); result:= (result shl 1 ) OR (pB^); inc(pB,delta); result:= (result shl 1 ) OR (pB^); inc(pB,delta); result:= (result shl 1 ) OR (pB^); inc(pB,delta); result:= (result shl 1 ) OR (pB^); inc(pB,delta);
result:= (result shl 1 ) OR (pB^); inc(pB,delta); result:= (result shl 1 ) OR (pB^); inc(pB,delta); result:= (result shl 1 ) OR (pB^); inc(pB,delta); result:= (result shl 1 ) OR (pB^); inc(pB,delta); result:= (result shl 1 ) OR (pB^); inc(pB,delta); result:= (result shl 1 ) OR (pB^); inc(pB,delta); result:= (result shl 1 ) OR (pB^); inc(pB,delta); result:= (result shl 1 ) OR (pB^); inc(pB,delta);
result:= (result shl 1 ) OR (pB^); end;
function TRule30Random.NextCardinal: Cardinal; var pB : pByte; delta,i,Fc,OG: DWORD; begin OG := FAutomaton.StateSize; Fc := FCursor; pB := @FAutomaton.State[Fc]; delta := FCursorSkip; IF (Fc + 33*delta) < OG then begin result := NextCardNoLoop(pB,delta); FCursor := FCursor+ 33*delta; end else Begin result:= 0; for i:= 32 downto 0 do begin result:= (result shl 1 ) OR pB^; inc(pB,delta); inc(Fc, delta); if Fc >= OG then begin dec(Fc, OG); dec(pB,OG); FAutomaton.Step; end; end; FCursor := Fc; end; end; |
Jetzt sind es 3879 ms statt 7897 ms, das ist doch ein kleiner Gewinn
Gruß Horst
Edit:
Ich habe es mal mit TurboDelphi kompiliert und dazu FastMM4 auskommentiert.
Diesmal mit 3.2 Ghz.
Einloggen, um Attachments anzusehen!
Für diesen Beitrag haben gedankt: DelphiShark, Martok, SebastianFei
|
|
Martok
Beiträge: 3661
Erhaltene Danke: 604
Win 8.1, Win 10 x64
Pascal: Lazarus Snapshot, Delphi 7,2007; PHP, JS: WebStorm
|
Verfasst: Mo 15.07.13 20:03
Einige der hier besprochenen Optimierungen habe ich jetzt eingebaut und damit eine Beschleunigung ungefähr auf 2.5-fache Datenrate erreicht. Einige der aggresiveren haben noch subtile Änderungen im Verhalten zur Folge, das ist nicht so ganz toll
Download im ersten Beitrag.
EDIT: da fehlten ein paar Dateien. Fixed.
_________________ "The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."
|
|
Horst_H
Beiträge: 1653
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Di 16.07.13 00:30
Hallo,
eine kleine Änderung in uRule30Random.pas:
EDIT: Änderung verworfen, aber eine neue gemacht:
Die Felder werden jetzt in einem Getmem erstellt und "aligned".
Die AssemblerVariante von Step, macht jetzt genauso, wie die PascalVariante.
Dazu wird Feld 0 an die Stelle FeldGroesse kopiert und die TSelle Feldgroesse-1 zu Feld[-1].
Anschliessend wird in einem Rutsch durchgerechnet.
// Ohne {$OPTIMIZATION REGVAR} wird Freepascal elend langsam
Zu Testzwecken habe ich Step in die zwei Varianten StepPurePascal und StepASM aufgeteilt.
Jetzt arbeiten sie scheinbar identisch.
Aber NextCardinalASM liefert ab und an falsche Werte gegenüber NextCardinalPurePascal.
Und zwar ist immer das niederwertigste BIT. Völlig absurd, wieso dieses. Ich sehe es nicht.... MäuseMelk...
Gruß Horst
Einloggen, um Attachments anzusehen!
|
|
Horst_H
Beiträge: 1653
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Di 16.07.13 21:57
Hallo,
passend zum Thema:
www.clevercaboose.com/rich/ca/index.htm
dort ein Test der Periodizität von Rule 30 bei kleinen Weiten, bei der wrap around geradezu übel zu sein scheint.[ OK, die Enden fest auf 0/1 zu setzen ist wohl noch schlechter )
Exemplarisch :
Quelltext 1: 2: 3: 4: 5: 6: 7: 8:
| In other words, a random number generator based on this approach will initially generate a non-repeating succession of count values, then it will start repeating every period values. Weite Start der Perioden- Periode länge .. 35 18,636,338 18,480,630 36 197,368 2,844 |
www.clevercaboose.co...xpts_with_rule30.pdf
Ist Rule30 dann nicht nur eine Spielerei, wenn dort solche Sprünge in der Periodenlänge sind?
Gruß Horst
|
|
Horst_H
Beiträge: 1653
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Fr 19.07.13 13:22
Hallo,
Martok hätte es gerne mal schneller in Assembler.
Ich hatte einen Knoten im Gehirn, es tauchten Bits an falschen Stellen auf, ist wohl zu kalt...
Eigentlich sollte es Richtung MMX/SSE gehen, aber erst wollte ich nur testen ob auch rauskommt, was man erwartet.
Ich bin erstaunt über die Geschwindigkeit. 15 Befehle, 5 Takte -> IPC = 3
Wie man schnell an die passende Bits kommt, wenn man mit einem Versatz arbeitet, kann ja Martok mal recherchieren, wenn er wieder Zeit hat.
EDIT: nach Martok's Veto geändert:
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61: 62: 63: 64: 65: 66: 67: 68: 69: 70: 71: 72: 73: 74: 75: 76: 77: 78: 79: 80: 81: 82: 83: 84: 85: 86: 87: 88: 89: 90: 91: 92: 93: 94: 95: 96: 97: 98: 99: 100: 101: 102: 103: 104: 105: 106: 107: 108: 109: 110: 111: 112: 113: 114: 115: 116: 117: 118: 119: 120: 121: 122: 123: 124: 125: 126: 127: 128: 129: 130: 131: 132:
| Program Rule30; {$IFDEF FPC} {$Mode Delphi} {$ELSE} {$OPTIMIZATION ON} {$APPTYPE CONSOLE} {$ENDIF} uses SysUtils; const Limit = 8192; LimitArr = Limit div 32-1; var TestArray : Array[0..LimitArr+1] OF Cardinal;
function Rule_30(a:pCardinal):cardinal;assembler; const SizeOfRegister = 4;
asm push EBX; push ESI; push EDI
MOV EBX,EAX MOV ESI,LimitArr SHL ESI,2 ADD ESI,EBX MOV ECX,Dword Ptr [ESI]; MOV EAX,Dword Ptr [EBX]; MOV Dword Ptr [ESI+SizeOfRegister],EAX; @Loop: MOV EDI,Dword Ptr [EBX+SizeOfRegister]; BT ECX,31 MOV ECX,EAX RCL ECX,1 BT EDI,0 MOV EDX,EAX RCR EDX,1 OR EDX,EAX ADD EBX,SizeOfRegister XOR ECX,EDX MOV Dword Ptr [EBX-SizeOfRegister],ECX; MOV ECX,EAX cmp EBX,ESI MOV EAX,EDI JBE @Loop
POP EDI POP ESI POP EBX end;
function dummy(a:pCardinal):cardinal;assembler; asm
end;
function BinStr(Zahl: cardinal): String; var i : integer;
begin setlength(result,33); result[1] :='_'; For i := 0 to 31 do begin result[i+2] := chr(Zahl AND 1+Ord('0')); Zahl := Zahl shr 1; end; end;
procedure Ausgabe; var i : integer; begin For i := LOW(TestArray) To High(TestArray)-1 do write(BinStr(TestArray[i])); write('D',BinStr(TestArray[High(TestArray)])); writeln; end;
const Runden :Int64 = 10*1000*1000; CpuF = 3.2e9; var k: integer; T1,T0 : TDateTime; Begin TestArray[Limit DIV 32 DIV 2]:=256*256; T0 := time; For k := 1 to Runden do begin dummy(@TestArray[0]); end; T1 := time; writeln('Dummy Aufrufe ',FormatDateTime('HH:NN:SS.zzz',T1-T0)); writeln('Takte pro Aufruf: ',((T1-t0)*86400*CpuF)/(Runden):0:1);
T0 := time; For k := 1 to Runden do begin Rule_30(@TestArray[0]); end; T1 := time; writeln('Echte Aufrufe ',FormatDateTime('HH:NN:SS.zzz',T1-T0)); writeln('Takte pro Aufruf: ',((T1-t0)*86400*CpuF)/Runden:0:0); writeln('Takte pro 32-Bit: ',((T1-t0)*86400*CpuF)/(Runden*(LimitArr+1)):0:1);
readln end. |
Gruß Horst
Zuletzt bearbeitet von Horst_H am Fr 19.07.13 21:24, insgesamt 1-mal bearbeitet
|
|
Martok
Beiträge: 3661
Erhaltene Danke: 604
Win 8.1, Win 10 x64
Pascal: Lazarus Snapshot, Delphi 7,2007; PHP, JS: WebStorm
|
Verfasst: Fr 19.07.13 18:15
Horst_H hat folgendes geschrieben : | Eigentlich sollte es Richtung MMX/SSE gehen, aber erst wollte ich nur testen ob auch rauskommt, was man erwartet. |
Delphi-Quelltext 1: 2:
| XOR EDX,EAX OR ECX,EDX |
Andersrum. Erst OR, dann XOR. Passt akkurat dann.
Horst_H hat folgendes geschrieben : | Ich bin erstaunt über die Geschwindigkeit. 15 Befehle, 5 Takte -> IPC = 3 |
Sieht bei mir geringfügig schlechter aus:
Zitat: |
CpuF = 1.4e9; // AMD FX 6300 per PowerMgmt auf 1.4 Ghz
Dummy Aufrufe 00:00:00.063
Takte pro Aufruf: 8.8
Echte Aufrufe 00:00:13.171
Takte pro Aufruf: 1844
Takte pro 32-Bit: 7.2 |
Horst_H hat folgendes geschrieben : | Wie man schnell an die passende Bits kommt, wenn man mit einem Versatz arbeitet, kann ja Martok mal recherchieren, wenn er wieder Zeit hat. |
Hrrm. Ich hab keine Zeit, aber das ist so viel interessanter
Die Idee mit BT und RCL ist gar nicht doof. Im Prinzip kann man ja sogar sehr einfach vorhersagen, wie viele Bereiche man braucht: Um 32bit in N-Bit-schritten zu generieren braucht man N DWORDs... damit braucht man nur einen Index für den ersten und von dort aus Bits mod 32 zählen. Das mit dem einen Überspringen kann man (vermutlich) lassen.
Als nächstes sollte man dann wohl mal die Periode untersuchen, immerhin haben wir ja jetzt 8mal weniger RAM-Verbrauch als der naive Ansatz. 100Mio 128Bit-Zustände sind nur 1.6GByte, das kann man sogar mit 32bit-OS problemlos machen. Zeit für viele viele CompareMem ist ja nicht so das Problem (zumal es ja die FastCode gibt).
EDIT: die Ergebnisse aus dem Link oben für die Periode von 32bit konnte ich reproduzieren. Weitere Vielfache von 32 sind mit meinen Mitteln nicht mehr festzustellen. Ich weiß nur, dass die Periode angefangen von einer schwarzen Zelle größer 242483200 ist, ausgehend von zufälligen Werten (Stichprobe von 100 Läufen) ist mit 2GB auch nichts zu finden.
Oh und: meine Güte, ist das Ding schnell
_________________ "The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."
|
|
Horst_H
Beiträge: 1653
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Sa 20.07.13 07:38
Hallo,
das der "Bulldozer" mehr im doze-mode ist wundert mich Das IPC ist ja knapp über 2 .
Ich gebe zu, IPC =3 habe ich auch bisher noch nicht erlebt ( 2,3 in www.entwickler-ecke....der=asc&start=37 ) .
Mit Freepascal 2.6.2, CPUF= 3.2e9
Quelltext 1: 2: 3: 4: 5: 6:
| sh-4.1# ./Rule30 Dummy Aufrufe 00:00:00.031 Takte pro Aufruf: 9.9 Echte Aufrufe 00:00:04.079 Takte pro Aufruf: 1305 Takte pro 32-Bit: 5.1 |
Scheinbar kann man sehr viel outoforder oder noch verarbeiten während andere Dinge laufen, da sie unabhängig von einander sind.
Sicher geht es noch schneller, aber für wen oder was
Gruß Horst
|
|
Martok
Beiträge: 3661
Erhaltene Danke: 604
Win 8.1, Win 10 x64
Pascal: Lazarus Snapshot, Delphi 7,2007; PHP, JS: WebStorm
|
Verfasst: Sa 20.07.13 15:21
Horst_H hat folgendes geschrieben : | Wie man schnell an die passende Bits kommt, wenn man mit einem Versatz arbeitet, kann ja Martok mal recherchieren, wenn er wieder Zeit hat. |
BTS/BTR/BT laufen über , und Delphi kennt eine TBits-Klasse (Classes.pas).
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7:
| function TRule30Automaton.GetBit(Index: integer): boolean; asm MOV EAX,[EAX].FState[0] BT [EAX],Index SBB EAX,EAX AND EAX,1 end; |
Wenn man mehr als das 32. Bit will, fasst das einfach mal in das nächste DWORD.
Also jetzt einfach nur noch durchzählen:
Pseudoassembler, nach Geschmack mit Registern würzen 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14:
| asm mov ptr, FState[0] xor result, result @@0 bt ptr, index rcl result, 1 add index, StepSize cmp index, bitcount jl @@1 call Automaton.Step dec index, bitcount @@1 jmp @@0 end |
EDIT:
323 Clocks/Call für 32bit. 67% der Zeit in asm BT [esi], edi end, obwohl das komplett Data Cache Hits sind.
Einloggen, um Attachments anzusehen!
_________________ "The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."
|
|
Horst_H
Beiträge: 1653
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Mo 22.07.13 12:04
Hallo,
Da übergibt der Assembler stepsize und ersetzt dann durch ein Register das ich gerade benutzte. Was für ein falscher Fehler von mir.
Anbei ein Version, die zumindest nicht abstürzt
Ich übergebe bei Testcard nicht mehr die Startposition innerhalb des Bitfeldes und nutzte das wieder eingeführte FCursor.
Bei einer Schrittweite von 5 und einer minimalen teilerfremden ( sonst kommen immer die gleichen Bitpositionen zum Zuge ) Feldgröße von (5+1) *32 Bit brauche ich jetzt 220 Takte pro Cardinalzahl, bei 256*32 Bit sind es um die 150.
Eigentlich wollte ich berechnete Sprünge machen.Vielleicht später.
Gruß Horst
P.S.
Endlich habe ich den Fehler gefunden.
Rule30.step erwartet die Anzahl der Cardinal und ich habe in GetBis32 aber die Anzahl der Bits übergeben.
Dass das nicht immer "knallte" wundert mich.
Einloggen, um Attachments anzusehen!
|
|
Horst_H
Beiträge: 1653
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Do 01.08.19 21:55
Hallo,
es geht auch ohne Assembler als 64-Bit Kompilat schnell.Wenn auch hier jedes Byte Bit für Bit erzeugt wird.
Freepascal kennt ja ROR und ROL.
Rule30, dort kann man es auch mit TryItOnline aufrufen,
Gruß Horst
|
|
|