ゴルーチン内の乱数生成を高速に行う

TL;DR

math/rand パッケージのトップレベル関数（rand.Float64 関数など）では内部でロックを取得するので、複数のゴルーチンで乱数を生成するとパフォーマンスがでない
複数のゴルーチンで乱数を生成するときは、Rand 構造体のインスタンスを使って乱数を生成するとよい

経緯

Goの勉強のためにGoRayTracerというレイトレーサーを作っています。こんな画像を生成するプログラムです。

f:id:LocaQ:20190321172935p:plain

一通り動くところまでできましたが、この画像（640 x 480）を生成するのに1163秒（約20分）かかります。

同じ画像を生成できるFRayTracerを前に作っていたのですが、それと比べて2倍以上の時間がかかっていました。特別な最適化をしていない.NETのプログラムより遅いのはおかしいと思い、プロファイラーを使って原因を調べてみました。

プロファイリング&分析

プロファイリングにはpkg/profileというライブラリを使いました。

main関数の先頭に以下のようなコードを追加すると、関数ごとのCPU使用時間を取得できます。

func main() {
    defer profile.Start(profile.ProfilePath(".")).Stop()

     ...
}

ビルドし、プログラムを起動して実行が終わると cpu.pprof というファイルができるので、Goの pprof というツールを使って結果を分析します。

>go tool pprof .go\bin\go_raytracer.exe cpu.pprof
File: go_raytracer.exe
Type: cpu
Time: Mar 10, 2019 at 8:49pm (JST)
Duration: 4.63mins, Total samples = 29.65mins (640.59%)
Entering interactive mode (type "help" for commands, "o" for options)
(pprof)

top -cumと入力して時間のかかる関数を表示します。 -cumは「対象の関数だけではなく、その関数の呼び出し先まで含めた実行時間を表す"cumulative weight"の値でソートする」オプションのようです。（flat は「対象の関数の実行時間から、呼び出し先の関数の実行時間を引いた時間」を表すようです。）

(pprof) top -cum
Showing nodes accounting for 14.34mins, 48.37% of 29.65mins total
Dropped 352 nodes (cum <= 0.15mins)
Showing top 10 nodes out of 73
      flat  flat%   sum%        cum   cum%
         0     0%     0%  26.07mins 87.93%  github.com/locatw/go-ray-tracer/rendering.(*RayTracer).renderPixelRoutine
  0.06mins  0.21%  0.21%  26.07mins 87.93%  github.com/locatw/go-ray-tracer/rendering.(*RayTracer).renderPixel
  0.36mins  1.21%  1.42%  25.22mins 85.08%  github.com/locatw/go-ray-tracer/rendering.(*RayTracer).traceRay
  0.04mins  0.13%  1.55%  15.99mins 53.94%  math/rand.Float64
  0.05mins  0.16%  1.70%  15.95mins 53.82%  math/rand.(*Rand).Float64
  0.03mins 0.087%  1.79%  15.91mins 53.66%  math/rand.(*Rand).Int63
  0.65mins  2.21%  3.99%  15.88mins 53.57%  math/rand.(*lockedSource).Int63
  0.30mins  1.01%  5.01%  15.77mins 53.20%  github.com/locatw/go-ray-tracer/element.CreateDiffuseRay
  2.29mins  7.73% 12.74%  13.09mins 44.17%  sync.(*Mutex).Lock
 10.56mins 35.63% 48.37%  10.56mins 35.63%  runtime.procyield
(pprof)

最初の3つはアプリのメソッドですが、その次に math/rand の関数とメソッドが4つ並んでいます。また、9番目に sync.(*Mutex).Lock があります。この内、アプリで直接使っているのは math/rand.Float64 だけです。この乱数生成だけで実行時間の50%以上を使っていることが読み取れます。

また、sync.(*Mutex).Lock と math/rand.(*lockedSource).Int63 があるので、「math/rand.Float64 の内部でロックを取得していてそれに時間がかかっている」と予想して調べたところ、以下の記事を見つけました。

golangのrandパッケージのlockについて - DevDevデブ!!

この記事（とさらに参照先の記事）を読むと、やはり math/rand.Float64 などのトップレベル関数は内部でロックを取っているようです。ロックを取っているのでパフォーマンスが出ない代わりに、ゴルーチンセーフになっているとのこと。また、ゴルーチン毎に Rand 構造体のインスタンスを作成し、それを使って乱数を生成するとパフォーマンスがよくなると書かれています。

Rand 構造体を使って乱数を生成する

GoRayTracerではCPUコア数と同じだけのゴルーチンを生成し、内部で rand.Float64 関数を使っています。なのでゴルーチンで実行する処理の内部で Rand 構造体のインスタンスを生成し、それを使って乱数を生成するようにしてみました。

