Last active
October 29, 2022 07:42
-
-
Save qdm12/75a1c5175d764f6a0f77a89521cf50c6 to your computer and use it in GitHub Desktop.
Fast thread-safe uniformly distributed numbers generation in Go
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package main | |
import ( | |
"crypto/rand" | |
"encoding/binary" | |
"fmt" | |
"hash/maphash" | |
mathrand "math/rand" | |
"runtime" | |
"sync" | |
"sync/atomic" | |
"testing" | |
) | |
func benchPerCoreConfigs(b *testing.B, f func(b *testing.B)) { | |
b.Helper() | |
coreConfigs := []int{1, 2, 4, 8, 12, 18, 24} | |
for _, n := range coreConfigs { | |
name := fmt.Sprintf("%d cores", n) | |
b.Run(name, func(b *testing.B) { | |
runtime.GOMAXPROCS(n) | |
f(b) | |
}) | |
} | |
} | |
func BenchmarkCryptoRandGenerator(b *testing.B) { | |
benchPerCoreConfigs(b, func(b *testing.B) { | |
b.RunParallel(func(b *testing.PB) { | |
for b.Next() { | |
buffer := make([]byte, 8) | |
_, _ = rand.Read(buffer) | |
outUint64 := binary.BigEndian.Uint64(buffer) | |
out := int(outUint64) | |
if out < 0 { | |
out = -out | |
} | |
_ = out % 100 | |
} | |
}) | |
}) | |
} | |
func BenchmarkMathRandGenerator(b *testing.B) { | |
benchPerCoreConfigs(b, func(b *testing.B) { | |
b.RunParallel(func(b *testing.PB) { | |
for b.Next() { | |
_ = mathrand.Intn(100) | |
} | |
}) | |
}) | |
} | |
func BenchmarkMutexGenerator(b *testing.B) { | |
benchPerCoreConfigs(b, func(b *testing.B) { | |
makeSeed := func() (seed uint64) { | |
b := make([]byte, 8) | |
_, _ = rand.Read(b) | |
return binary.BigEndian.Uint64(b) | |
} | |
generator := struct { | |
n uint64 | |
sync.Mutex | |
}{ | |
n: makeSeed(), | |
} | |
b.RunParallel(func(b *testing.PB) { | |
for b.Next() { | |
generator.Lock() | |
// xorshift | |
generator.n ^= generator.n << 13 | |
generator.n ^= generator.n >> 7 | |
generator.n ^= generator.n << 17 | |
outUint64 := generator.n | |
generator.Unlock() | |
out := int(outUint64) | |
if out < 0 { | |
out = -out | |
} | |
_ = out % 100 | |
} | |
}) | |
}) | |
} | |
func BenchmarkMutexCounter(b *testing.B) { | |
benchPerCoreConfigs(b, func(b *testing.B) { | |
var generator struct { | |
counter uint64 | |
sync.Mutex | |
} | |
b.RunParallel(func(b *testing.PB) { | |
for b.Next() { | |
generator.Lock() | |
outUint64 := generator.counter | |
generator.counter++ | |
generator.Unlock() | |
out := int(outUint64) | |
if out < 0 { | |
out = -out | |
} | |
_ = out % 100 | |
} | |
}) | |
}) | |
} | |
func BenchmarkAtomicCounter(b *testing.B) { | |
benchPerCoreConfigs(b, func(b *testing.B) { | |
counterPtr := new(uint64) | |
b.RunParallel(func(b *testing.PB) { | |
for b.Next() { | |
_ = int(atomic.AddUint64(counterPtr, 1)) % 100 | |
} | |
}) | |
}) | |
} | |
func BenchmarkSyncPool(b *testing.B) { | |
benchPerCoreConfigs(b, func(b *testing.B) { | |
type generator struct { | |
n uint64 | |
} | |
makeSeed := func() (seed uint64) { | |
b := make([]byte, 8) | |
_, _ = rand.Read(b) | |
return binary.BigEndian.Uint64(b) | |
} | |
pool := &sync.Pool{ | |
New: func() interface{} { | |
return &generator{ | |
n: makeSeed(), | |
} | |
}, | |
} | |
b.RunParallel(func(b *testing.PB) { | |
for b.Next() { | |
generator := pool.Get().(*generator) | |
// xorshift | |
generator.n ^= generator.n << 13 | |
generator.n ^= generator.n >> 7 | |
generator.n ^= generator.n << 17 | |
outUint64 := generator.n | |
pool.Put(generator) | |
out := int(outUint64) | |
if out < 0 { | |
out = -out | |
} | |
_ = out % 100 | |
} | |
}) | |
}) | |
} | |
func BenchmarkMaphash(b *testing.B) { | |
benchPerCoreConfigs(b, func(b *testing.B) { | |
b.RunParallel(func(b *testing.PB) { | |
for b.Next() { | |
outUint64 := new(maphash.Hash).Sum64() | |
out := int(outUint64) | |
if out < 0 { | |
out = -out | |
} | |
_ = out % 100 | |
} | |
}) | |
}) | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package main | |
import ( | |
"crypto/rand" | |
"encoding/binary" | |
"hash/maphash" | |
mathrand "math/rand" | |
"sync" | |
"sync/atomic" | |
"testing" | |
) | |
func isUniformlyDistributed(t *testing.T, f func(n int) int) { | |
t.Helper() | |
const iterations = 100000 | |
const maxValue = 30 | |
numberToCount := make(map[int]int, maxValue) | |
for i := 0; i < iterations; i++ { | |
out := f(maxValue) | |
numberToCount[out]++ | |
} | |
targetGenerationsPerNumber := iterations / maxValue | |
const maxPercentDivergence = 0.07 | |
for number := 0; number < maxValue; number++ { | |
count := numberToCount[number] | |
diff := targetGenerationsPerNumber - count | |
if diff < 0 { | |
diff = -diff | |
} | |
divergence := float64(diff) / float64(targetGenerationsPerNumber) | |
if divergence > maxPercentDivergence { | |
t.Errorf("Number %d was generated %d times, with a %.2f%% divergence from the target %d", | |
number, count, 100*divergence, targetGenerationsPerNumber) | |
} | |
} | |
} | |
func Test_CryptoRandGenerator(t *testing.T) { | |
f := func(n int) int { | |
buffer := make([]byte, 8) | |
_, _ = rand.Read(buffer) | |
outUint64 := binary.BigEndian.Uint64(buffer) | |
out := int(outUint64) | |
if out < 0 { | |
out = -out | |
} | |
return out % n | |
} | |
isUniformlyDistributed(t, f) | |
} | |
func Test_MathRandGenerator(t *testing.T) { | |
isUniformlyDistributed(t, mathrand.Intn) | |
} | |
func Test_MutexGenerator(t *testing.T) { | |
makeSeed := func() (seed uint64) { | |
b := make([]byte, 8) | |
_, _ = rand.Read(b) | |
return binary.BigEndian.Uint64(b) | |
} | |
generator := struct { | |
n uint64 | |
sync.Mutex | |
}{ | |
n: makeSeed(), | |
} | |
f := func(n int) int { | |
generator.Lock() | |
// xorshift | |
generator.n ^= generator.n << 13 | |
generator.n ^= generator.n >> 7 | |
generator.n ^= generator.n << 17 | |
outUint64 := generator.n | |
generator.Unlock() | |
out := int(outUint64) | |
if out < 0 { | |
out = -out | |
} | |
return out % n | |
} | |
isUniformlyDistributed(t, f) | |
} | |
func Test_MutexCounter(t *testing.T) { | |
var generator struct { | |
counter uint64 | |
sync.Mutex | |
} | |
f := func(n int) int { | |
generator.Lock() | |
outUint64 := generator.counter | |
generator.counter++ | |
generator.Unlock() | |
out := int(outUint64) | |
if out < 0 { | |
out = -out | |
} | |
return out % n | |
} | |
isUniformlyDistributed(t, f) | |
} | |
func Test_AtomicCounter(t *testing.T) { | |
counterPtr := new(int64) | |
f := func(n int) int { | |
return int(atomic.AddInt64(counterPtr, 1)) % n | |
} | |
isUniformlyDistributed(t, f) | |
} | |
func Test_SyncPool(t *testing.T) { | |
type generator struct { | |
n uint64 | |
} | |
makeSeed := func() (seed uint64) { | |
b := make([]byte, 8) | |
_, _ = rand.Read(b) | |
return binary.BigEndian.Uint64(b) | |
} | |
pool := &sync.Pool{ | |
New: func() interface{} { | |
return &generator{ | |
n: makeSeed(), | |
} | |
}, | |
} | |
f := func(n int) int { | |
generator := pool.Get().(*generator) | |
// xorshift | |
generator.n ^= generator.n << 13 | |
generator.n ^= generator.n >> 7 | |
generator.n ^= generator.n << 17 | |
outUint64 := generator.n | |
pool.Put(generator) | |
out := int(outUint64) | |
if out < 0 { | |
out = -out | |
} | |
return out % n | |
} | |
isUniformlyDistributed(t, f) | |
} | |
func Test_Maphash(t *testing.T) { | |
f := func(n int) int { | |
outUint64 := new(maphash.Hash).Sum64() | |
out := int(outUint64) | |
if out < 0 { | |
out = -out | |
} | |
return out % n | |
} | |
isUniformlyDistributed(t, f) | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment