LoginSignup
3

More than 5 years have passed since last update.

Goroutine と math/rand とベンチマークの罠

Last updated at Posted at 2016-04-24

やりたかった事

なんとなくrandで大量に乱数を使った計算をなるべく高速にしたくなった

実験前に考察

マルチコアCPUなんだし、Goroutine使って同時に生成/消費していけば速いはず

コード

b_test.go
package main
import (
    "testing"
    "math/rand"
    "sync"
)
const (
    // 1op=乱数100個じゃ少ない気がしたので
    // 1op=UNITS回、乱数100個の平均をとる
    UNITS = 10
    thread = 8
)

// 適当に100個の乱数の平均を取る
func average_100() int{
    sum := 0
    for it := 0; it < 100; it++ {
        sum += rand.Intn(100)
    }
    return sum / 100.0
}


func Standard(){
    for ix := 0; ix < MAX_UNITS; ix++ {
        average_100()
    }
}

func BenchmarkStandard(b *testing.B){
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        Standard()
    }
}

func mt_calc(max int, chn chan bool){
    for index := 0; index < max; index++ {
        Standard()
    }
    chn <- true
}
func BenchmarkMThread(b *testing.B){
    div := b.N / thread
    mod := b.N % thread
    chn := make(chan bool,thread)
    b.ResetTimer()
    for core := 0; core < thread; core++ {
        mt_calc(div, chn)
    }
    for ix := 0; ix < mod; ix++ {
        Standard()
    }
    for core := 0; core < thread; core++ {
        <- chn
    }
}

結果

BenchmarkStandard-8                50000             27041 ns/op
BenchmarkMThread-8                 50000             27101 ns/op

えっと……速くなってないorz

原因

よく考えれば分かる事ですが、
このベンチの処理はmath/rand.Intnがほとんどです。
そして、rand.IntnはMutexでロックされたGoroutineセーフな乱数生成器です。
そのため、ほとんどずっとロックされてしまって実質1スレッドと差がなくなってしまっていました。

改良

bench2_test.go
package main
import (
    "testing"
    "math/rand"
    "sync"
)
const (
    UNITS = 10
    thread = 8
)

func average_100() int{
    sum := 0
    for it := 0; it < 100; it++ {
        sum += rand.Intn(100)
    }
    return sum / 100.0
}
func rndave_100(rnd *rand.Rand) int{
    sum := 0
    for it := 0; it < 100; it++ {
        sum += rnd.Intn(100)
    }
    return sum / 100.0
}

func NewRand(rnd *rand.Rand){
    for ix := 0; ix < UNITS; ix++ {
        rndave_100(rnd)
    }
}

func Standard(){
    for ix := 0; ix < UNITS; ix++ {
        average_100()
    }
}

func BenchmarkStandard(b *testing.B){
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        Standard()
    }
}

func mt_calc(max int, chn chan bool){
    for index := 0; index < max; index++ {
        Standard()
    }
    chn <- true
}
func BenchmarkMThread(b *testing.B){
    div := b.N / thread
    mod := b.N % thread
    chn := make(chan bool,thread)
    b.ResetTimer()
    for core := 0; core < thread; core++ {
        mt_calc(div, chn)
    }
    for ix := 0; ix < mod; ix++ {
        Standard()
    }
    for core := 0; core < thread; core++ {
        <- chn
    }
}

func BenchmarkSThreadNewRand(b *testing.B){
    rnd := rand.New(rand.NewSource(0xCAFEBABE))
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        NewRand(rnd)
    }
}

func calc(max int, chn chan bool, seed int64){
    rnd := rand.New(rand.NewSource(seed))
    for index := 0; index < max; index++ {
        NewRand(rnd)
    }
    chn <- true
}

func BenchmarkNThread(b *testing.B){
    div := b.N / thread
    mod := b.N % thread
    chn := make(chan bool,thread)
    b.ResetTimer()
    for core := 0; core < thread; core++ {
        go calc(div, chn, int64(core))
    }
    for ix := 0; ix < mod; ix++ {
        Standard()
    }
    for core := 0; core < thread; core++ {
        <- chn
    }
}

func calc_wg(max int, wg *sync.WaitGroup, seed int64){
    rnd := rand.New(rand.NewSource(seed))
    for index := 0; index < max; index++ {
        NewRand(rnd)
    }
    wg.Done()
}

func BenchmarkNThreadWG(b *testing.B){
    div := b.N / thread
    mod := b.N % thread
    wg := &sync.WaitGroup{}
    wg.Add(thread)
    b.ResetTimer()
    for core := 0; core < thread; core++ {
        go calc_wg(div, wg, int64(core))
    }
    for ix := 0; ix < mod; ix++ {
        Standard()
    }
    wg.Wait()
}

改良内容

  • スレッド毎にrand.New を使ってロックしない乱数ジェネレータを使う
  • sync.WaitGroupも試してみる

改良結果

BenchmarkStandard-8                50000             26981 ns/op
BenchmarkMThread-8                 50000             26901 ns/op
BenchmarkSThreadNewRand-8         100000             15850 ns/op
BenchmarkNThread-8                300000              3376 ns/op
BenchmarkNThreadWG-8              500000              3350 ns/op

非ロック乱数を使うだけでもほぼ2倍の速度を得られ、Goroutineを8つ使うとシングル時の8倍の生成速度になった。
channelとwaitgroupでは大差がなかった。

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
3