ると（@cocoa_ruto）氏による記事です。彼がTwitterで「有名なオープンソースソフトで今まであったおもしろいバグを解説した本とかないだろうか」とつぶやいたところ、多くの人から反応があったためこの記事を書くに至ったようです。題材として彼がScalaのバグとして報告した例を挙げています。それはScala 2.9のコレクションAPIに含まれるmutable.HashSetでの要素のコピーがJava APIのHashSetに比べて100倍遅くなる、という問題です。再現コードも提示してあり、実際にその違いを実感できます。しかし、必ず遅くなるわけではなく、値をソートすると遅くなりません。ハッシュテーブルの処理が遅くなる原因として、多くの要素のハッシュ値が衝突してしまっていることが想像できますが、値のソートで速度が変わるというのが不思議なところです。

このバグの原因ですが、次の3つの条件がそろうことで起きてしまうようです。

• インデックスの計算に上位数ビットを利用した
• 複数要素の挿入時にテーブルのサイズを前もって拡大しなかった
• ハッシュテーブル内の要素を列挙する際にテーブルに入っている順に列挙した

このうち1つ目については、Scala 2.8までは下位数ビットを使っていたところ、2.9にて上位数ビットを使う実装に変更されたことが大きな原因となりました。なぜこのような変更が行われたかというと、Scala 2.9にて各操作の前にparと付けるだけで並列処理を行う並列コレクションを導入した際に、各コアが同期を行わずにハッシュテーブルを効率的に構築できるようにするための措置とのことです。

今回のバグはすでに修正が施されています。ちなみにバグ解説本については私も見たことはありませんが、非常に厄介なバグについての記事がまとめられたWebページとしては「BugStories」があり、今回紹介した記事へのリンクも掲載されています。

URL：http://www.tatapa.org/~takuo/bug/scala_mutable_hash_set_collision.html