GNURZ - Arithmetik-Unit für große Zahlen

[mschnell]

Übrigens:

Es könnte möglich sein, 64 Bit Additionen und 64*64=128 Bit Multiplikationen mit Hilfe des SSE Befehlssatzes oder anderer Erweiterungen auch mit einem 32 Bit Prozessor in einem Befehl zu machen. Möglicherweise müssen dafür zwei 32 Bit Operationen parallel ausgeführt und die Ergebnisse nachher kombiniert werden. Ich habe da aber keine Erfahrungen. Im normalen 64 Bit CPU Modus ist es sicher einfacher.

-Michael

[af0815]

GNURZ ist auch im SVN.

https://lazsnippets.svn.sourceforge.net/svnroot/lazsnippets/trunk/software/algorithmen/GNURZ

Lesezugriff haben alle

[marcov]

(ein Tip: wenn man auf 64-bit mit 64-bit Typen, und auf 32-bit mit 32-bit rechnet bekommt man Endianess Probleme wenn man auf 64-bit etwas ein Großzahl speichert (zb blockwrite) und wieder auf 32-bit lest, und vice versa. Und wenn man Kryptologie macht, wird man oft Keys nach Disk schreiben. Ja, man kann das manuell speichern, aber solch ein Problem ist verwirrend)

[Euklid]

Für einen ausgiebigen Test möchte ich mir Zeit nehmen und ihn daher erst morgen durchführen.

Als Vergleichstest habe ich die Dauer von zehntausend Additionen fünfzigtausendstelliger Zahlen gemessen.

Ergebnis:
Bisherige Routine: 2,196 sec
Assembler-Routin: 0,973 sec

Durch Assembler kann demnach eine gute Halbierung der Rechenzeit erreicht werden. Die Beschleunigung der Additions-Routinen beeinflusst ebenfalls die Division und vor allem die Multiplikation positiv.
Dank nochmal an Michael. Werde die Assembler-Routinen anpassen und anschließend in die GNURZ einfügen. Bisher müssen die beiden Summanden noch gleich lang sein.

af0815: Danke für die Aufnahme ins SVN!
marcov: Du hast Recht. Die Speicherung solcher Zahlen sollte in einem Format passieren, das von allen Architekturen gleichermaßen geöffnet werden kann.

michael: Kurze Frage.

Code: Alles auswählen

push ebx           // s, s1 and s2 already are eax, edx and ecx

Woher weißt du, dass s, s1 und s2 ausgerechnet in diesen Registern landet?


Viele Grüße, Euklid

[mschnell]

