| |
| Autor |
 iterativer Benchmark "Mul, Add, Sub, cmp 256 Bit Int" in mehreren Sprachen |
|
hyperG
Senior 
Dabei seit: 03.02.2017
Mitteilungen: 2158
 |  Beitrag No.40, vom Themenstarter, eingetragen 2023-09-01
|
Und das bekannte JAVA:
\sourceon JAVA
public static void main(String[] args) {
long N,start,stop, nad=0, nsu=0;
BigInteger a = new BigInteger("170141183460469231731687303715884105757");
BigInteger b = new BigInteger("170141183460469231731687303715884105703");
BigInteger c = new BigInteger("9");
BigInteger zwei = new BigInteger("2");
BigInteger soll = new BigInteger("255");
BigInteger sub = new BigInteger("10");
BigInteger zHoch128m1 = new BigInteger("340282366920938463463374607431768211455");
soll=zwei.pow(255);
sub=sub.pow(77).subtract(BigInteger.ONE).divide(c);
System.out.println(sub);
start = System.currentTimeMillis();
for(N = 0; N < 25000000; N+=1)
{ c=a.multiply(b);
while(c.compareTo(soll)<0) //
{ c=c.add(sub);nad+=1;
}
while(c.compareTo(soll)>0)
{ c=c.subtract(sub);nsu+=1;
}
a=c.shiftRight(128); b=c.and(zHoch128m1);
}
stop = System.currentTimeMillis();
System.out.println("add="+String.valueOf(nad)+ " su="+String.valueOf(nsu)+" in "+String.valueOf((stop - start)/1000.000)+" s");
System.out.println(c);//
}
\sourceoff
Ergebnis:
\sourceon nameDerSprache
11111111111111111111111111111111111111111111111111111111111111111111111111111
add=83884810 su=25000000 in 5.451 s
47306219819553867530681020915755484915944251665601642944764215683054098939729
\sourceoff
Da es shr + and gibt -> sehr schnell!
|
 Profil
|
schnitzel
Senior 
Dabei seit: 26.02.2009
Mitteilungen: 227
 | Beitrag No.41, eingetragen 2023-09-02