optimize performance · locatw/GoRayTracer@c67a081

// ゴルーチン毎に生成
random := rand.New(rand.NewSource(time.Now().UnixNano()))

// ゴルーチンで実行される関数のなかで、Rand構造体のメソッドを使って乱数を生成する。
value := random.Float64()

変更前と変更後でベンチマークを取った結果が以下です。

コード	実行時間（秒）
改善前	1163
改善後	283

（CPU：Intel Core i7-8700, 画像の解像度：640 x 480）

変更前と比べて約4倍速くなりました。

プロファイリングでは乱数生成に全体の50%を使っていたので速くなるのは高々2倍くらいかと思いましたが、予想以上に速くなりました。おそらく、プロファイラーは全ての処理の実行時間を計測しているわけではなくサンプリングしているため、実際の割合と差があり、結果予想以上に速くなったのだと思います。

Goの math/rand パッケージのソースコードを確認する

速くなって目的は達成しましたが、最後にGoのソースコードを確認してみます。確認するコードはGo1.12の math/rand パッケージです。

go/rand.go at release-branch.go1.12 · golang/go

以下、ここからコードを引用します。全てのコードは引用しませんので詳しくは直接コードを見てください。

Float64、globalRand、lockedSource

まずは今回使っている、トップレベルの Float64 関数のコードを見てみます。

var globalRand = New(&lockedSource{src: NewSource(1).(Source64)})

// Float64 returns, as a float64, a pseudo-random number in [0.0,1.0)
// from the default Source.
func Float64() float64 { return globalRand.Float64() }

トップレベルの Float64 関数は globalRand の Float64 メソッドを呼び出す実装になっています。また、globalRand はパッケージプライベートな *Rand 型の変数です。

NewSource 関数は Source 型のオブジェクトを生成する関数、New 関数は新しい Rand 構造体のオブジェクトを生成する関数でした。

次にここまで出てきた Source 、Rand、lockedSource、Source と関連する Source64 の定義を見てみます。

// A Source represents a source of uniformly-distributed
// pseudo-random int64 values in the range [0, 1<<63).
type Source interface {
    Int63() int64
    Seed(seed int64)
}

// A Source64 is a Source that can also generate
// uniformly-distributed pseudo-random uint64 values in
// the range [0, 1<<64) directly.
// If a Rand r's underlying Source s implements Source64,
// then r.Uint64 returns the result of one call to s.Uint64
// instead of making two calls to s.Int63.
type Source64 interface {
    Source
    Uint64() uint64
}

// A Rand is a source of random numbers.
type Rand struct {
    src Source
    s64 Source64 // non-nil if src is source64

    // readVal contains remainder of 63-bit integer used for bytes
    // generation during most recent Read call.
    // It is saved so next Read call can start where the previous
    // one finished.
    readVal int64
    // readPos indicates the number of low-order bytes of readVal
    // that are still valid.
    readPos int8
}

type lockedSource struct {
    lk  sync.Mutex
    src Source64
}

Source は乱数生成源を表すインターフェースのようで、このインターフェースに定義されている Int63 メソッドで実際に乱数を生成するようです。また、Source64 は Source に Uint64 メソッドを追加したインターフェースのようです。

Rand 構造体は Source、Source64 型のインスタンスを保持する構造体、lockedSource はミューテックスと Source64 型のオブジェクトを持つ構造体です。また、ここには載せていませんが、Rand 構造体と lockedSource 構造体は Source、Source64 インターフェースに定義されているメソッドを定義していますので、Source、Source64 インターフェースを実装した構造体になっています。

lockedSource を使った乱数生成

globalRand を生成するコードと、アプリでゴルーチン毎に生成した Rand 構造体のインスタンスを生成するコードを比べてみます。

globalRand を生成するコード

var globalRand = New(&lockedSource{src: NewSource(1).(Source64)})

GoRayTracerでゴルーチン毎に生成するコード

random := rand.New(rand.NewSource(time.Now().UnixNano()))

違いは New 関数に渡す引数で、globalRand は lockedSource を渡していますが、アプリでは通常の NewSource 関数で生成した乱数生成源を渡しています。

さて、トップレベルの Float64 関数

func Float64() float64 { return globalRand.Float64() }

ですが、globalRand の Float64 メソッドを呼び出しています。

これは内部を辿っていくと Rand 構造体が持つ乱数生成源 src の Int63 メソッドを呼び出すのですが、globalRand の場合は lockedSource の Int63 メソッドになります。そのコードは以下のようになっています。

func (r *lockedSource) Int63() (n int64) {
    r.lk.Lock()
    n = r.src.Int63()
    r.lk.Unlock()
    return
}

確かに乱数生成時にロックを使っていました。