(ein Tip: wenn man auf 64-bit mit 64-bit Typen, und auf 32-bit mit 32-bit rechnet bekommt man Endianess Probleme wenn man auf 64-bit etwas ein Großzahl speichert (zb blockwrite) und wieder auf 32-bit lest, und vice versa.

Wieso ?
Sowohl der 32 Bit als auch der 64 Bit modus der x86 CPU arbeiten "low endien first". d.h. im Speicher steht in der Zahl auf

Byte Adresse + 00 die Bits 2^0 bis 2^7,
Byte Adresse + 01 die Bits 2^8 bis 2^15,
Byte Adresse + 02 die Bits 2^16 bis 2^24,
usw. gespeichert sind

Die Langzahl wird nun sinnvollerweise so abgelegt, dass bei einem 32 Bit Grundtyp auf

DWord 0 (Adresse + 00) die Bits 2^0 bis 2^31,
DWord 1 (Adresse + 04) die Bits 2^32 bis 2^63,
DWord 2 (Adresse + 08) die Bits 2^64 bis 2^95,
usw. gespeichert sind

Davon geht zumindest mein ASM "add" aus (bei Umgekehrter Reig´henfolge könnte man sogar einen ASM-Befehl sparen, aber man hält sich richtigerweise immer an das durch die Hardware vorgegebene Zahlenformat).

Die Langhzahl des 64 Bit Grundtyp sieht dann entsprechend aus
QWord 0 (Adresse + 00) die Bits 2^0 bis 2^63,
QWord 1 (Adresse + 08) die Bits 2^64 bis 2^128,
QWord 2 (Adresse + 16) die Bits 2^128 bis 2^181,
usw.

Das Speicher-Layout ist also identisch.

Wenn man die Langzahl in ein Datei speichern will muss man natürlich in der Datei-Beschreibung (auf Papier) hinterlegen, wie sie dort formatiert ist. Am besten ist natürlich ein lesbares Text-Format. Dabei am einfachsten zu realisieren ist Hexadezimal (wie z.B. bei MD5 immer verwendet). Das ist natürlich normalerweise "high-nibbel first". Diese Konvertierung muss die Eingabe/Ausgabe-Funktion behandeln.

-Michael

[mschnell]

Durch Assembler kann demnach eine gute Halbierung der Rechenzeit erreicht werden.

64 Bit bringt sicherlich nochmal ca Faktor 2.
"subadd" und "subsub" wird auch einiges bringen, weil hier nur eine Schleife durchlaufen werden muss, anstatt die Langzahl zwischenzuspeichern und eine weitere komplette Rechnung durchzuführen. Bei 50000 Stellen (20KByte). wird das 'rein und 'raustransportieren der Werte in die verschiedenen Bereiche der CPU (Kern, RISC-Bereich, 1st Level Cache, 2nd Level Cache) wichtig und Zwischen-Speicherungen von Langzahlen sollten soweit möglich vermieden werden.
Die Assembler-Programmierung für die primitiv-Multiplikation habe ich mir noch nicht überlegt. Ich denke das wird auch viel schneller als in Pascal(besonders mit 64 Bit).

Code: Alles auswählen

push ebx           // s, s1 and s2 already are eax, edx and ecx

Woher weißt du, dass s, s1 und s2 ausgerechnet in diesen Registern landet?

Das ist Bestandteil des ABI (Application Binary Interface), das regelt, wie ein Compiler Unterprogramme aufruft. Das ist Compiler-abhängig und deshalb kann man mit Pascal nicht ohne Zusatz-Angeben C-Funktionen aufrufen. Es gibt entsprechende Keywords - z.B. "stdcall" - die man angeben kann, wenn man eine andere als die FPC-Standard-Aufruf-Konvention verwenden möchte. Übrigens ist die Aufruf-Konvention in FPC und Delphi gleich, so dass die einzige Vorkehrung, die getroffen werden muss, wenn man den Quellcode auch in Delphi verwenden will das bedingte kompilieren von "{$asmmode..." ist.

Ich habe mir die ABI-Definition für den 64 Bit Modus noch nicht angeschaut, da gibt es ja nicht nur doppelt so große, sondern auch doppelt so viele Register. u.U. werden da mehr Parameter in Registern und weniger über den Stack transportiert.

Ich weiß auch nicht, ob man in einem ASM-Programm nicht sogar einfach den 64 Bit Modus verwenden kann, auch wenn der Rest für 32 Bit kompiliert ist. (Wird aber sicherlich nur funktionieren, wenn wir in einem 64-Bit Betriebssystem arbeiten, weil ein 32 Bit Betriebssystem die zusätzlichen Bits und Register beim Task-Wechsel ja nicht restauriert. Aber im 64 Bit Linux und Windows kann man schließlich für 32 Bit kompilierte Programme durchaus aufrufen. )

Die erhöhte Register-Zahl wird bei den "addsubb" und "subsub" sehr helfen. Im 32 Bit Modus müssen hier nämlich mangels Arbeitsregistern Zwischenspeicher auf dem Stack angelegt und in der Schleife verwendet werden - und der Transport von Werten in und aus dem innersten CPU-Kern kann einiges an Verarbeitungsgeschwindigkeit kosten.

-Michael

[marcov]

(ein Tip: wenn man auf 64-bit mit 64-bit Typen, und auf 32-bit mit 32-bit rechnet bekommt man Endianess Probleme wenn man auf 64-bit etwas ein Großzahl speichert (zb blockwrite) und wieder auf 32-bit lest, und vice versa.

Wieso ?
Sowohl der 32 Bit als auch der 64 Bit modus der x86 CPU arbeiten "low endien first". d.h. im Speicher steht in der Zahl auf

Aber das sind nicht die einzige architecturen die FPC/Lazarus unterstutzen. PowerPC und Arm sind (meistens (*)) big endian. Und PPC gibts es in 64-bit.

Das war glaube ich anfangs PowerPC support ein Problem, weil der "SET OF" code einmal "byte-wise" andermal "longint-wise" zugraf auf Sets.

(*) ich glaube die Cores von beiden sind im Grund Endianness agnostisch, und der Chipsatz bestimmt die Endianess des Systems. Meistens (>90%) bigendian. Little endian PPC is sehr seltsam, aber ARM little endian (ARMLE) kann man finden.

(**) Moderator Bitte die naechste Nachricht löschen.

[marcov]

(ein Tip: wenn man auf 64-bit mit 64-bit Typen, und auf 32-bit mit 32-bit rechnet bekommt man Endianess Probleme wenn man auf 64-bit etwas ein Großzahl speichert (zb blockwrite) und wieder auf 32-bit lest, und vice versa.

Wieso ?
Sowohl der 32 Bit als auch der 64 Bit modus der x86 CPU arbeiten "low endien first". d.h. im Speicher steht in der Zahl auf

Aber das sind nicht die einzige architecturen die FPC/Lazarus unterstutzen. PowerPC und Arm sind (meistens (*)) big endian. Und PPC gibts es in 64-bit.

Das war glaube ich anfangs PowerPC support ein Problem, weil der "SET OF" code einmal "byte-wise" andermal "longint-wise" zugraf auf Sets.

(*) ich glaube die Cores von beiden sind im Grund Endianness agnostisch, und der Chipsatz bestimmt die Endianess des Systems. Meistens (>90%) bigendian. Little endian PPC is sehr seltsam, aber ARM little endian (ARMLE) kann man finden.

[marcov]

Das ist Bestandteil des ABI (Application Binary Interface), das regelt, wie ein Compiler Unterprogramme aufruft. Das ist Compiler-abhängig und deshalb kann man mit Pascal nicht ohne Zusatz-Angeben C-Funktionen aufrufen. Es gibt entsprechende Keywords - z.B. "stdcall" - die man angeben kann, wenn man eine andere als die FPC-Standard-Aufruf-Konvention verwenden möchte.

Und register; ist die standard Konvention

Übrigens ist die Aufruf-Konvention in FPC und Delphi gleich, so dass die einzige Vorkehrung, die getroffen werden muss, wenn man den Quellcode auch in Delphi verwenden will das bedingte kompilieren von "{$asmmode..." ist.

Seit 1.9.8 ja. {$mode delphi} macht auch {$asmmode intel}

Ich habe mir die ABI-Definition für den 64 Bit Modus noch nicht angeschaut, da gibt es ja nicht nur doppelt so große, sondern auch doppelt so viele Register. u.U. werden da mehr Parameter in Registern und weniger über den Stack transportiert.

Ich weiß auch nicht, ob man in einem ASM-Programm nicht sogar einfach den 64 Bit Modus verwenden kann, auch wenn der Rest für 32 Bit kompiliert ist. (Wird aber sicherlich nur funktionieren, wenn wir in einem 64-Bit Betriebssystem arbeiten, weil ein 32 Bit Betriebssystem die zusätzlichen Bits und Register beim Task-Wechsel ja nicht restauriert. Aber im 64 Bit Linux und Windows kann man schließlich für 32 Bit kompilierte Programme durchaus aufrufen. )

Das ist etwas anders. Zwei unterschiedliche Prozesse in resp. 32 und 64-bit, oder 32-bit und 64-bit in ein und demselben Prozess. Ich glaube das letzte ist nicht moeglich. (db 66 macht 16-bit, nicht 64-bit in 32-bit modus)

Aber man konnte versuchen das mit SSE2/3 zu machen. 128-bit als 8 x 16-bit. Man muss dann doch den Overflow selber machen. Ich weiss aber nicht ob das moeglich ist, aber (pseudo SSE) code würde so aussehen:

//saturation AUS.
xor xmm3,xmm3
.Lstart:

load xmm1,ptr (8x16-bit)
add xmm1,xxm3 // overflow of last cycle
load xmm2,ptr(8x16-bit)
.loverflow
add xmm1,xmm2 // *
setc xmm2 // * store 8 overflows to xmm2
cmp xmm2,0 // check for all but
jne loverflow
shift xmm2,7*16-bit. // keep highest overflow
mov xmm2,xmm3 // move to xmm3
inc(ptr1,16);
inc(ptr2,16);
test for end
jne .Lstart

die mit (*) markierten instructionen sind das Problem. Die Addition muss möglich sein mit 8x Carry (erster *), und es muss möglich sein die 8x Carry nach ein Register zu storen. (zweiter *)

[mschnell]

Aber das sind nicht die einzige architecturen die FPC/Lazarus unterstutzen.

Da hast Du natürlich vollkommen recht. Der Code (auch die Pascal-Teile) müssen entsprechenden Kompiler-Optionen bekommen. Ich halte es für sehr schlecht, Langzahlen-Arithmetik anders einzubauen, als die Hardware des Prozessors vorgibt.

PowerPC und Arm sind (meistens (*)) big endian. Und PPC gibts es in 64-bit.

Soweit ich weiß kann man beide Cores softwaremäßig umschalten (PPC hat zusätzlich noch einen ganz merkwürdigen Modus mit verdrehter Byte-Ordnung, der aber wohl nie benutzt wird). Wenn ich mich recht erinnere, wird PPC (in Linux, Mac: gar keine Ahnung) als "high byte first" verwendet (kommt wohl aus der 68K-Tradition), ARM wird (in Linux, WinCE: gar keine Ahnung) aber "low-Byte first" (wie X86) verwendet. Oder ?

-Michael

[mschnell]

Noch ein Paar ideen zur Optimierung des 32-Bit "add" in ASM:

1)
Ich habe die Adressierung mit 2 Registern verwendet. Das spart gegenüber drei laufenden Pointern einen Befehl, benötigt aber eine arithmetische Operation mehr. Man könnte auch diesen Code probieren:

Code: Alles auswählen

@loop:
  mov esi, [edx]
  adc esi, [ecx]
  mov [eax], esi
  lea edx, [edx+4]
  lea ecx, [ecx+4]
  lea eax, [eax+4]
  dec ebx
  jnz @loop

Was schneller ist, müsste man testen.

2)
Da vermutlich der Sprung am Ende der Schleife viel Zeit kostet, könnte man "Loop Enrolling" machen.
z.B:

Code: Alles auswählen

@loop:
  mov esi, [edx+edi]
  adc esi, [ecx+edi]
  mov [eax+edi], esi
  lea edi, [edi+4]   //edi = edi + 4 without affecting carry
  dec ebx
@l2:
  mov esi, [edx+edi]
  adc esi, [ecx+edi]
  mov [eax+edi], esi
  lea edi, [edi+4]   //edi = edi + 4 without affecting carry
  dec ebx
  jnz @loop

(Vorher Schleifenzähler halbieren und bei ungerade nach l2 springen )

Vielleicht noch besser sogar vier oder 8 Schleifendurchläufe ausrollen.
Man müsste ausprobieren, was das bringt.

-Michael

[mschnell]

(db 66 macht 16-bit, nicht 64-bit in 32-bit modus)

Ich kann mich erinnern, dass Du da vermutlich recht hast. Also 64 Bit Arithmetik(ohne SSE) nur bei echten 64 Bit Programmen.
-Michael

[Euklid]

Hallo Michael,

habe heute die beiden neuen Geschwindigkeitsoptimierungen getestet.

Optimierung 1) bringt einen Geschwindigkeitsvorteil von unter 1%.
Optimierung 2) verkürzt die Zeit zur Berechnung immerhin um 3%. Wenn ich deinen ASM-Code betrachte, erscheit mir diese Optimierung aber noch nicht fertig programmiert? @l2 wird garnicht benutzt. Wenn ich richtig liege, funktioniert der Code nur für eine gerade Stellenanzahl.