|
Aus Interesse habe ich nochmal die optimierte Java Version uebersetzt. (Auch die wird online nicht funktionieren):
hier
\sourceon rust
// needs:
// cargo add ethnum;
use ethnum::U256;
use std::time::Instant;
fn main() {
let ten = &U256::new(10);
let two = &U256::new(2);
let soll = two.pow(255);
let z = two.pow(128) - 1;
let sub = ten.pow(77) / 9;
let mut a = two.pow(127) + 29;
let mut b = two.pow(127) - 25;
let mut c = U256::new(0);
let mut nad = 0u64;
let mut nsu = 0u64;
let watch = Instant::now();
for _nn in 0..25_000_000 {
c = &a * &b;
while &c < &soll {
c += ⊂
nad += 1;
}
while &c > &soll {
c -= ⊂
nsu += 1;
}
a = &c >> 128;
b = &c & &z;
}
let duration = watch.elapsed();
println!("c {:?}", c);
println!("ad={:?} su={:?} in {} s", nad, nsu, duration.as_secs_f64());
}
\sourceoff
\sourceon
c 47306219819553867530681020915755484915944251665601642944764215683054098939729
ad=83884810 su=25000000 in 0.485019033 s
\sourceoff
Ich hoffe, dass da nicht irgendein caching im Hintergrund läuft...
Gruss
|
Profil
|
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 2158
| Beitrag No.42, vom Themenstarter, eingetragen 2023-09-02
|
\quoteon(2023-09-02 08:44 - schnitzel in Beitrag No. 41)
Aus Interesse habe ich nochmal die optimierte Java Version uebersetzt. (Auch die wird online nicht funktionieren):
hier
...
\sourceon
c 47306219819553867530681020915755484915944251665601642944764215683054098939729
ad=83884810 su=25000000 in 0.485019033 s
\sourceoff
Ich hoffe, dass da nicht irgendein caching im Hintergrund läuft...
Gruss
\quoteoff
Wow, neuer Rekord, der bei Dir schon mehr als doppelt so schnell wie mein Rekord war und mit meiner CPU dann nochmal schneller?!?!
https://matheplanet.com/matheplanet/nuke/html/uploads/c/47407_Bench256BitMulAddSub_Rust2.PNG
Das schafft man eigentlich nur mit AVX-Befehlen (und genau die suche ich für mul256) oder mit mehreren Threads.
Wo gibt's den Compiler & was musste eingebunden werden?
(Ist die Install für Win von https://www.rust-lang.org/learn/get-started ?)
Die EXE ist für dieses kleine Programm 1000 mal größer als mein Rekord.
(damit wird das Re-ASM so gut wie unmöglich)
Vermutlich wird eine Bibl. komplett mit eingebunden...
Scheint auch eine Mischung aus zig Sprachen zu sein (gcc,
x86_64-w64-mingw32-x86_64-w64-mingw32-crt, mpmc library\core\src\num library\core\src\iter\traits library\std\src\net library\std\src\ffi library,...
Verdächtig ist die CPU-Last: während alle anderen Programme bei 1 Kern kurz auf 100% springen, sind es hier 2 Kerne, die kurz nur auf 5 % springen?
Nicht dass der Compiler schon alles zusammenfasst und das Ergebnis in die EXE mit hineinpackt?
Könntest Du die Laufvariable von 25 Mio mindestens auf 125 Mio. vergrößern (oder mit Eingabe oder Übergabeparameter), damit ich die Kernlast besser beobachten kann?
Sehr interessant alles!
|
Profil
|
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 2158
| Beitrag No.43, vom Themenstarter, eingetragen 2023-09-02
|
Bei YMP (NumberFactory) wollte ich ja divmod optimieren, da wir das ja als "Bremse" identifizierten:
https://matheplanet.com/matheplanet/nuke/html/uploads/c/47407_Bench256BitMulAddSub_ymp_25Mio_8sK.PNG
Mit "Anzapfen" der "inneren Ptr" + 4 SSE/AVX-Befehlen nun also mehr als doppelt so schnell -> damit dürften alle anderen Programme spätestens ab 1000 Stellen überholt werden...
|
Profil
|
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 2158
| Beitrag No.44, vom Themenstarter, eingetragen 2023-09-02
|
Zur Referenz "c++ VC 2017 + ASM + mul256ASMminGW.obj" mit 1 s:
Da der Hi-Teil der 256-Bit Variablen a und b immer 0 bleibt,
reicht statt zwei 265_loadu2
zwei _mm_load_si128 aus,
was statt 1.000 s nun 0.978 s ergibt.
Die exe ist nur 24064 Byte groß!
Bei Mathematica scheinen die Bit-Manipulationsbefehle {BitShiftRight[c,128] + BitAnd } hingegen aller anderen Programme
nicht schneller, sondern 7 s langsamer als divmod {QuotientRemainder }
zu werden?! (schlechte Umsetzung?)
Wo bleiben die maple Fans?
|
Profil
|
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 2158
| Beitrag No.45, vom Themenstarter, eingetragen 2023-09-02
|
So, rust installiert und nach Anweisung
C:\Users\...\mul256add>cargo --offline build
Compiling mul256add v0.1.0 (C:\Users\...\mul256add)
error[E0432]: unresolved import `ethnum`
--> src\main.rs:3:5
|
3 | use ethnum::U256;
| ^^^^^^ use of undeclared crate or module `ethnum`
For more information about this error, try `rustc --explain E0432`.
error: could not compile `mul256add` (bin "mul256add") due to previous error
Wie binde ich ethnum ein? https://crates.io/crates/ethnum
oder?
muss bestimmt in Cargo.toml darauf verwiesen werden?
assets = "path/to..." ?
|
Profil
|
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 2158
| Beitrag No.46, vom Themenstarter, eingetragen 2023-09-02
|
https://github.com/nlordell/ethnum-rs/tree/main heruntergeladen
dann Firewall geöffnet (gefällt mir nicht!)
cargo add ethnum
Updating crates.io index
warning: spurious network error (3 tries remaining): [6] Couldn't resolve host name (getaddrinfo() thread failed to start)
warning: spurious network error (2 tries remaining): [6] Couldn't resolve host name (getaddrinfo() thread failed to start)
warning: spurious network error (1 tries remaining): [6] Couldn't resolve host name (getaddrinfo() thread failed to start)
error: failed to query replaced source registry `crates-io`
Caused by:
download of config.json failed
Caused by:
failed to download from `https://index.crates.io/config.json`
Caused by:
[6] Couldn't resolve host name (getaddrinfo() thread failed to start)
C:\Users\gl\mul256add>cargo add ethnum
Updating crates.io index
warning: spurious network error (3 tries remaining): [6] Couldn't resolve host name (getaddrinfo() thread failed to start)
warning: spurious network error (2 tries remaining): [6] Couldn't resolve host name (getaddrinfo() thread failed to start)
warning: spurious network error (1 tries remaining): [6] Couldn't resolve host name (getaddrinfo() thread failed to start)
error: failed to query replaced source registry `crates-io`
Caused by:
download of config.json failed
Caused by:
failed to download from `https://index.crates.io/config.json`
Caused by:
[6] Couldn't resolve host name (getaddrinfo() thread failed to start)
...trotzdem Err!!
https://index.crates.io/config.json heruntergeladen
aber wo soll die hin? umständlicher geht's nicht :-(
|
Profil
|
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 2158
| Beitrag No.47, vom Themenstarter, eingetragen 2023-09-02
|
LUA: (Dank an Pascal)
\sourceon LUA
local ffi = require("ffi")
ffi.cdef("unsigned __stdcall GetTickCount(void);")
local kernel32 = ffi.load("KERNEL32")
local now = ffi.C.GetTickCount
local gmp = require("gmp-binding")("libgmp-10") -- GMP DLL
local mpz = gmp.types.z
-- Benchmark
local a, b, c = mpz(), mpz(), mpz()
local soll, diff, mpz_zHoch128m1 = mpz(), mpz(), mpz()
local nn =0
local nad =0
local nsu =0
local start_time = os.clock()*1.000
gmp.z_init_set_str(a, "170141183460469231731687303715884105757", 10)
gmp.z_init_set_str(b, "170141183460469231731687303715884105703", 10)
gmp.z_init_set_str(soll, "57896044618658097711785492504343953926634992332820282019728792003956564819968", 10)
gmp.z_init_set_str(diff, "11111111111111111111111111111111111111111111111111111111111111111111111111111", 10)
gmp.z_init_set_str(mpz_zHoch128m1, "340282366920938463463374607431768211455", 10)
while nn < 25000000 do
gmp.z_mul(c, a, b)
while gmp.z_cmp(c, soll) < 0 do
gmp.z_add(c, c, diff)
nad = nad + 1
end
while gmp.z_cmp(c, soll) > 0 do
nsu = nsu + 1
gmp.z_sub(c, c, diff)
end
gmp.z_tdiv_q_2exp(a, c, 128) --gmp.z_fdiv_q(a, c, huge) 5 s
gmp.z_and(b, c, mpz_zHoch128m1) --gmp.z_mod(b, c, mpz_zHoch128)
nn = nn + 1
end
gmp.printf("c=%Zd\nnad=%.0f\nnsu=%.0f\n in %.3f s\n", c, nad, nsu, (os.clock()*1.0 - start_time)/1.000)
\sourceoff
\sourceon Ergebnis
c=47306219819553867530681020915755484915944251665601642944764215683054098939729
nad=83884810
nsu=25000000
in 2.152 s
\sourceoff
Eigentlich ein Verstoß gegen Regel f),
da hier die GMP.DLL eingebunden wurde und diese in c geschrieben ist.
Der dahinter steckende Interpreter verlangsamt die
"Original c-Zeit" von 1.98 s auf 2.152 s
Hinweis:
Ich konnte die schnellste exe von schnitzel genauer untersuchen:
- kein AVX Befehl
- kein Multitasking
- bei 10 mal größeren Schleifen ist meine Referenz 3,37 mal langsamer
- Suche nach der schnellen Mul läuft...
|
Profil
|
AlphaSigma
Senior
Dabei seit: 23.11.2012
Mitteilungen: 462
| Beitrag No.48, eingetragen 2023-09-03
|
\quoteon(2023-08-30 22:16 - hyperG in Beitrag No. 6)
Liste der fehlenden Codes,
wo ich mich über Hilfe freuen würde...
\sourceon nameDerSprache
GP/Pari
JAVA
JavaScript
php
bc
PureBasic
c++ per Linux gcc
...
\sourceoff
\sourceon weitere Sprachen, an die ich nicht einfach herankomme
Haskell danke tactac!
maple
...
\sourceoff
\quoteoff
Wenn bc gefragt ist, darf dc (engl. wikipedia) natürlich auch nicht fehlen.
bench256.dc
\sourceon dc
2 127^29+sa # a = 2^127+29
2 127^25-sb # b = 2^127-25
2 255^st # t = 2^255
10 77^1-9/ss # s = (10^77 - 1) / 9
0su # init up counter
0sd # init down counter
0se # init main loop counter
[ls+dlu1+sult>g]sg # add s loop
[ls-dld1+sdlty]sy # main loop
lyx lcp lup ldp
\sourceoff
\sourceon bash
dc$ time dc -f bench256.dc
47306219819553867530681020915755484915944251665601642944764215683054098939729
83884810
25000000
real 13m30.476s
user 13m29.671s
sys 0m0.145s
\sourceoff
dc braucht, wie erwartet, etwa so lange wie bc und ist deutlich langsamer als die nur auf 256 Bit Arithmetik optimierten Programme.
P.S. Forth wäre auch noch interessant.
|
Profil
|
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 2158
| Beitrag No.49, vom Themenstarter, eingetragen 2023-09-03
|
PureBasic: (Dank an Helle für die DLL)
\sourceon PureBasic
XIncludeFile "UnlimitedIntegerArithmetic.dll.pbi"
Define.Z za, zb, zc, zsoll, z255, zsub, z77, z1,z9,zh128
Z_Number(za,"170141183460469231731687303715884105757")
Z_Number(zb,"170141183460469231731687303715884105703")
Z_Number(zh128,"340282366920938463463374607431768211456")
Z_Number(zc,"0")
Z_Number(zsoll,"2")
Z_Set(z255, 255)
Z_Power(zsoll, z255)
Z_Set(zsub, 10)
Z_Set(z77, 77)
Z_Power(zsub, z77)
Z_Set(z1, 1)
Z_Subtract(zsub, z1)
Z_Set(z9, 9)
Z_Divide(zsub,z9)
nad.q=0
nsu.q=0
If OpenConsole()
PrintN("Schleifenanzahl (25000000):");
strIn.s=Input()
uEnde.q=Val(strIn.s)
TA = ElapsedMilliseconds()
i.q=0
Repeat
Z_Copy(zc,za)
Z_Multiply(zc, zb)
While Z_Compare(zc,zsoll)< 0
Z_Add(zc,zsub)
nad.q=nad.q+1
Wend
While Z_Compare(zc,zsoll)> 0
Z_Subtract(zc,zsub)
nsu.q=nsu.q+1
Wend
Z_Copy(za,zc)
Z_Divide(za,zh128) ; Z_Shift funktioniert nur langsam mit -1 :-(
Z_Copy(zb,zc)
Z_Modulo(zb,zh128)
i.q=i.q+1;
Until (i.q>=uEnde.q)
zeit.d=(ElapsedMilliseconds() - TA)
PrintN("fertig in "+StrD(zeit.d/1000.000)+" s")
PrintN("ad="+StrU(nad.q)+" asu="+StrU(nsu.q));
PrintN(Z_String(zc))
Input()
CloseConsole()
EndIf
End
\sourceoff
\sourceon Ergebnis
Schleifenanzahl (25000000):
25000000
fertig in 58.655 s
ad=83884810 asu=25000000
47306219819553867530681020915755484915944251665601642944764215683054098939729
\sourceoff
Leider funktioniert das Z_Shift nur mit Parameter -1 (also durch 2), und dann auch noch sehr langsam :-(
Zugabe:
Der Trick mit CopyMemory als Ersatz für Modulo funktionierte teilweise:
- musste mit nochmaligem Copy über Hilfsvariablen repariert werden
- bei Divide funktionierte es nicht (immer Absturz auch bei nur 8 Byte)
Immerhin eine Verbesserung auf 38.935 s
|
Profil
|
pzktupel
Aktiv
Dabei seit: 02.09.2017
Mitteilungen: 2456
Wohnort: Thüringen
 | Beitrag No.50, eingetragen 2023-09-06
|
Update:
Die Geschindigkeit halbierte sich nach einem Update.
\sourceon nameDerSprache
#INCLUDE "windows.bi"
#INCLUDE "vbcompat.bi"
#include "Big-Int overload.bi"
DIM AS ULONG nad,nsu,nn
DIM AS BIGINT A,B,C,D,soll,subb,q3,r3
DIM AS DOUBLE TI
Sub divext(Byref a As bigint, Byref b As bigint, Byref q As bigint, Byref r As bigint)
big_int_div_extended(a.numptr, b.numptr, q.numptr, r.numptr)
End Sub
a="170141183460469231731687303715884105757"
b="170141183460469231731687303715884105703"
soll="57896044618658097711785492504343953926634992332820282019728792003956564819968"
subb="11111111111111111111111111111111111111111111111111111111111111111111111111111"
d="340282366920938463463374607431768211456"
nad = 0
nsu = 0
c="0"
TI=timer
nn=0
WHILE nn<25000000
c = a * b
while c < soll
c += subb
nad+=1
wend
while c > soll
c -= subb
nsu+=1
wend
divext(c,d,a,b)
nn+=1
WEND
print "c=";c
print "nad=";nad
print "sub=";nsu
PRINT TIMER-TI;" s"
SLEEP
\sourceoff
\sourceon nameDerSprache
c=47306219819553867530681020915755484915944251665601642944764215683054098939729
nad=83884810
sub=25000000
~42 s
\sourceoff
|
Profil
|
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 2158
| Beitrag No.51, vom Themenstarter, eingetragen 2023-09-06
|
Danke pzktupel,
wie zu erwarten bringt die Zusammenfassung von div & mod zu 1 Befehl natürlich richtig was.
Bei mir nun 27.8367 s
Shr + AND sollte noch schneller sein...
Trage es in große Liste ein.
|
Profil
|
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 2158
| Beitrag No.52, vom Themenstarter, eingetragen 2023-09-06
|
Bei Python bringt der Ersatz von Div & Mod durch divmod:
\sourceon Python
zH128=2**128
...
a,b=divmod(c,zH128)
\sourceoff
jedoch nur eine kleine Verbesserung von 38.4 s auf 30.8 s.
Bei SAGE ist divmod erst in der neusten Version bekannt -> kann daher mit dem online-Interpreter nicht getestet werden.
|
Profil
|
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 2158
| Beitrag No.53, vom Themenstarter, eingetragen 2023-09-06
|
Auch an der Spitze hat sich was getan:
Den ethnum-Code für RUST "umulddi3()" habe ich in eine cpp gewandelt,
die MinGW versteht (MS VC kennt ja kein __int128 ):
\sourceon cpp
void umulddi3(unsigned __int128*a, unsigned __int128 *b, unsigned __int128 c[2])
\sourceoff
Mit https://godbolt.org cpp -> ASM (MinGW für Win) -> ASM -> OBJ
und diese OBJ in cpp von VC 2017 eingebunden: 0.96 s statt 1 s.
( die Verschlechterung von 0.978 s auf 1 s kam nur durch winzige Änderungen für variable Übergabeparameter statt feste 25000000 Schleifengröße)
Die ethnum-Bib konnte ich nun auch in RUST einbinden (erforderte totale Freischaltung der Firewall in beide Richtungen, was ich nur sehr ungern mache), was tatsächlich den Code von #41 zu einer exe führte:
debug : 9.74 s (zwar leichtes Re-ASM, aber unbrauchbar langsam)
release: 0.364 s krasse Optimierung! exe 197 k
Wie schnitzel seine exe noch schneller bekommen hat (0.296 s),
hat er noch nicht verraten... Auch die Größe von 5,5 MB zeigt, dass da die ganze Bib. eingebunden wurde, was ein Re-ASM (wie bereits geschrieben) verkompliziert.
(könnte auch eine Optimierung per https://rustc-dev-guide.rust-lang.org/backend/updating-llvm.html sein...)
Ich schaue mir aber noch add256 genauer an, denn meine AVX-Umsetzung in cpp gefällt mir noch nicht richtig...
Immer noch kein maple , Fortran,...
|
Profil
|
AnnaKath
Senior
Dabei seit: 18.12.2006
Mitteilungen: 3858
Wohnort: hier und dort (s. Beruf)
 | Beitrag No.54, eingetragen 2023-09-07
|
\(\begingroup\)\(\newcommand{\C}{\mathbb{C}}
\newcommand{\E}{\mathbb{E}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\i}{\mathrm{i}}
\newcommand{\d}{\mathrm{d}} \)
Huhu zusammen,
ich muss zugeben, mich ein wenig geärgert zu haben, dass "meine" Sprache C# so schlecht abgeschnitten hat*. Deshalb haben wir** uns noch ein wenig hiermit beschäftigt.
Selbstverständlich verfügt auch C# über effizientere Implementierungen von Algorithmen. Wir haben allerdings keinen Intel-Prozessor im Haus und so haben wir auf tactacs Unterstützung zurückgegriffen***.
Hier einmal ein paar Performance-Daten:
Erster Algorithmus aus diesem Thread:
Laufzeit (AK) 6,08 s
Laufzeit (tt) 30,40 s
Verbesserter Code (ohne Hardware-Beschleunigung)
Laufzeit (AK) 2,15 s
Laufzeit (tt) 19,92 s
Verbesserter Code (mit Hardware-Beschleunigung)
Laufzeit (AK) 1,02 s (ARM-Optimierung)
Laufzeit (tt) 10,82 s (x86-Optimierung)
Dabei haben wir selbstverständlich nur die aktuelle Laufzeitumgebung, C#11 kompatiblen Code und die Standard-Bibliothek genutzt. Die Performance lässt sich also bereits mit Bordmitteln um 281% (tactac) bis 596% (AK) erhöhen.
Dabei haben wir noch nicht einmal den Code direkt kompiliert, sondern nach wie vor den JIT-Compiler genutzt. Allerdings habe ich die GarbageCollection für die Ausführung unterdrückt, was aber natürlich alles im Rahmen von "gültigem Code" sein dürfte.
lg, AK
PS. Hier des Testcode (allerdings sind die UInt256* Typen natürlich noch selbst implementiert, beispielsweise wird ein Auszug des nicht-hardware-optimierten Codes angegeben):
\showon
\sourceon C#
using System;
using System.Numerics;
using System.Diagnostics;
using System.Runtime.Intrinsics.Arm;
using System.Runtime.Intrinsics.X86;
using AK.MP.Performance;
bool flag = GC.TryStartNoGCRegion(1024);
var (nad, nsu) = (0ul, 0ul);
var a = BigInteger.Parse("170141183460469231731687303715884105757");
var b = BigInteger.Parse("170141183460469231731687303715884105703");
var c = BigInteger.Parse("9");
var soll = BigInteger.Pow(BigInteger.Parse("2"), 255);
var sub = (BigInteger.Pow(BigInteger.Parse("10"), 77) - BigInteger.One) / c;
Stopwatch s = new();
if(Avx2.IsSupported)
{
// optimized code & using hardware acceleration (Intel x86)
var a1 = (UInt256x86)a;
var b1 = (UInt256x86)b;
var c1 = (UInt256x86)c;
var soll1 = (UInt256x86)soll;
var sub1 = (UInt256x86)sub;
Console.WriteLine("Avx2");
s.Start();
nad = 0; nsu = 0;
for(ulong N = 0; N < 25000000; N++)
{
c1 = a1 * b1;
while(c1 < soll1) { c1 += sub1; nad++; }
while(c1 > soll1) { c1 -= sub1; nsu++; }
UInt256x86.DivMod128(in c1, out a1, out b1);
}
s.Stop();
Console.WriteLine($"add={nad} su={nsu} in {s.ElapsedMilliseconds / 1000.0:F4} s");
Console.WriteLine(c1);
}
else if(AdvSimd.IsSupported)
{
// optimized code & using hardware acceleration (Arm / Apple M2)
var a1 = (UInt256arm)a;
var b1 = (UInt256arm)b;
var c1 = (UInt256arm)c;
var soll1 = (UInt256arm)soll;
var sub1 = (UInt256arm)sub;
Console.WriteLine("AdvSimd");
s.Start();
nad = 0; nsu = 0;
for(ulong N = 0; N < 25000000; N++)
{
c1 = a1 * b1;
while(c1 < soll1) { c1 += sub1; nad++; }
while(c1 > soll1) { c1 -= sub1; nsu++; }
UInt256arm.DivMod128(in c1, out a1, out b1);
}
s.Stop();
Console.WriteLine($"add={nad} su={nsu} in {s.ElapsedMilliseconds / 1000.0:F4} s");
Console.WriteLine(c1);
}
// optimized code, no hardware acceleration
Console.WriteLine("UInt256 (generic)");
var a2 = (UInt256)a;
var b2 = (UInt256)b;
var c2 = (UInt256)c;
var soll2 = (UInt256)soll;
var sub2 = (UInt256)sub;
s.Start();
nad = 0; nsu = 0;
for(ulong N = 0; N < 25000000; N++)
{
c2 = a2 * b2;
while(c2 < soll2) { c2 += sub2; nad++;}
while(c2 > soll2) { c2 -= sub2; nsu++;}
UInt256.DivMod128(in c2, out a2, out b2);
}
s.Stop();
Console.WriteLine($"add={nad} su={nsu} in {s.ElapsedMilliseconds / 1000.0:F4} s");
Console.WriteLine(c2);
// MP sample code
var zHoch128m1 = BigInteger.Parse("340282366920938463463374607431768211455");
Console.WriteLine("BigInt");
s.Start();
nad = 0;
nsu = 0;
for(ulong N = 0; N < 25000000; N++)
{
c = a * b;
while(c < soll) { c += sub; nad++;}
while(c > soll) { c -= sub; nsu++;}
a = c >> 128;
b = c & zHoch128m1;
}
s.Stop();
Console.WriteLine($"add={nad} su={nsu} in {s.ElapsedMilliseconds / 1000.0:F4} s");
Console.WriteLine(c);
\sourceoff
\sourceon C#
using System;
using System.Buffers.Binary;
using System.Globalization;
using System.Numerics;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using System.Runtime.Intrinsics.X86;
using System.Runtime.Intrinsics;
using System.Diagnostics.CodeAnalysis;
namespace AK.MP.Performance;
[StructLayout(LayoutKind.Explicit)]
public readonly struct UInt256
{
[FieldOffset(0)]
public readonly ulong u0;
[FieldOffset(8)]
public readonly ulong u1;
[FieldOffset(16)]
public readonly ulong u2;
[FieldOffset(24)]
public readonly ulong u3;
public static readonly UInt256 Zero = new();
public static readonly UInt256 One = new(1ul);
public static readonly UInt256 UInt128MaxValue = new(ulong.MaxValue, ulong.MaxValue);
public UInt256(ulong u0 = 0, ulong u1 = 0, ulong u2 = 0, ulong u3 = 0)
{
this.u0 = u0;
this.u1 = u1;
this.u2 = u2;
this.u3 = u3;
}
public UInt256(in ReadOnlySpan bytes, bool isBigEndian = false) // unchecked
{
// this constructor will cause a memory violation, if BYTES does not contain at least 32 bytes !
if (isBigEndian)
{
u3 = BinaryPrimitives.ReadUInt64BigEndian(bytes.Slice(0, 8));
u2 = BinaryPrimitives.ReadUInt64BigEndian(bytes.Slice(8, 8));
u1 = BinaryPrimitives.ReadUInt64BigEndian(bytes.Slice(16, 8));
u0 = BinaryPrimitives.ReadUInt64BigEndian(bytes.Slice(24, 8));
}
else
{
u0 = BinaryPrimitives.ReadUInt64LittleEndian(bytes.Slice(0, 8));
u1 = BinaryPrimitives.ReadUInt64LittleEndian(bytes.Slice(8, 8));
u2 = BinaryPrimitives.ReadUInt64LittleEndian(bytes.Slice(16, 8));
u3 = BinaryPrimitives.ReadUInt64LittleEndian(bytes.Slice(24, 8));
}
}
public static UInt256 operator +(in UInt256 a, in UInt256 b) // unchecked
{
Add(in a, in b, out UInt256 res);
return res;
}
public static UInt256 operator -(in UInt256 a, in UInt256 b) // unchecked
{
Subtract(in a, in b, out UInt256 c);
return c;
}
public static UInt256 operator *(in UInt256 a, in UInt256 b)
{
Multiply(in a, in b, out UInt256 c);
return c;
}
public static void Multiply(in UInt256 a, in UInt256 b, out UInt256 res)
{
// multiplies to 256-bit integer by Karatsuba's algorithm
ref ulong x = ref Unsafe.As(ref Unsafe.AsRef(in a));
ref ulong y = ref Unsafe.As(ref Unsafe.AsRef(in b));
Multiply64(x, y, out ulong carry, out ulong r0);
MulAndAdd(carry, Unsafe.Add(ref x, 1), y, out carry, out ulong res1);
MulAndAdd(carry, Unsafe.Add(ref x, 2), y, out carry, out ulong res2);
ulong res3 = Unsafe.Add(ref x, 3) * y + carry;
MulAndAdd(res1, x, Unsafe.Add(ref y, 1), out carry, out ulong r1);
MulAndAddWithCarry(res2, Unsafe.Add(ref x, 1), Unsafe.Add(ref y, 1), carry, out carry, out res2);
res3 = res3 + Unsafe.Add(ref x, 2) * Unsafe.Add(ref y, 1) + carry;
MulAndAdd(res2, x, Unsafe.Add(ref y, 2), out carry, out ulong r2);
res3 = res3 + Unsafe.Add(ref x, 1) * Unsafe.Add(ref y, 2) + carry;
ulong r3 = res3 + x * Unsafe.Add(ref y, 3);
res = new UInt256(r0, r1, r2, r3);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static void Multiply64(ulong a, ulong b, out ulong high, out ulong low)
{
high = Math.BigMul(a, b, out low);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static void MulAndAddWithCarry(ulong z, ulong x, ulong y, ulong carry, out ulong high, out ulong low) // z + (x * y) + carry
{
Multiply64(x, y, out high, out low);
ulong c = 0ul;
AddWithCarry(low, carry, ref c, out low);
AddWithCarry(high, 0, ref c, out high);
c = 0;
AddWithCarry(low, z, ref c, out low);
AddWithCarry(high, 0, ref c, out high);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static void MulAndAdd(ulong z, ulong x, ulong y, out ulong high, out ulong low) // (high * 2^64 + low) = z + (x * y)
{
Multiply64(x, y, out high, out low);
ulong carry = 0ul;
AddWithCarry(low, z, ref carry, out low);
AddWithCarry(high, 0, ref carry, out high);
}
public static void Add(in UInt256 a, in UInt256 b, out UInt256 res)
{
ulong carry = 0ul;
AddWithCarry(a.u0, b.u0, ref carry, out ulong res1);
AddWithCarry(a.u1, b.u1, ref carry, out ulong res2);
AddWithCarry(a.u2, b.u2, ref carry, out ulong res3);
AddWithCarry(a.u3, b.u3, ref carry, out ulong res4);
res = new UInt256(res1, res2, res3, res4);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static void AddWithCarry(ulong x, ulong y, ref ulong carry, out ulong sum)
{
sum = x + y + carry;
carry = ((x & y) | ((x | y) & (~sum))) >> 63;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static void Subtract(in UInt256 a, in UInt256 b, out UInt256 res)
{
ulong borrow = 0ul;
SubtractWithBorrow(a.u0, b.u0, ref borrow, out ulong res0);
SubtractWithBorrow(a.u1, b.u1, ref borrow, out ulong res1);
SubtractWithBorrow(a.u2, b.u2, ref borrow, out ulong res2);
SubtractWithBorrow(a.u3, b.u3, ref borrow, out ulong res3);
res = new UInt256(res0, res1, res2, res3);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static void SubtractWithBorrow(ulong a, ulong b, ref ulong borrow, out ulong res)
{
res = a - b - borrow;
borrow = (((~a) & b) | (~(a ^ b)) & res) >> 63;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static UInt256 operator &(in UInt256 a, in UInt256 b)
{
And(a, b, out UInt256 res);
return res;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void And(in UInt256 a, in UInt256 b, out UInt256 res)
{
res = new UInt256(a.u0 & b.u0, a.u1 & b.u1, a.u2 & b.u2, a.u3 & b.u3);
}
// offensichtliche Funktionen, "<=", casten in BigInteger, string operationen etc ...
// und alles andere was ein Typ eben so braucht
static ReadOnlySpan Lookup => // ...
}
\sourceoff
\showoff
*) und ich fand es ein wenig "unfair" die Implementierung eines "Nicht-Muttersprachlers" in den Vergleich einzubeziehen...
**) im Wesentlichen meine Ehefrau und Tester tactac
***) der offenbar einen Taschenrechner genutzt hat... \(\endgroup\)
|
Profil
|
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 2158
| Beitrag No.55, vom Themenstarter, eingetragen 2023-09-07
|
Oh, das freut mich -> mir geht es ja nicht anders :-)
Aber so lernt man noch was dabei.
80% der Computer-Sprachen verwenden meist vorhandene Bibliotheken, die aus der C-Welt kommen. Genau deshalb hatte ich eigentlich mit Regel f) auch das "Schummeln" ausklammern wollen (da stellen sich Sprachen als schnell dar, aber die eigentliche Berechnung wird ausgelagert).
So könnte man die GMP.DLL auch in EXCELs VBA Sprache einbinden und diesen langsamen Interpreter als "schnell hinstellen"...
Könnt Ihr etwas mehr zu Euren verbalen Formulierungen
"Verbesserter Code (ohne Hardware-Beschleunigung)" sagen?
Es gibt ja bei unveränderter Hardware immer mehrere Wege:
a) mathematische Zusammenfassung/Abkürzung: die wollte ich ja mit Regel e) ausklammern. Nur im letzten STEP darf mathematisch optimiert werden: Regel g)
b) Multitasking -> das kommt erst später, wenn man alle Sprachen mit 1 Thread verglichen hat (Regel h) )
c) erweiterte Befehlssätze (AVX, AVX512, ...) hohe Kunst, die nur wenige Sprachen anbieten!
d) verbesserte Compileroptionen & Zielplatformen
e) andere/neue Bib. verwenden (hatte ich ja schon Regel f) )
...
Beispiel zu a)
statt mit einer while-Schleife
\sourceon mathematica
fW[c_, soll_, sub_] := Module[{c0 = c}, While[c0 < soll, c0 += sub; nad++]; c0];
\sourceoff
kann man auch einfach die explizite Formel:
\sourceon mathematica
fE[c_, soll_, sub_] := ((nad = Max[0, Ceiling[(soll - c)/sub]]) - 1)*sub + c;
\sourceoff
verwenden... -> bei RUST könnte es durchaus der Fall sein, denn nicht nur der krasse Unterschied zw. Debug & release, sondern auch der extreme Unterschied des Re-ASM-Codes macht mich stutzig.
(vielleicht sollten wir die while Schleife komplizierter machen, um noch so intelligente Compiler zur while-Schleife zu zwingen; z.B. Pseudozufallsgenerator mit einbauen...)
Hier geht es aber nicht um maximale Optimierung des kompletten Programmes, sondern um Vergleich von mul256 und add256/sub256.
Oder mit den Worten aus Beitrag 3:
"Natürlich kommen nur "gültige Programme" zur Wertung".
(und außer einen Zahlenwert & verbale Formulierungen habe ich nichts in der Hand; falsche Zeitberechnungen können auch noch hinzu kommen)
Hardware-Beschleunigung kenne ich nur GPU (CUDA, die dann 1024 Kerne nutzt)
oder Coprozessor. Bin gespannt...
Bei tactac glaube ich aber nicht so recht an diese Wege 😄
Bin gespannt...
Grüße
|
Profil
|
AnnaKath
Senior
Dabei seit: 18.12.2006
Mitteilungen: 3858
Wohnort: hier und dort (s. Beruf)
| Beitrag No.56, eingetragen 2023-09-07
|
Huhu,
grundsätzlich haben wir natürlich ausgenutzt, dass die fraglichen Zahlen sich als nicht vorzeichenbehaftete 256-bit-Daten darstellen lassen. Ansonsten:
\quoteon(2023-09-07 22:46 - hyperG in Beitrag No. 55)
a) mathematische Zusammenfassung/Abkürzung: die wollte ich ja mit Regel e) ausklammern. Nur im letzten STEP darf mathematisch optimiert werden: Regel g)
b) Multitasking -> das kommt erst später, wenn man alle Sprachen mit 1 Thread verglichen hat (Regel h) )
c) erweiterte Befehlssätze (AVX, AVX512, ...) hohe Kunst, die nur wenige Sprachen anbieten!
d) verbesserte Compileroptionen & Zielplatformen
e) andere/neue Bib. verwenden (hatte ich ja schon Regel f) )
\quoteoff
a) ja, wir nutzen das effizientere DIVMOD, statt des Shifts und des AND (s. Code);
b) haben wir natürlich nicht genutzt;
c) Genau das ist mit Hardware-Beschleunigung gemeint. C# bietet in der Standard-Bibliothek im namespace "System.Runtime.Instrinsic" eben solche Unterstützung an. Wir haben für Intel-Prozessoren AVX2 und für (meinen) Apple-Chip ADVSIMD genutzt (aber alles im Rahmen der Standard-Lib);
d) Nein, wir haben das Programm nur ohne zusätzliche Debug-Informationen ("dotnet build -c Release") in die CIL übersetzen lassen;
e) haben wir - wie gesagt - nicht getan.
lg, AK
|
Profil
|
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 2158
| Beitrag No.57, vom Themenstarter, eingetragen 2023-09-08
|
Hallo AnnaKath,
wie zu erwarten war Dein >> und & statt / und % natürlich schneller: 15.6 s statt 19.965 s.
Ich habe mir sogar NET 7 installiert, aber es ist erst ab VC 2022 kompatibel (ich habe aber nur 2017).
Ich konnte aber die neuen DLLs per Verweise einbinden
System.Runtime.Intrinsics.X86
und
using System.Buffers.Binary;
somit ohne Fehler.
auch die Korrektur zu Stopwatch s = new Stopwatch(); war kein Problem.
ABER:
trotz dieser Einbindung habe ich keine einzige der 2 "DivMod128" (ARM habe ich natürlich komplett ausgeklammert) gefunden.
Bei namespace AK.MP.Performance (wo übrigens die Klammern { } fehlten)
ist auch keine definiert?
Mich interessiert natürlich der AVX-Teil am meisten, ABER bisher fehlt mir der komplette Ast
"UInt256x86" !
Könntest Du mir mal die Langform aufschreiben, als wenn kein einziges
USING im Kopf vorhanden wäre?
(die Langform von BigInteger wäre z.B. System.Numerics.BigInteger )
vielleicht werden dann Ast & dazugehörige Funktionen gefunden...
Grüße
|
Profil
|
AnnaKath
Senior
Dabei seit: 18.12.2006
Mitteilungen: 3858
Wohnort: hier und dort (s. Beruf)
| Beitrag No.58, eingetragen 2023-09-08
|
\(\begingroup\)\(\newcommand{\C}{\mathbb{C}}
\newcommand{\E}{\mathbb{E}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\i}{\mathrm{i}}
\newcommand{\d}{\mathrm{d}} \)
Huhu hyperG,
ich kann gerne einen Extrakt meines Codes (s.u.) aufführen, der den Avx-Teil enthält und auch ansonsten in sich lauffähig ist (es ist nur ein Auszug, weil die Typen natürlich noch viel mehr können - sie implementieren beispielsweise zahlreiche Interfaces etc. - , aber es kaum Sinn macht, 4000 Zeilen Code hier zu posten).
Ich werde aber keine veraltete Sprachversion künstlich einbauen... Also etwa namespaces mit curly braces versehen oder `Stopwatch s = new();` ersetzen... Man muss also schon die aktuelle Sprachversion verwenden, um den Code auszuführen ;)
Online beispielsweise unter Sharplab, das auch erlaubt, die Zwischenschritte der Kompilierung (lowered C#, IL, ASM) in Maschinencode nachzuvollziehen.
Ein kleines Rahmenprogramm:
\showon
\sourceon C#
global using System;
global using System.Numerics;
using System.Diagnostics;
using System.Runtime.Intrinsics.X86;
using AK.MP.Performance;
bool flag = GC.TryStartNoGCRegion(1024);
var (nad, nsu) = (0ul, 0ul);
var a = BigInteger.Parse("170141183460469231731687303715884105757");
var b = BigInteger.Parse("170141183460469231731687303715884105703");
var c = BigInteger.Parse("9");
var soll = BigInteger.Pow(BigInteger.Parse("2"), 255);
var sub = (BigInteger.Pow(BigInteger.Parse("10"), 77) - BigInteger.One) / c;
Stopwatch s = new();
if(Avx2.IsSupported)
{
// optimized code & using hardware acceleration (Intel x86)
var (a1, b1, c1) = ((UInt256x86)a, (UInt256x86)b, (UInt256x86)c);
var (soll1, sub1) = ((UInt256x86)soll, (UInt256x86)sub);
Console.WriteLine("Avx2");
s.Start();
nad = 0; nsu = 0;
for(ulong N = 0; N < 25000000; N++)
{
c1 = a1 * b1;
while(c1 < soll1) { c1 += sub1; nad++; }
while(c1 > soll1) { c1 -= sub1; nsu++; }
UInt256x86.DivMod128(in c1, out a1, out b1);
}
s.Stop();
Console.WriteLine($"add={nad} su={nsu} in {s.ElapsedMilliseconds / 1000.0:F4} s");
Console.WriteLine($"{c1}\n");
}
// MP original code
var zHoch128m1 = BigInteger.Parse("340282366920938463463374607431768211455");
Console.WriteLine("BigInt");
s.Start();
nad = 0;
nsu = 0;
for(ulong N = 0; N < 25000000; N++)
{
c = a * b;
while(c < soll) { c += sub; nad++;}
while(c > soll) { c -= sub; nsu++;}
a = c >> 128;
b = c & zHoch128m1;
}
s.Stop();
Console.WriteLine($"add={nad} su={nsu} in {s.ElapsedMilliseconds / 1000.0:F4} s");
Console.WriteLine(c);
if(!flag) GC.EndNoGCRegion();
\sourceoff
\showoff
Der 256bit-Typ, der nicht hardwarebeschleunigt ist:
\showon
\sourceon C#
// UInt256.cs
using System.Buffers.Binary;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using System.Runtime.Intrinsics.X86;
using System.Runtime.Intrinsics;
namespace AK.MP.Performance;
[StructLayout(LayoutKind.Explicit)]
public readonly struct UInt256
{
[FieldOffset(0)]
public readonly ulong u0;
[FieldOffset(8)]
public readonly ulong u1;
[FieldOffset(16)]
public readonly ulong u2;
[FieldOffset(24)]
public readonly ulong u3;
public static readonly UInt256 Zero = new UInt256();
public static readonly UInt256 UInt128MaxValue = new(ulong.MaxValue, ulong.MaxValue);
public UInt256(ulong u0 = 0, ulong u1 = 0, ulong u2 = 0, ulong u3 = 0)
{
this.u0 = u0;
this.u1 = u1;
this.u2 = u2;
this.u3 = u3;
}
public UInt256(in ReadOnlySpan bytes, bool isBigEndian = false) // unchecked
{
// this constructor will cause a memory violation, if BYTES does not contain at least 32 bytes !
if (isBigEndian)
{
u3 = BinaryPrimitives.ReadUInt64BigEndian(bytes.Slice(0, 8));
u2 = BinaryPrimitives.ReadUInt64BigEndian(bytes.Slice(8, 8));
u1 = BinaryPrimitives.ReadUInt64BigEndian(bytes.Slice(16, 8));
u0 = BinaryPrimitives.ReadUInt64BigEndian(bytes.Slice(24, 8));
}
else
{
u0 = BinaryPrimitives.ReadUInt64LittleEndian(bytes.Slice(0, 8));
u1 = BinaryPrimitives.ReadUInt64LittleEndian(bytes.Slice(8, 8));
u2 = BinaryPrimitives.ReadUInt64LittleEndian(bytes.Slice(16, 8));
u3 = BinaryPrimitives.ReadUInt64LittleEndian(bytes.Slice(24, 8));
}
}
public static UInt256 operator +(in UInt256 a, in UInt256 b) // unchecked
{
Add(in a, in b, out UInt256 res);
return res;
}
public static UInt256 operator -(in UInt256 a, in UInt256 b) // unchecked
{
Subtract(in a, in b, out UInt256 c);
return c;
}
public static UInt256 operator *(in UInt256 a, in UInt256 b)
{
Multiply(in a, in b, out UInt256 c);
return c;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void Multiply(in UInt256 a, in UInt256 b, out UInt256 res)
{
// multiplies to 256-bit integer by Karatsuba's algorithm
ref ulong x = ref Unsafe.As(ref Unsafe.AsRef(in a));
ref ulong y = ref Unsafe.As(ref Unsafe.AsRef(in b));
Multiply64(x, y, out ulong carry, out ulong r0);
MulAndAdd(carry, Unsafe.Add(ref x, 1), y, out carry, out ulong res1);
MulAndAdd(carry, Unsafe.Add(ref x, 2), y, out carry, out ulong res2);
ulong res3 = Unsafe.Add(ref x, 3) * y + carry;
MulAndAdd(res1, x, Unsafe.Add(ref y, 1), out carry, out ulong r1);
MulAndAddWithCarry(res2, Unsafe.Add(ref x, 1), Unsafe.Add(ref y, 1), carry, out carry, out res2);
res3 = res3 + Unsafe.Add(ref x, 2) * Unsafe.Add(ref y, 1) + carry;
MulAndAdd(res2, x, Unsafe.Add(ref y, 2), out carry, out ulong r2);
res3 = res3 + Unsafe.Add(ref x, 1) * Unsafe.Add(ref y, 2) + carry;
ulong r3 = res3 + x * Unsafe.Add(ref y, 3);
res = new UInt256(r0, r1, r2, r3);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static void Multiply64(ulong a, ulong b, out ulong high, out ulong low)
{
high = Math.BigMul(a, b, out low);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static void MulAndAddWithCarry(ulong z, ulong x, ulong y, ulong carry, out ulong high, out ulong low) // z + (x * y) + carry
{
Multiply64(x, y, out high, out low);
ulong c = 0ul;
AddWithCarry(low, carry, ref c, out low);
AddWithCarry(high, 0, ref c, out high);
c = 0;
AddWithCarry(low, z, ref c, out low);
AddWithCarry(high, 0, ref c, out high);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static void MulAndAdd(ulong z, ulong x, ulong y, out ulong high, out ulong low) // (high * 2^64 + low) = z + (x * y)
{
Multiply64(x, y, out high, out low);
ulong carry = 0ul;
AddWithCarry(low, z, ref carry, out low);
AddWithCarry(high, 0, ref carry, out high);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void Add(in UInt256 a, in UInt256 b, out UInt256 res)
{
ulong carry = 0ul;
AddWithCarry(a.u0, b.u0, ref carry, out ulong res1);
AddWithCarry(a.u1, b.u1, ref carry, out ulong res2);
AddWithCarry(a.u2, b.u2, ref carry, out ulong res3);
AddWithCarry(a.u3, b.u3, ref carry, out ulong res4);
res = new UInt256(res1, res2, res3, res4);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static void AddWithCarry(ulong x, ulong y, ref ulong carry, out ulong sum)
{
sum = x + y + carry;
carry = ((x & y) | ((x | y) & (~sum))) >> 63;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static void Subtract(in UInt256 a, in UInt256 b, out UInt256 res)
{
ulong borrow = 0ul;
SubtractWithBorrow(a.u0, b.u0, ref borrow, out ulong res0);
SubtractWithBorrow(a.u1, b.u1, ref borrow, out ulong res1);
SubtractWithBorrow(a.u2, b.u2, ref borrow, out ulong res2);
SubtractWithBorrow(a.u3, b.u3, ref borrow, out ulong res3);
res = new UInt256(res0, res1, res2, res3);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static void SubtractWithBorrow(ulong a, ulong b, ref ulong borrow, out ulong res)
{
res = a - b - borrow;
borrow = (((~a) & b) | (~(a ^ b)) & res) >> 63;
}
public static UInt256 operator &(in UInt256 a, in UInt256 b)
{
And(a, b, out UInt256 res);
return res;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void And(in UInt256 a, in UInt256 b, out UInt256 res)
{
res = new UInt256(a.u0 & b.u0, a.u1 & b.u1, a.u2 & b.u2, a.u3 & b.u3);
}
public static explicit operator UInt256(in BigInteger value)
{
byte[] bytes32 = value.ToBytes32(true);
return new UInt256(bytes32, true);
}
public static explicit operator BigInteger(in UInt256 value)
{
ReadOnlySpan bytes = MemoryMarshal.CreateReadOnlySpan(ref Unsafe.As(ref Unsafe.AsRef(in value)), 32);
return new BigInteger(bytes, true);
}
public static bool operator <(in UInt256 a, in UInt256 b) => LessThan(in a, in b);
public static bool operator <=(in UInt256 a, in UInt256 b) => !LessThan(in b, in a);
public static bool operator >(in UInt256 a, in UInt256 b) => LessThan(in b, in a);
public static bool operator >=(in UInt256 a, in UInt256 b) => !LessThan(in a, in b);
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static bool LessThan(in UInt256 a, in UInt256 b)
{
if (a.u3 != b.u3) return a.u3 < b.u3;
if (a.u2 != b.u2) return a.u2 < b.u2;
if (a.u1 != b.u1) return a.u1 < b.u1;
return a.u0 < b.u0;
}
public static void DivMod128(in UInt256 value, out UInt256 result, out UInt256 remainder)
{
result = new(value.u2, value.u3);
remainder = value & UInt128MaxValue;
}
public override string ToString() => ((BigInteger)this).ToString();
public string ToString(string format) => ((BigInteger)this).ToString(format);
public static UInt256 Parse(string value) => !TryParse(value, out UInt256 i) ? throw new FormatException() : i;
public static bool TryParse(in ReadOnlySpan value, out UInt256 result)
{
Span fixedHexValue = stackalloc char[value.Length];
value.CopyTo(fixedHexValue);
if (BigInteger.TryParse(fixedHexValue, out BigInteger a))
{
result = (UInt256)a;
return true;
}
result = Zero;
return false;
}
static ReadOnlySpan Lookup => new byte[] {
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 };
}
\sourceoff
\showoff
Hier nun der Typ mit Avx2-Beschleunigung
\showon
\sourceon C#
// UInt256x86.cs
using System.Buffers.Binary;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using System.Runtime.Intrinsics.X86;
using System.Runtime.Intrinsics;
namespace AK.MP.Performance;
[StructLayout(LayoutKind.Explicit)]
public readonly struct UInt256x86
{
[FieldOffset(0)]
public readonly ulong u0;
[FieldOffset(8)]
public readonly ulong u1;
[FieldOffset(16)]
public readonly ulong u2;
[FieldOffset(24)]
public readonly ulong u3;
public static readonly UInt256x86 Zero = new();
public static readonly UInt256x86 UInt128MaxValue = new(ulong.MaxValue, ulong.MaxValue);
public UInt256x86(ulong u0 = 0, ulong u1 = 0, ulong u2 = 0, ulong u3 = 0)
{
Unsafe.SkipInit(out this.u0);
Unsafe.SkipInit(out this.u1);
Unsafe.SkipInit(out this.u2);
Unsafe.SkipInit(out this.u3);
Unsafe.As>(ref this.u0) = Vector256.Create(u0, u1, u2, u3);
}
public UInt256x86(in ReadOnlySpan bytes, bool isBigEndian = false) // unchecked
{
// this constructor will cause a memory violation, if BYTES does not contain at least 32 bytes !
if (isBigEndian)
{
u3 = BinaryPrimitives.ReadUInt64BigEndian(bytes.Slice(0, 8));
u2 = BinaryPrimitives.ReadUInt64BigEndian(bytes.Slice(8, 8));
u1 = BinaryPrimitives.ReadUInt64BigEndian(bytes.Slice(16, 8));
u0 = BinaryPrimitives.ReadUInt64BigEndian(bytes.Slice(24, 8));
}
else
{
Unsafe.SkipInit(out this.u0);
Unsafe.SkipInit(out this.u1);
Unsafe.SkipInit(out this.u2);
Unsafe.SkipInit(out this.u3);
Unsafe.As>(ref this.u0) = Vector256.Create(bytes);
}
}
public static UInt256x86 operator +(in UInt256x86 a, in UInt256x86 b) // unchecked
{
Add(in a, in b, out UInt256x86 res);
return res;
}
public static UInt256x86 operator -(in UInt256x86 a, in UInt256x86 b) // unchecked
{
Subtract(in a, in b, out UInt256x86 c);
return c;
}
public static UInt256x86 operator *(in UInt256x86 a, in UInt256x86 b) // unchecked
{
Multiply(in a, in b, out UInt256x86 c);
return c;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void Multiply(in UInt256x86 a, in UInt256x86 b, out UInt256x86 res)
{
ref ulong x = ref Unsafe.As(ref Unsafe.AsRef(in a));
ref ulong y = ref Unsafe.As(ref Unsafe.AsRef(in b));
Multiply64(x, y, out ulong carry, out ulong r0);
MulAndAdd(carry, Unsafe.Add(ref x, 1), y, out carry, out ulong res1);
MulAndAdd(carry, Unsafe.Add(ref x, 2), y, out carry, out ulong res2);
ulong res3 = Unsafe.Add(ref x, 3) * y + carry;
MulAndAdd(res1, x, Unsafe.Add(ref y, 1), out carry, out ulong r1);
MulAndAddWithCarry(res2, Unsafe.Add(ref x, 1), Unsafe.Add(ref y, 1), carry, out carry, out res2);
res3 = res3 + Unsafe.Add(ref x, 2) * Unsafe.Add(ref y, 1) + carry;
MulAndAdd(res2, x, Unsafe.Add(ref y, 2), out carry, out ulong r2);
res3 = res3 + Unsafe.Add(ref x, 1) * Unsafe.Add(ref y, 2) + carry;
ulong r3 = res3 + x * Unsafe.Add(ref y, 3);
res = new UInt256x86(r0, r1, r2, r3);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static void Multiply64(ulong a, ulong b, out ulong high, out ulong low)
{
high = Math.BigMul(a, b, out low);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static void MulAndAddWithCarry(ulong z, ulong x, ulong y, ulong carry, out ulong high, out ulong low) // z + (x * y) + carry
{
Multiply64(x, y, out high, out low);
ulong c = 0ul;
AddWithCarry(low, carry, ref c, out low);
AddWithCarry(high, 0, ref c, out high);
c = 0;
AddWithCarry(low, z, ref c, out low);
AddWithCarry(high, 0, ref c, out high);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static void MulAndAdd(ulong z, ulong x, ulong y, out ulong high, out ulong low) // (high * 2^64 + low) = z + (x * y)
{
Multiply64(x, y, out high, out low);
ulong carry = 0ul;
AddWithCarry(low, z, ref carry, out low);
AddWithCarry(high, 0, ref carry, out high);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void Add(in UInt256x86 a, in UInt256x86 b, out UInt256x86 res)
{
var av = Unsafe.As>(ref Unsafe.AsRef(in a));
var bv = Unsafe.As>(ref Unsafe.AsRef(in b));
var result = Avx2.Add(av, bv);
var both = Avx2.And(av, bv);
var either = Avx2.Or(av, bv);
var high = Avx2.AndNot(result, either);
var vcarry = Avx2.Or(both, high);
var carry = Avx.MoveMask(Unsafe.As, Vector256>(ref vcarry));
var vcascade = Avx2.CompareEqual(result, Vector256.AllBitsSet);
var cascade = Avx.MoveMask(Unsafe.As, Vector256>(ref vcascade));
carry = cascade + 2 * carry;
cascade ^= carry;
cascade &= 0x0f;
var cascaded = Unsafe.Add(ref Unsafe.As>(ref MemoryMarshal.GetReference(Lookup)), cascade);
Unsafe.SkipInit(out res);
Unsafe.As>(ref res) = Avx2.Add(result, cascaded);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static void AddWithCarry(ulong x, ulong y, ref ulong carry, out ulong sum)
{
sum = x + y + carry;
carry = ((x & y) | ((x | y) & (~sum))) >> 63;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static void Subtract(in UInt256x86 a, in UInt256x86 b, out UInt256x86 res)
{
var x = Unsafe.As>(ref Unsafe.AsRef(in a));
var y = Unsafe.As>(ref Unsafe.AsRef(in b));
var result = Avx2.Subtract(x, y);
var rs = Avx2.Xor(result, Vector256.Create(0x8000000000000000));
var xs = Avx2.Xor(x, Vector256.Create(0x8000000000000000));
var bor = Avx2.CompareGreaterThan(
Unsafe.As, Vector256>(ref rs),
Unsafe.As, Vector256>(ref xs));
var borrow = Avx.MoveMask(Unsafe.As, Vector256>(ref bor));
var vcascade = Avx2.CompareEqual(result, Vector256.Zero);
var cascade = Avx.MoveMask(Unsafe.As, Vector256>(ref vcascade));
borrow = cascade + 2 * borrow;
cascade ^= borrow;
cascade &= 0x0f;
var cascaded = Unsafe.Add(ref Unsafe.As>(ref MemoryMarshal.GetReference(Lookup)), cascade);
Unsafe.SkipInit(out res);
Unsafe.As>(ref res) = Avx2.Subtract(result, cascaded);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static void SubtractWithBorrow(ulong a, ulong b, ref ulong borrow, out ulong res)
{
res = a - b - borrow;
borrow = (((~a) & b) | (~(a ^ b)) & res) >> 63;
}
public static UInt256x86 operator &(in UInt256x86 a, in UInt256x86 b)
{
And(a, b, out UInt256x86 res);
return res;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void And(in UInt256x86 a, in UInt256x86 b, out UInt256x86 res)
{
var veca = Unsafe.As>(ref Unsafe.AsRef(in a));
var vecb = Unsafe.As>(ref Unsafe.AsRef(in b));
Unsafe.SkipInit(out res);
Unsafe.As>(ref res) = Avx2.And(veca, vecb);
}
public static explicit operator UInt256x86(in BigInteger value)
{
byte[] bytes32 = value.ToBytes32(true);
return new UInt256x86(bytes32, true);
}
public static explicit operator BigInteger(in UInt256x86 value)
{
ReadOnlySpan bytes = MemoryMarshal.CreateReadOnlySpan(ref Unsafe.As(ref Unsafe.AsRef(in value)), 32);
return new BigInteger(bytes, true);
}
public static bool operator <(in UInt256x86 a, in UInt256x86 b) => LessThan(in a, in b);
public static bool operator <=(in UInt256x86 a, in UInt256x86 b) => !LessThan(in b, in a);
public static bool operator >(in UInt256x86 a, in UInt256x86 b) => LessThan(in b, in a);
public static bool operator >=(in UInt256x86 a, in UInt256x86 b) => !LessThan(in a, in b);
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static bool LessThan(in UInt256x86 a, in UInt256x86 b)
{
if (a.u3 != b.u3) return a.u3 < b.u3;
if (a.u2 != b.u2) return a.u2 < b.u2;
if (a.u1 != b.u1) return a.u1 < b.u1;
return a.u0 < b.u0;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void DivMod128(in UInt256x86 value, out UInt256x86 result, out UInt256x86 remainder)
{
result = new(value.u2, value.u3);
remainder = value & UInt128MaxValue;
}
public override string ToString() => ((BigInteger)this).ToString();
public string ToString(string format) => ((BigInteger)this).ToString(format);
public static UInt256x86 Parse(string value) => !TryParse(value, out UInt256x86 i) ? throw new FormatException() : i;
public static bool TryParse(in ReadOnlySpan value, out UInt256x86 result)
{
Span fixedHexValue = stackalloc char[value.Length];
value.CopyTo(fixedHexValue);
if (BigInteger.TryParse(fixedHexValue, out BigInteger a))
{
result = (UInt256x86)a;
return true;
}
result = Zero;
return false;
}
static ReadOnlySpan Lookup => new byte[] {
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 };
}
\sourceoff
\showoff
Und hier noch ein paar convenience-Funktionen für BigIntegers:
\showon
\sourceon C#
// BigIntegerExtensions.cs
using System;
using System.Numerics;
namespace AK.MP.Performance;
static class BigIntegerExtensions
{
public static byte[] ToBytes32(this BigInteger value, bool isBigEndian)
{
byte[] bytes32 = new byte[32];
value.ToBytes32(bytes32.AsSpan(), isBigEndian);
return bytes32;
}
public static void ToBytes32(this BigInteger value, Span target, bool isBigEndian)
{
if (!isBigEndian)
throw new NotImplementedException();
if (target.Length != 32)
throw new ArgumentException($"Target length should be 32 and is {target.Length}", nameof(target));
ReadOnlySpan bytes = value.ToByteArray(true, true);
if (bytes.Length > 32)
bytes.Slice(bytes.Length - 32, bytes.Length).CopyTo(target);
else
bytes.CopyTo(target.Slice(32 - bytes.Length, bytes.Length));
}
}
\sourceoff
\showoff
lg, AK\(\endgroup\)
|
Profil
|
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 2158
| Beitrag No.59, vom Themenstarter, eingetragen 2023-09-16
|
So AnnaKath,
ich gebe es auf: dieses .NET 7 bekomme ich nicht zum Laufen.
Ich habe mir sogar die Mühe gemacht, die mich interessierenden Codeabschnitte für sharplab.io kompatibel zu machen, um wenigstens die JIT ASM Wandlung zu betrachten:
\showon
\sourceon c#
using System;
using System.Buffers.Binary;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using System.Runtime.Intrinsics.X86;
using System.Runtime.Intrinsics;
using System.Numerics;
using System.Linq;
[StructLayout(LayoutKind.Explicit)]
public struct UInt256x86
{
[FieldOffset(0)]
public ulong u0;
[FieldOffset(8)]
public ulong u1;
[FieldOffset(16)]
public ulong u2;
[FieldOffset(24)]
public ulong u3;
public static UInt256x86 Zero = new();
public static UInt256x86 UInt128MaxValue = new(ulong.MaxValue, ulong.MaxValue);
public UInt256x86(ulong u0 = 0, ulong u1 = 0, ulong u2 = 0, ulong u3 = 0)
{
Unsafe.SkipInit(out this.u0);
Unsafe.SkipInit(out this.u1);
Unsafe.SkipInit(out this.u2);
Unsafe.SkipInit(out this.u3);
Unsafe.As>(ref this.u0) = Vector256.Create(u0, u1, u2, u3);
}
public UInt256x86(in Span bytes, bool isBigEndian = false) // unchecked
{
// this constructor will cause a memory violation, if BYTES does not contain at least 32 bytes !
if (isBigEndian)
{
u3 = BinaryPrimitives.ReadUInt64BigEndian(bytes.Slice(0, 8));
u2 = BinaryPrimitives.ReadUInt64BigEndian(bytes.Slice(8, 8));
u1 = BinaryPrimitives.ReadUInt64BigEndian(bytes.Slice(16, 8));
u0 = BinaryPrimitives.ReadUInt64BigEndian(bytes.Slice(24, 8));
}
else
{
Unsafe.SkipInit(out this.u0);
Unsafe.SkipInit(out this.u1);
Unsafe.SkipInit(out this.u2);
Unsafe.SkipInit(out this.u3);
Unsafe.As>(ref this.u0) = Vector256.Create(bytes);
}
}
public static UInt256x86 operator +(in UInt256x86 a, in UInt256x86 b) // unchecked
{
Add(in a, in b, out UInt256x86 res);
return res;
}
public static UInt256x86 operator -(in UInt256x86 a, in UInt256x86 b) // unchecked
{
Subtract(in a, in b, out UInt256x86 c);
return c;
}
public static UInt256x86 operator *(in UInt256x86 a, in UInt256x86 b) // unchecked
{
Multiply(in a, in b, out UInt256x86 c);
return c;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void Multiply(in UInt256x86 a, in UInt256x86 b, out UInt256x86 res)
{
ref ulong x = ref Unsafe.As(ref Unsafe.AsRef(in a));
ref ulong y = ref Unsafe.As(ref Unsafe.AsRef(in b));
Multiply64(x, y, out ulong carry, out ulong r0);
MulAndAdd(carry, Unsafe.Add(ref x, 1), y, out carry, out ulong res1);
MulAndAdd(carry, Unsafe.Add(ref x, 2), y, out carry, out ulong res2);
ulong res3 = Unsafe.Add(ref x, 3) * y + carry;
MulAndAdd(res1, x, Unsafe.Add(ref y, 1), out carry, out ulong r1);
MulAndAddWithCarry(res2, Unsafe.Add(ref x, 1), Unsafe.Add(ref y, 1), carry, out carry, out res2);
res3 = res3 + Unsafe.Add(ref x, 2) * Unsafe.Add(ref y, 1) + carry;
MulAndAdd(res2, x, Unsafe.Add(ref y, 2), out carry, out ulong r2);
res3 = res3 + Unsafe.Add(ref x, 1) * Unsafe.Add(ref y, 2) + carry;
ulong r3 = res3 + x * Unsafe.Add(ref y, 3);
res = new UInt256x86(r0, r1, r2, r3);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static void Multiply64(ulong a, ulong b, out ulong high, out ulong low)
{
high = Math.BigMul(a, b, out low);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static void MulAndAddWithCarry(ulong z, ulong x, ulong y, ulong carry, out ulong high, out ulong low) // z + (x * y) + carry
{
Multiply64(x, y, out high, out low);
ulong c = 0ul;
AddWithCarry(low, carry, ref c, out low);
AddWithCarry(high, 0, ref c, out high);
c = 0;
AddWithCarry(low, z, ref c, out low);
AddWithCarry(high, 0, ref c, out high);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static void MulAndAdd(ulong z, ulong x, ulong y, out ulong high, out ulong low) // (high * 2^64 + low) = z + (x * y)
{
Multiply64(x, y, out high, out low);
ulong carry = 0ul;
AddWithCarry(low, z, ref carry, out low);
AddWithCarry(high, 0, ref carry, out high);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static void AddWithCarry(ulong x, ulong y, ref ulong carry, out ulong sum)
{
sum = x + y + carry;
carry = ((x & y) | ((x | y) & (~sum))) >> 63;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void Add(in UInt256x86 a, in UInt256x86 b, out UInt256x86 res)
{
var av = Unsafe.As>(ref Unsafe.AsRef(in a));
var bv = Unsafe.As>(ref Unsafe.AsRef(in b));
var result = Avx2.Add(av, bv);
var both = Avx2.And(av, bv);
var either = Avx2.Or(av, bv);
var high = Avx2.AndNot(result, either);
var vcarry = Avx2.Or(both, high);
var carry = Avx.MoveMask(Unsafe.As, Vector256>(ref vcarry));
var vcascade = Avx2.CompareEqual(result, Vector256.AllBitsSet);
var cascade = Avx.MoveMask(Unsafe.As, Vector256>(ref vcascade));
carry = cascade + 2 * carry;
cascade ^= carry;
cascade &= 0x0f;
//The name 'Lookup' does not exist in the current context
// var cascaded = Unsafe.Add(ref Unsafe.As>(ref Unsafe.AsRef( cascade)));
//(ref MemoryMarshal.GetReference(Lookup)), cascade);
Unsafe.SkipInit(out res);
Unsafe.As>(ref res) =result;// Avx2.Add(result, cascaded);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static void Subtract(in UInt256x86 a, in UInt256x86 b, out UInt256x86 res)
{
var x = Unsafe.As>(ref Unsafe.AsRef(in a));
var y = Unsafe.As>(ref Unsafe.AsRef(in b));
var result = Avx2.Subtract(x, y);
var rs = Avx2.Xor(result, Vector256.Create(0x8000000000000000));
var xs = Avx2.Xor(x, Vector256.Create(0x8000000000000000));
var bor = Avx2.CompareGreaterThan(
Unsafe.As, Vector256>(ref rs),
Unsafe.As, Vector256>(ref xs));
var borrow = Avx.MoveMask(Unsafe.As, Vector256>(ref bor));
var vcascade = Avx2.CompareEqual(result, Vector256.Zero);
var cascade = Avx.MoveMask(Unsafe.As, Vector256>(ref vcascade));
borrow = cascade + 2 * borrow;
cascade ^= borrow;
cascade &= 0x0f;
//var cascaded = Unsafe.Add(ref Unsafe.As>(ref MemoryMarshal.GetReference(Lookup)), cascade);
Unsafe.SkipInit(out res);
Unsafe.As>(ref res) = result;//Avx2.Subtract(result, cascaded);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static void SubtractWithBorrow(ulong a, ulong b, ref ulong borrow, out ulong res)
{
res = a - b - borrow;
borrow = (((~a) & b) | (~(a ^ b)) & res) >> 63;
}
public static UInt256x86 operator &(in UInt256x86 a, in UInt256x86 b)
{
And(a, b, out UInt256x86 res);
return res;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void And(in UInt256x86 a, in UInt256x86 b, out UInt256x86 res)
{
var veca = Unsafe.As>(ref Unsafe.AsRef(in a));
var vecb = Unsafe.As>(ref Unsafe.AsRef(in b));
Unsafe.SkipInit(out res);
Unsafe.As>(ref res) = Avx2.And(veca, vecb);
}
public static explicit operator UInt256x86(in BigInteger value)
{
byte[] bytes32 = value.ToByteArray();// value.ToBytes32(true);
// byte[] bytes32= new byte[32];
//Buffer.BlockCopy(value, 0, bytes32, 0, 32);//ToByteArray
return new UInt256x86(bytes32 , true);//bytes32
}
public static explicit operator BigInteger(in UInt256x86 value)
{
Span bytes = MemoryMarshal.CreateSpan(ref Unsafe.As(ref Unsafe.AsRef(in value)), 32);
return new BigInteger(bytes, true);
}
public static bool operator <(in UInt256x86 a, in UInt256x86 b) => LessThan(in a, in b);
public static bool operator <=(in UInt256x86 a, in UInt256x86 b) => !LessThan(in b, in a);
public static bool operator >(in UInt256x86 a, in UInt256x86 b) => LessThan(in b, in a);
public static bool operator >=(in UInt256x86 a, in UInt256x86 b) => !LessThan(in a, in b);
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static bool LessThan(in UInt256x86 a, in UInt256x86 b)
{
if (a.u3 != b.u3) return a.u3 < b.u3;
if (a.u2 != b.u2) return a.u2 < b.u2;
if (a.u1 != b.u1) return a.u1 < b.u1;
return a.u0 < b.u0;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void DivMod128(in UInt256x86 value, out UInt256x86 result, out UInt256x86 remainder)
{
result = new(value.u2, value.u3);
remainder = value & UInt128MaxValue;
}
public override string ToString() => ((BigInteger)this).ToString();
public string ToString(string format) => ((BigInteger)this).ToString(format);
}
\sourceoff
\showoff
aber nach Beseitigung aller Syntay-Fehler kamen interne Fehler auf dem Internet-Server:
\showon
System.NotSupportedException: Type UInt256x86 has a static constructor, which is not supported by SharpLab JIT decompiler.
at SharpLab.Server.Decompilation.JitAsmDecompiler.EnsureNoJitSideEffects(Assembly assembly) in D:\a\SharpLab\SharpLab\source\Server\Decompilation\JitAsmDecompiler.cs:line 76
at SharpLab.Server.Decompilation.JitAsmDecompiler.Decompile(CompilationStreamPair streams, TextWriter codeWriter, IWorkSession session) in D:\a\SharpLab\SharpLab\source\Server\Decompilation\JitAsmDecompiler.cs:line 57
at SharpLab.Server.MirrorSharp.SlowUpdate.WriteResult(IFastJsonWriter writer, Object result, IWorkSession session) in D:\a\SharpLab\SharpLab\source\Server\MirrorSharp\SlowUpdate.cs:line 175
at MirrorSharp.Internal.Handlers.SlowUpdateHandler.SendSlowUpdateAsync(IReadOnlyList`1 diagnostics, WorkSession session, Object extensionResult, ICommandResultSender sender, CancellationToken cancellationToken) in D:\a\SharpLab\SharpLab\source\#external\mirrorsharp\Common\Internal\Handlers\SlowUpdateHandler.cs:line 74
\showoff
(Lookup musste ich komplett ausklammern, da jegliche Versuche scheiterten)
Kannst Du mir nicht einfach die exe nur für den AVX2 Teil zukommen lassen?
(analog Laufzeit (tt) 10,82 s (x86-Optimierung)
Selbst wenn sie trotz Laufzeit NET 7.0 nicht laufen sollte (um objektiv Geschwindigkeiten zu vergleichen, denn Faktor 10 zw. Deiner & tt CPU ist schon enorm),
könnte ich sie mit Re-ASM untersuchen.
Grüße
|
Profil
|
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 2158
| Beitrag No.60, vom Themenstarter, eingetragen 2023-09-16
|
Mit der Analyse der schnellsten RUST.exe von schnitzel bin ich nun dank binaryninja tiefer eingedrungen:
- kein AVX2
- kein Multitasking
- keine mathematischen Tricks
Die super Zeit entstand durch maximale Optimierung des Maschinencodes,
was man auch schon am gewaltigen Unterschied zwischen Debug & Release sieht:
- in der Schleife keine Call & RET (keine Unterprozeduren!)
- kein PUSH & POP zum Sichern von Registern
- minimale MOV: Register einer 256er Variablen liegen verstreut unübersichtlich weit auseinander und werden erst kurz vor dem PRINT
(also nach der Zeitmessung) zusammengeholt!
- kaum Jump
Der Code der Hauptschleife ist also minimal klein & passt gut in den schnellen Cache der CPU!
Absolut unübersichtlich aber sehr CPU-Effizient.
Der eigentliche MUL-Teil unterscheidet sich kaum von meiner MUL-ASM,
aber ich muss ja 25 Mio. mal mit mehreren
MOV, JUMP, Call, PUSH, POP, RET, Register-Sortierungen von C++ nach ASM wechseln, was Zeit kostet.
Zwar konnte ich ADD_AVX minimal verbessern & mit "inline" die vielen Call, PUSH, POP , RET etwas verkleinern, aber nur kleine Verbesserung.
Nun noch was zu Abkürzungen & Tricks:
- Mathematische "Abkürzungen" (die ich ja ausgeschlossen hatte) bringen natürlich immer etwas. Allein das Weglassen von SUB & der letzten Add (durch optimierten While-Vergleich) verkürzt meine 0.914 s auf 0.63 s.
Bei Mathematica von 134.9 s nach 94 s.
Weitere Reduzierung der Add durch mehr If-Vorab-Fragen machten alles wieder langsamer (vermutlich ist mathematicas IF langsamer als das Add).
In c++ hatte ich noch keine Zeit für ADD-Reduktion.
- Multitasking: wegen der absichtlichen "seriellen Zerstückelung des letzten Schleifenergebnisses" lässt sich außen kein paralleles Abarbeiten ansetzen. Bei ADD habe ich testweise mal 2 Threads parallel arbeiten lassen: statt 0.6 s dann 48 s -> "Schuss nach hinten" weil das zigmalige Sammeln von Eingangsvariablen + Start von Threads, GetThread, Warten auf Fertig usw. mehr Zeit kostet, als ein paar AVX Befehle!
Die Mühe für eine weitere Ergebnistabelle "mit Abkürzungen & Tricks" (also auch ohne Zählung der Add & Sub) lasse ich mal aus Zeitgründen weg.
Grüße
|
Profil
|
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 2158
| Beitrag No.61, vom Themenstarter, eingetragen 2023-09-16
|
Beim Stöbern im Internet bin ich auf 2 interessante Mul1024 Bit
Algorithmen gestoßen (statt 78stellige dann 309stellige Zahlen).
Das wäre aber ein neuer Beitrag, da zu große Unterschiede...
|
Profil
|
AnnaKath
Senior
Dabei seit: 18.12.2006
Mitteilungen: 3858
Wohnort: hier und dort (s. Beruf)
| Beitrag No.62, eingetragen 2023-09-16
|
Huhu hyperG,
zwar verstehe ich nicht so genau, welchen Problemen Du begegnest, aber natürlich ist es kein Problem, hier zwei IL-kompilierte Versionen des Codes mit allen erforderlichen Bibliotheken zur Verfügung zu stellen:
win-x86 sowie osx-arm
lg, AK
|
Profil
|
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 2158
| Beitrag No.63, vom Themenstarter, eingetragen 2023-09-16
|
Dankeschön.
\sourceon Antwort Mp.Performance.exe
Avx2
add=83884810 su=25000000 in 3,3700 s
47306219819553867530681020915755484915944251665601642944764215683054098939729
BigInt
add=83884810 su=25000000 in 12,2140 s
47306219819553867530681020915755484915944251665601642944764215683054098939729
\sourceoff
BigInt mit Net7.0 ist also etwas schneller geworden.
Meine CPU liegt also zwischen Deiner & der von Tactac.
Werte in Tabelle nachgetragen.
ASM Analyse:
Mp.Performance.dll & Mp.Performance.exe:
AVX-Befehle : 0
AVX2-Befehle: 0
(In der DLL sieht es nach vielen normalen imul & mul aus.)
|
Profil
|
Delastelle
Senior
Dabei seit: 17.11.2006
Mitteilungen: 2512
 | Beitrag No.64, eingetragen 2023-09-17
|
Hallo hyperG!
\quoteon(2023-09-16 22:10 - hyperG in
|
Profil
|
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 2158
| Beitrag No.65, vom Themenstarter, eingetragen 2023-09-17
|
Profil
|
| hyperG hat die Antworten auf ihre/seine Frage gesehen. | | Seite 2 | Gehe zur Seite: 1 | 2 |
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die
Nutzungsbedingungen,
die Distanzierung,
die Datenschutzerklärung und das Impressum.
[Seitenanfang]
|
Home / Seite ohne Frame
2023-11-29 01:19 ?
Wie unterstütze ich den Matheplaneten mit Geld?
