Fast thread-safe uniformly distributed numbers generation in Go

bench_test.go

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
			}
		})
	})
}

test_test.go

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)
}