Werde die ASM-Optimierung im Laufe der nächsten Tage einbauen und dann im Rahmen einer 0.99.5 veröffentlichen. Werde voraussichtlich nochmal schaun, ob man am Algorithmus der Multiplikation noch etwas schrauben kann. Jedenfalls sind mir noch Wege eingefallen, die ich durch Laufzeittests überprüfen möchte.

Viele Grüße, Euklid

[mschnell]

Optimierung 2) verkürzt die Zeit zur Berechnung immerhin um 3%. Wenn ich deinen ASM-Code betrachte, erscheit mir diese Optimierung aber noch nicht fertig programmiert?

Da hast Du recht. Das war erstmal nur ein Entwurf. Der Counter wird ja auch noch gar nicht dividiert. Den Einlauf-Code mache ich gleich 'mal, damit Du testen kannst.

Hier die Variante mit vierfachem Loop-Enrolling.

Code: Alles auswählen

procedure GNZAddInternal(var s, s1, s2: GNZBaseType; length: Integer); assembler;
asm
  push ebx           // s, s1 and s2 already are eax, edx and ecx
  push esi
  push edi
  mov  ebx, length
  mov  edi, ebx
  shr  ebx, 2
  and  edi, 3         // clear carry       (finally edi=0).
  jz   @loop
  inc  ebx
  dec  edi
  jz   @l1
  dec  edi
  jz   @l2
  dec  edi
  jmp   @l3
