Skip to content

Instantly share code, notes, and snippets.

@raggi
Created March 29, 2023 05:55
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save raggi/25035bf3fc5cd7c1a3b02dd3987a87fa to your computer and use it in GitHub Desktop.
Save raggi/25035bf3fc5cd7c1a3b02dd3987a87fa to your computer and use it in GitHub Desktop.
golang math/rand is large, exp/rand is much smaller
package howmuchrand
import (
"math/rand"
"sync"
"testing"
exprand "golang.org/x/exp/rand"
)
var (
seed uint64 = 8729831
numDraw = 100
numGouroutines = 5000
job = make(chan func(), 2<<20)
res = make(chan struct{}, 2<<20)
)
func init() {
for i := 0; i < numGouroutines; i++ {
go func() {
for {
f := <-job
f()
res <- struct{}{}
}
}()
}
}
var stdPool = sync.Pool{
New: func() interface{} {
return rand.New(rand.NewSource(int64(seed)))
},
}
var expPool = sync.Pool{
New: func() interface{} {
return exprand.New(exprand.NewSource(seed))
},
}
func BenchmarkStd(b *testing.B) {
b.ReportAllocs()
for i := 0; i < b.N; i++ {
job <- func() {
rand.Seed(int64(seed))
for i := 0; i < numDraw; i++ {
rand.Intn(100)
}
}
}
for i := 0; i < b.N; i++ {
<-res
}
}
func BenchmarkPCG(b *testing.B) {
b.ReportAllocs()
for i := 0; i < b.N; i++ {
job <- func() {
exprand.Seed(seed)
for i := 0; i < numDraw; i++ {
exprand.Intn(100)
}
}
}
for i := 0; i < b.N; i++ {
<-res
}
}
func BenchmarkStdPool(b *testing.B) {
b.ReportAllocs()
for i := 0; i < b.N; i++ {
job <- func() {
r := stdPool.Get().(*rand.Rand)
defer stdPool.Put(r)
r.Seed(int64(seed))
for i := 0; i < numDraw; i++ {
r.Intn(100)
}
}
}
for i := 0; i < b.N; i++ {
<-res
}
}
func BenchmarkPCGPool(b *testing.B) {
b.ReportAllocs()
for i := 0; i < b.N; i++ {
job <- func() {
r := expPool.Get().(*exprand.Rand)
defer expPool.Put(r)
r.Seed(seed)
for i := 0; i < numDraw; i++ {
r.Intn(100)
}
}
}
for i := 0; i < b.N; i++ {
<-res
}
}
func BenchmarkLocalStd(b *testing.B) {
b.ReportAllocs()
for i := 0; i < b.N; i++ {
job <- func() {
r := rand.New(rand.NewSource(int64(seed)))
for i := 0; i < numDraw; i++ {
r.Intn(100)
}
}
}
for i := 0; i < b.N; i++ {
<-res
}
}
func BenchmarkLocalPCG(b *testing.B) {
b.ReportAllocs()
for i := 0; i < b.N; i++ {
job <- func() {
r := exprand.New(exprand.NewSource(seed))
for i := 0; i < numDraw; i++ {
r.Intn(100)
}
}
}
for i := 0; i < b.N; i++ {
<-res
}
}
func BenchmarkStackRand(b *testing.B) {
b.ReportAllocs()
for i := 0; i < b.N; i++ {
job <- func() {
r := New()
r.Seed(seed)
for i := 0; i < numDraw; i++ {
r.Intn(100)
}
}
}
for i := 0; i < b.N; i++ {
<-res
}
}
// A Rand is a source of random numbers.
type Rand struct {
src exprand.PCGSource
}
// New returns a new Rand that uses random values from src
// to generate other random values.
func New() Rand {
var r Rand
r.Seed(1)
return r
}
// Seed uses the provided seed value to initialize the generator to a deterministic state.
// Seed should not be called concurrently with any other Rand method.
func (r *Rand) Seed(seed uint64) {
r.src.Seed(seed)
}
// Uint64 returns a pseudo-random 64-bit integer as a uint64.
func (r *Rand) Uint64() uint64 { return r.src.Uint64() }
const maxUint64 = (1 << 64) - 1
// Uint64n returns, as a uint64, a pseudo-random number in [0,n).
// It is guaranteed more uniform than taking a Source value mod n
// for any n that is not a power of 2.
func (r *Rand) Uint64n(n uint64) uint64 {
if n&(n-1) == 0 { // n is power of two, can mask
if n == 0 {
panic("invalid argument to Uint64n")
}
return r.Uint64() & (n - 1)
}
// If n does not divide v, to avoid bias we must not use
// a v that is within maxUint64%n of the top of the range.
v := r.Uint64()
if v > maxUint64-n { // Fast check.
ceiling := maxUint64 - maxUint64%n
for v >= ceiling {
v = r.Uint64()
}
}
return v % n
}
// Intn returns, as an int, a non-negative pseudo-random number in [0,n).
// It panics if n <= 0.
func (r *Rand) Intn(n int) int {
if n <= 0 {
panic("invalid argument to Intn")
}
// TODO: Avoid some 64-bit ops to make it more efficient on 32-bit machines.
return int(r.Uint64n(uint64(n)))
}
goos: linux
goarch: amd64
pkg: howmuchrand
cpu: AMD Ryzen 9 3950X 16-Core Processor
BenchmarkStd-32 109020 10439 ns/op 0 B/op 0 allocs/op
BenchmarkPCG-32 233880 5700 ns/op 0 B/op 0 allocs/op
BenchmarkStdPool-32 1862824 628.3 ns/op 0 B/op 0 allocs/op
BenchmarkPCGPool-32 2252481 549.7 ns/op 0 B/op 0 allocs/op
BenchmarkLocalStd-32 755256 1413 ns/op 5376 B/op 1 allocs/op
BenchmarkLocalPCG-32 2193565 540.6 ns/op 16 B/op 1 allocs/op
BenchmarkStackRand-32 2224692 529.0 ns/op 0 B/op 0 allocs/op
PASS
ok howmuchrand 11.324s
go test -bench . 113.72s user 14.73s system 1102% cpu 11.646 total 95 rss
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment