monolithic kernel

goroutine safe で高速な疑似乱数生成器

golang 標準の math/rand は goroutine safe ではあるものの、単にロックを取っているだけで非常に遅い。そこで、高速なものを書いてみた。

ベンチマークの結果は以下の通り。単一の goroutine だと遅いが、64並列に設定した場合には逆転している。

goos: darwin
goarch: amd64
pkg: github.com/mono0x/prand
BenchmarkMathRandInt63-8                100000000               22.2 ns/op       361.02 MB/s
BenchmarkPrandInt63-8                   20000000                94.9 ns/op        84.27 MB/s
BenchmarkMathRandInt63Parallel-8        20000000               103 ns/op          77.62 MB/s
BenchmarkPrandInt63Parallel-8           50000000                24.7 ns/op       323.91 MB/s
BenchmarkMathRandUint64-8               100000000               22.8 ns/op       350.91 MB/s
BenchmarkPrandUint64-8                  20000000               105 ns/op          75.77 MB/s
BenchmarkMathRandUint64Parallel-8       20000000               104 ns/op          76.75 MB/s
BenchmarkPrandUint64Parallel-8          50000000                26.6 ns/op       301.27 MB/s
PASS
ok      github.com/mono0x/prand 15.787s

仕組みとしては乱数生成機を複数作って sync.Pool で使いまわしている。

func NewSource(newSource func() rand.Source) rand.Source {
  return &source{
    pool: sync.Pool{
      New: func() interface{} { return newSource() },
    },
  }
}


func (s *source) Int63() int64 {
  source := s.pool.Get().(rand.Source)
  defer s.pool.Put(source)
  return source.Int63()
}

というわけでロックを取るのと等価ではない。が、とにかく乱数がほしいのであればこれで問題ないはず。

標準では math/rand の乱数生成機を内部的に利用しているが、rand.Source interface を実装しているものであれば他の乱数生成機に差し替えることが可能。math/rand は速度的にも品質的にも優れているとはいえないので、適当に差し替えるのが無難。

sync.Pool は手軽にそこそこ高速化できてよいが、ほんとは thread local storage 的なものがほしい。golang の runtime の実装では、スレッドを表現する M 構造体の中に乱数のステートを保持しており、これを使って高速に乱数生成する runtime.fastrand という関数が存在する。こういうアプローチの実装がユーザでもできたらうれしい。ただ、golang の世界では基本的にスレッドを意識しないようになっているし、thread local storage を操作する部分では goroutine のプリエンプションを明示的に無効化する必要があったりして難しいので、シンプルな golang の方向性とは合わないのかもしれない。

Related articles