-
-
Save rafpro/b15326ba042d8af2ac3bc5370fa118f8 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