@loop:
  mov esi, [edx+edi]
  adc esi, [ecx+edi]
  mov [eax+edi], esi
  lea edi, [edi+4]   //ebp = ebp + 4 without affecting carry
@l3:
  mov esi, [edx+edi]
  adc esi, [ecx+edi]
  mov [eax+edi], esi
  lea edi, [edi+4]   //ebp = ebp + 4 without affecting carry
@l2:
  mov esi, [edx+edi]
  adc esi, [ecx+edi]
  mov [eax+edi], esi
  lea edi, [edi+4]   //ebp = ebp + 4 without affecting carry
@l1:
  mov esi, [edx+edi]
  adc esi, [ecx+edi]
  mov [eax+edi], esi
  lea edi, [edi+4]   //ebp = ebp + 4 without affecting carry
  dec ebx
  jnz @loop
  pop edi
  pop esi
  pop ebx
end;

Gruß,

-Michael

[mschnell]

Die "SubSub" Funktion könnte so aussehen:

Code: Alles auswählen

procedure GNZSubSubInternal(var s, s1, s2, s3: GNZBaseType; length: Integer); assembler;
var
  stemp, s1temp: Pointer;
asm                   // s, s1 and s2 are eax, edx and ecx.
  push ebx
  push esi
  push edi
  mov  stemp, eax     // s  -> temp.
  mov  s1temp, edx    // s1 -> t1emp.
  mov  ebx, length
  xor  edi, edi       // rbp = 0 .
  xor  eax, eax       // carry eax = 0.
 
@loop:                // eax = 0 or 1 or 2 or 3.
  mov  edx, s1temp
  mov  esi, [edx+edi] // s1.
  sub  esi, eax       // - carry.
  mov  eax, 0
  adc  eax, 0         // 0 or -1.
  sub  esi, [ecx+edi] // s2.
  adc  eax, 0         // eax = 0 or -1 or -2.
  mov  edx, s3
  sub  esi, [edx+edi]
  adc  eax, 0         // eax = 0 or -1 or -2 or -3.
  mov  edx, stemp
  mov  [edx+edi], esi
  lea  edi, [edi+4]   //ebp = ebp + 4 without affecting carry
  dec  ebx
  jnz  @loop
  pop  edi
  pop  esi
  pop  ebx
end;
 
 
function GNZSubSub(s1, s2, s3: GNZType): GNZType;
begin
  setlength(Result, length(s1));
  GNZSubSubInternal(Result[0], s1[0], s2[0], s3[0], length(s1));
end;

Ob das allerdings was bringt, kann man nur ausprobieren. In der Schleife ist recht viel Code, ob das den Vorteil ausgleicht, dass das Zwischenergebnic nicht gespeichert werden muss, ist fraglich.

-Michael