ただの足し算だし順序依存ないだろと思っていたらそうでもなかった話
並行プログラミングの勉強をしています。読んでいる本に例題があったので、その本が提示する鉄則に従って
- 逐次処理を書く
- 独立した処理を見つける
- 独立した処理を並行化する
- テストする
を行ったところ、最初から躓いたのでメモに残します。
円周率の近似値を求める逐次処理
例題として円周率の近似値を求める関数が上げられています。
func compute(rectCount int) float64 {
sum := 0.0
width := 1.0 / float64(rectCount)
for i := 0; i < rectCount; i++ {
mid := (float64(i) + 0.5) * width
height := 4.0 / (1.0 + mid*mid)
sum += height
}
return sum * width
}
並行化
ループ内の計算は各ループから独立しているため並行化が可能です。
func computeC(rectCount, workers int) float64 {
sum := 0.0
width := 1.0 / float64(rectCount)
ch := make(chan float64)
// worker あたりの計算量を []int で返す関数。略。
works := splitWorks(rectCount, workers)
head := 0
for _, n := range works {
tail := head + n
go func(ch chan float64, head, tail int) {
sum := 0.0
for i := head; i < tail; i++ {
mid := (float64(i) + 0.5) * width
height := 4.0 / (1.0 + mid*mid)
sum += height
}
ch <- sum
}(ch, head, tail)
head = tail
}
for i := 0; i < workers; i++ {
sum += <-ch
}
return sum * width
}
テストが通らない
しかしこれでは同じ結果を得られませんでした。
<br/>func TestCompute(t *testing.T) {
rows := []struct {
total int
workers int
comp func(int, int) float64
}{
{10000, 1, computeC},
{10000, 2, computeC}, // 落ちる
{10000, 10, computeC}, // 落ちる
}
for _, row := range rows {
ex := compute(row.total)
ac := row.comp(row.total, row.workers)
if ex != ac {
fmt.Printf("%+v, %+v: %+v %+v\n", row.total, row.workers, ex, ac)
t.Fail()
}
}
}
10000, 2: 3.141592654423134 3.141592654423129
10000, 10: 3.141592654423134 3.1415926544231265
--- FAIL: TestCompute (0.00s)
worker 数が 1 の時のみ通ります。
足し算で丸め誤差が起こる
結果の数値でだいたい察せられたかもしれません。この微妙な差異は float64 丸め誤差で起こっています。
worker が 1 の時は必ず同じ順序で加算されます。これは逐次処理の順序と同じなのでテストが通ります。
一方で worker が 2 以上の場合はworker 内での加算は常に 0.0 から始まり、最終的に加算される順序も不定です。 そのため、同じ worker 数でも同じ結果が返るとは限りません。
10000, 10: 3.141592654423134 3.141592654423127
10000, 10: 3.141592654423134 3.1415926544231265
10000, 10: 3.141592654423134 3.1415926544231274
--- FAIL: TestCompute (0.00s)
順序を保証する
ならば順番を保証すればよいということで、+= height を後回しにしました。これにより、無事テストが通りました。
func computeCC(rectCount, workers int) float64 {
sum := 0.0
width := 1.0 / float64(rectCount)
ch := make(chan WorkerResult)
works := splitWorks(rectCount, workers)
head := 0
for _, n := range works {
tail := head + n
go func(ch chan WorkerResult, head, tail int) {
result := WorkerResult{
Head: head,
Heights: make([]float64, tail-head),
}
for i := head; i < tail; i++ {
mid := (float64(i) + 0.5) * width
height := 4.0 / (1.0 + mid*mid)
result.Heights[i-head] = height
}
ch <- result
}(ch, head, tail)
head = tail
}
heights := make([]float64, rectCount)
for i := 0; i < workers; i++ {
ms := <-ch
for i, height := range ms.Heights {
heights[ms.Head+i] = height
}
}
for _, height := range heights {
sum += height
}
return sum * width
}
ベンチマーク
BenchmarkCompute-8 50 36383353 ns/op
BenchmarkComputeC-8 200 9884245 ns/op
BenchmarkComputeCC-8 30 47883258 ns/op
BenchmarkComputeBig-8 1 12168459303 ns/op
最初の並行化 BenchmarkComputeC はスレッドの分だけの高速化がされています。順序を保証する BenchmarkComputeCC では逐次処理 BenchmarkCompute より遅くなってしまいました。
BenchmarkComputeBig は BenchmarkComputeCC での低速化をうけて、他に計算結果を保証する方法はないものかとまず逐次処理を big.Float で行った結果です。めちゃくちゃに遅くなったので並行化はしませんでした。
まとめ
本の後半でこの例題を扱うという話なのですが、まだそこまで至っていないので、この本ではどのように解決されているのかはわかりません。
しかし一見簡単に見えた関数を並行化することによって、問題ある結果を返すようになってしまうというのは出だしのいい薬になった気がします。