Skip to content

Commit 833833c

Browse files
daosvikDag Arne Osvik
daosvik
and
Dag Arne Osvik
authored
testing: benchmark updates (#93)
* Use least non negative residue of the addend for each modulus when testing AddMod * Use powers of a residue for MulMod testing * Remove not yet defined cacheStats Co-authored-by: Dag Arne Osvik <[email protected]>
1 parent 4420c2b commit 833833c

File tree

1 file changed

+83
-95
lines changed

1 file changed

+83
-95
lines changed

‎benchmarks_test.go‎

Lines changed: 83 additions & 95 deletions
Original file line numberDiff line numberDiff line change
@@ -16,16 +16,22 @@ var (
1616
int32Samples [numSamples]Int
1717
int32SamplesLt [numSamples]Int
1818
int64Samples [numSamples]Int
19+
int64SamplesLt [numSamples]Int
1920
int128Samples [numSamples]Int
21+
int128SamplesLt [numSamples]Int
2022
int192Samples [numSamples]Int
23+
int192SamplesLt [numSamples]Int
2124
int256Samples [numSamples]Int
2225
int256SamplesLt [numSamples]Int // int256SamplesLt[i] <= int256Samples[i]
2326

2427
big32Samples [numSamples]big.Int
2528
big32SamplesLt [numSamples]big.Int
2629
big64Samples [numSamples]big.Int
30+
big64SamplesLt [numSamples]big.Int
2731
big128Samples [numSamples]big.Int
32+
big128SamplesLt [numSamples]big.Int
2833
big192Samples [numSamples]big.Int
34+
big192SamplesLt [numSamples]big.Int
2935
big256Samples [numSamples]big.Int
3036
big256SamplesLt [numSamples]big.Int // big256SamplesLt[i] <= big256Samples[i]
3137

@@ -55,21 +61,56 @@ func initSamples() bool {
5561
int32SamplesLt[i].SetUint64(uint64(x32l))
5662
big32SamplesLt[i] = *int32SamplesLt[i].ToBig()
5763

58-
int64Samples[i] = newRandInt(1)
64+
l := newRandInt(1)
65+
g := newRandInt(1)
66+
if g.Lt(&l) {
67+
g,l = l,g
68+
}
69+
if g[0] == 0 {
70+
g[0]++
71+
}
72+
int64Samples[i] = g
5973
big64Samples[i] = *int64Samples[i].ToBig()
74+
int64SamplesLt[i] = l
75+
big64SamplesLt[i] = *int64SamplesLt[i].ToBig()
6076

61-
int128Samples[i] = newRandInt(2)
77+
l = newRandInt(2)
78+
g = newRandInt(2)
79+
if g.Lt(&l) {
80+
g,l = l,g
81+
}
82+
if g[1] == 0 {
83+
g[1]++
84+
}
85+
int128Samples[i] = g
6286
big128Samples[i] = *int128Samples[i].ToBig()
87+
int128SamplesLt[i] = l
88+
big128SamplesLt[i] = *int128SamplesLt[i].ToBig()
6389

64-
int192Samples[i] = newRandInt(3)
90+
l = newRandInt(3)
91+
g = newRandInt(3)
92+
if g.Lt(&l) {
93+
g,l = l,g
94+
}
95+
if g[2] == 0 {
96+
g[2]++
97+
}
98+
int192Samples[i] = g
6599
big192Samples[i] = *int192Samples[i].ToBig()
100+
int192SamplesLt[i] = l
101+
big192SamplesLt[i] = *int192SamplesLt[i].ToBig()
66102

67-
int256Samples[i] = newRandInt(4)
68-
int256SamplesLt[i] = newRandInt(4)
69-
if int256Samples[i].Lt(&int256SamplesLt[i]) {
70-
int256Samples[i], int256SamplesLt[i] = int256SamplesLt[i], int256Samples[i]
103+
l = newRandInt(4)
104+
g = newRandInt(4)
105+
if g.Lt(&l) {
106+
g,l = l,g
71107
}
108+
if g[3] == 0 {
109+
g[3]++
110+
}
111+
int256Samples[i] = g
72112
big256Samples[i] = *int256Samples[i].ToBig()
113+
int256SamplesLt[i] = l
73114
big256SamplesLt[i] = *int256SamplesLt[i].ToBig()
74115
}
75116

@@ -626,106 +667,53 @@ func BenchmarkAddMod(b *testing.B) {
626667
}
627668
}
628669

629-
// Compute least non negative residue of the addend for each modulus
630-
631-
{
632-
var (
633-
I Int
634-
B big.Int
635-
636-
residue32Int [len(int32Samples)]Int
637-
residue32Big [len(int32Samples)]big.Int
638-
residue64Int [len(int64Samples)]Int
639-
residue64Big [len(int64Samples)]big.Int
640-
residue128Int [len(int128Samples)]Int
641-
residue128Big [len(int128Samples)]big.Int
642-
residue192Int [len(int192Samples)]Int
643-
residue192Big [len(int192Samples)]big.Int
644-
residue256Int [len(int256Samples)]Int
645-
residue256Big [len(int256Samples)]big.Int
646-
)
647-
648-
for i := 0; i < len(int32Samples); i++ {
649-
residue32Int[i] = *(I.Mod(&int32Samples[i], &int32SamplesLt[i]))
650-
}
651-
for i := 0; i < len(big32Samples); i++ {
652-
residue32Big[i] = *(B.Mod(&big32Samples[i], &big32SamplesLt[i]))
653-
}
654-
655-
for i := 0; i < len(int64Samples); i++ {
656-
residue64Int[i] = *(I.Mod(&int64Samples[i], &int64Samples[i]))
657-
}
658-
for i := 0; i < len(big64Samples); i++ {
659-
residue64Big[i] = *(B.Mod(&big64Samples[i], &big64Samples[i]))
660-
}
661-
662-
for i := 0; i < len(int128Samples); i++ {
663-
residue128Int[i] = *(I.Mod(&int128Samples[i], &int128Samples[i]))
664-
}
665-
for i := 0; i < len(big128Samples); i++ {
666-
residue128Big[i] = *(B.Mod(&big128Samples[i], &big128Samples[i]))
667-
}
668-
669-
for i := 0; i < len(int192Samples); i++ {
670-
residue192Int[i] = *(I.Mod(&int192Samples[i], &int192Samples[i]))
671-
}
672-
for i := 0; i < len(big192Samples); i++ {
673-
residue192Big[i] = *(B.Mod(&big192Samples[i], &big192Samples[i]))
674-
}
675-
676-
for i := 0; i < len(int256Samples); i++ {
677-
residue256Int[i] = *(I.Mod(&int256Samples[i], &int256SamplesLt[i]))
678-
}
679-
for i := 0; i < len(big256Samples); i++ {
680-
residue256Big[i] = *(B.Mod(&big256Samples[i], &big256SamplesLt[i]))
681-
}
682-
683-
b.Run("small/uint256", func(b *testing.B) { benchmarkAddModUint256(b, &residue32Int, &int32SamplesLt) })
684-
b.Run("small/big", func(b *testing.B) { benchmarkAddModBig(b, &residue32Big, &big32SamplesLt) })
685-
b.Run("mod64/uint256", func(b *testing.B) { benchmarkAddModUint256(b, &residue256Int, &int64Samples) })
686-
b.Run("mod64/big", func(b *testing.B) { benchmarkAddModBig(b, &residue256Big, &big64Samples) })
687-
b.Run("mod128/uint256", func(b *testing.B) { benchmarkAddModUint256(b, &residue256Int, &int128Samples) })
688-
b.Run("mod128/big", func(b *testing.B) { benchmarkAddModBig(b, &residue256Big, &big128Samples) })
689-
b.Run("mod192/uint256", func(b *testing.B) { benchmarkAddModUint256(b, &residue256Int, &int192Samples) })
690-
b.Run("mod192/big", func(b *testing.B) { benchmarkAddModBig(b, &residue256Big, &big192Samples) })
691-
b.Run("mod256/uint256", func(b *testing.B) { benchmarkAddModUint256(b, &residue256Int, &int256SamplesLt) })
692-
b.Run("mod256/big", func(b *testing.B) { benchmarkAddModBig(b, &residue256Big, &big256SamplesLt) })
693-
}
670+
b.Run("small/uint256", func(b *testing.B) { benchmarkAddModUint256 (b, &int32SamplesLt, &int32Samples) })
671+
b.Run("small/big", func(b *testing.B) { benchmarkAddModBig (b, &big32SamplesLt, &big32Samples) })
672+
b.Run("mod64/uint256", func(b *testing.B) { benchmarkAddModUint256 (b, &int64SamplesLt, &int64Samples) })
673+
b.Run("mod64/big", func(b *testing.B) { benchmarkAddModBig (b, &big64SamplesLt, &big64Samples) })
674+
b.Run("mod128/uint256", func(b *testing.B) { benchmarkAddModUint256 (b, &int128SamplesLt, &int128Samples) })
675+
b.Run("mod128/big", func(b *testing.B) { benchmarkAddModBig (b, &big128SamplesLt, &big128Samples) })
676+
b.Run("mod192/uint256", func(b *testing.B) { benchmarkAddModUint256 (b, &int192SamplesLt, &int192Samples) })
677+
b.Run("mod192/big", func(b *testing.B) { benchmarkAddModBig (b, &big192SamplesLt, &big192Samples) })
678+
b.Run("mod256/uint256", func(b *testing.B) { benchmarkAddModUint256 (b, &int256SamplesLt, &int256Samples) })
679+
b.Run("mod256/big", func(b *testing.B) { benchmarkAddModBig (b, &big256SamplesLt, &big256Samples) })
694680
}
695681

696682
func BenchmarkMulMod(b *testing.B) {
697683
benchmarkMulModUint256 := func(b *testing.B, factorsSamples, modSamples *[numSamples]Int) {
698-
var sink, x Int
699-
for j := 0; j < b.N; j += numSamples {
700-
for i := 0; i < numSamples; i++ {
701-
y := factorsSamples[i]
702-
sink.MulMod(&x, &y, &modSamples[i])
703-
x = y
684+
iter := (b.N + numSamples - 1) / numSamples
685+
686+
for j := 0; j < numSamples; j++ {
687+
x := factorsSamples[j]
688+
689+
for i := 0; i < iter; i++ {
690+
x.MulMod(&x, &factorsSamples[j], &modSamples[j])
704691
}
705692
}
706693
}
707694
benchmarkMulModBig := func(b *testing.B, factorsSamples, modSamples *[numSamples]big.Int) {
708-
var sink, x big.Int
709-
for j := 0; j < b.N; j += numSamples {
710-
for i := 0; i < numSamples; i++ {
711-
y := factorsSamples[i]
712-
sink.Mul(&x, &y)
713-
sink.Mod(&sink, &modSamples[i])
714-
x = y
695+
iter := (b.N + numSamples - 1) / numSamples
696+
697+
for j := 0; j < numSamples; j++ {
698+
x := factorsSamples[j]
699+
700+
for i := 0; i < iter; i++ {
701+
x.Mul(&x, &factorsSamples[j])
702+
x.Mod(&x, &modSamples[j])
715703
}
716704
}
717705
}
718706

719-
b.Run("small/uint256", func(b *testing.B) { benchmarkMulModUint256(b, &int32Samples, &int32SamplesLt) })
720-
b.Run("small/big", func(b *testing.B) { benchmarkMulModBig(b, &big32Samples, &big32SamplesLt) })
721-
b.Run("mod64/uint256", func(b *testing.B) { benchmarkMulModUint256(b, &int256Samples, &int64Samples) })
722-
b.Run("mod64/big", func(b *testing.B) { benchmarkMulModBig(b, &big256Samples, &big64Samples) })
723-
b.Run("mod128/uint256", func(b *testing.B) { benchmarkMulModUint256(b, &int256Samples, &int128Samples) })
724-
b.Run("mod128/big", func(b *testing.B) { benchmarkMulModBig(b, &big256Samples, &big128Samples) })
725-
b.Run("mod192/uint256", func(b *testing.B) { benchmarkMulModUint256(b, &int256Samples, &int192Samples) })
726-
b.Run("mod192/big", func(b *testing.B) { benchmarkMulModBig(b, &big256Samples, &big192Samples) })
727-
b.Run("mod256/uint256", func(b *testing.B) { benchmarkMulModUint256(b, &int256Samples, &int256SamplesLt) })
728-
b.Run("mod256/big", func(b *testing.B) { benchmarkMulModBig(b, &big256Samples, &big256SamplesLt) })
707+
b.Run("small/uint256", func(b *testing.B) { benchmarkMulModUint256 (b, &int32SamplesLt, &int32Samples) })
708+
b.Run("small/big", func(b *testing.B) { benchmarkMulModBig (b, &big32SamplesLt, &big32Samples) })
709+
b.Run("mod64/uint256", func(b *testing.B) { benchmarkMulModUint256 (b, &int64SamplesLt, &int64Samples) })
710+
b.Run("mod64/big", func(b *testing.B) { benchmarkMulModBig (b, &big64SamplesLt, &big64Samples) })
711+
b.Run("mod128/uint256", func(b *testing.B) { benchmarkMulModUint256 (b, &int128SamplesLt, &int128Samples) })
712+
b.Run("mod128/big", func(b *testing.B) { benchmarkMulModBig (b, &big128SamplesLt, &big128Samples) })
713+
b.Run("mod192/uint256", func(b *testing.B) { benchmarkMulModUint256 (b, &int192SamplesLt, &int192Samples) })
714+
b.Run("mod192/big", func(b *testing.B) { benchmarkMulModBig (b, &big192SamplesLt, &big192Samples) })
715+
b.Run("mod256/uint256", func(b *testing.B) { benchmarkMulModUint256 (b, &int256SamplesLt, &int256Samples) })
716+
b.Run("mod256/big", func(b *testing.B) { benchmarkMulModBig (b, &big256SamplesLt, &big256Samples) })
729717
}
730718

731719
func benchmark_SdivLarge_Big(bench *testing.B) {

0 commit comments

Comments
 (0)