浮動小数点数の加算の順序にハマった話

fediverseにちょっと書いたけど、仕事でちょっとハマって数時間悩んだ話。

とあるコードを書いていて、どうもテストが安定しなくてflakyになる。つまり、通るときは通るがたまに失敗する。が、理由がよくわからない。

こういうとき、Goでよくあるのはmapのイテレーションの順序が意図的にランダム化されているというパターンだ。mapは(内部的にはハッシュテーブルが使われているので)イテレーションの順序は不定であるし、不定であるべきなので順序に依存するコードを書くべきではない。現実的にはたいていの言語ではこのへんは「実装依存である」ということになっていて、うっかりすると言語のランタイムバージョンが上がったり、キーが一個増えたり減ったりするだけで順序が狂い、突然テストが死ぬみたいな現象によくみまわれる。Goでは意図的にこの問題に対処するために、言語のバージョンが変わらなくても毎回イテレーションの順番かわることになっている。実際、同じバイナリで同じmapをfor-loopで巡回するだけでも、毎回結果は異なったりする。たとえば次みたいに。

https://go.dev/play/p/fm_oDaAeXpI

ただ自分はそのことはよく知っているし、ここでいじってるコードのイテレーションの順番はわりと大事なのできちんと順序を保っているつもりでいた。それか、イテレーションの順番に影響なさそうな単純な集計だ。なのに微妙に結果がかわることがある。わけがわからない。困ったな……と思っていた。

そこでいろんなところにhackyな変更を入れたりしてデバッグしていたのだけど、しばらくしてひらめいて正しい修正ができたのだった。

実際にはコードのなかでは「単純な集計」をしている箇所があって、そのなかの集計のひとつはmapのなかの浮動小数点数を合計するというものだった。単純化するとこんな感じ。

func getTotal(m map[string]float64) float64 {
  var total float64
  for _, v := range m {
    total += v
  }
  return total
}

これは一見問題ないように見える。単純に合計しているだけだし。でもこういう計算が実はflakinessの原因になっていた。

浮動小数点数では大きな数と小さな数のあいだの演算をすると小さな数の下位ビットの情報が抜けおちるように計算される。そのため、上のコードのmのなかに大きな数値と小さな数値が混在していると、イテレーションの順番によって結果が微妙に異なってしまうというケースがありうる。これまた単純化された事例だけど、mapのsliceがあって、そのなかをスキャンして最大値をとるもののインデックスを知りたい、みたいなことがあったとしても、次のようにまったく同じmapなのにインデックスが変わってしまう、みたいなことがありうる。今回遭遇したのもだいぶ単純化されてるけどこういうパターン。

https://go.dev/play/p/HKyvY6BFOnm

ようするに浮動小数点数の加算順序は大事なのを見落していたということだ。たいていの場合、この順番のちがいの結果はほんとうに微差なので、微差を無視するような比較を実装するというのも手だし、getTotalするときの順番はどんなものでもいいがとにかく固定する(たとえばキーをソートしてその順番をつかう)という手もある。今回やったのはfloat64の値をもってきてその値でソートして小さい順に加算していくというもの。下位ビットの欠落が問題であるはずなので、これがまぁたぶんいちばん正しいだろうと思う、が、実際のところはほとんどどうでも良いということになるだろうと思う。

https://go.dev/play/p/HKyvY6BFOnm

というわけで、浮動小数点数の加算による情報の欠落も、mapの順序が不定になることも知ってはいたけれども実際に遭遇するとなかなか見つけづらいバグでした、という話でした。いやぁ浮動小数点数はむずかしいですね。あとあれだな、テストケースにそういうのが見つかるようなケースがあってよかったですね。