バグから学ぶ計算機科学 Scalaのハッシュテーブルにおいて並列コレクションのためのコード変更が大量の衝突を引き起こした事例

バグから学ぶ計算機科学 Scalaのハッシュテーブルにおいて並列コレクションのためのコード変更が大量の衝突を引き起こした事例 書いた人: ると 書いた日: 2012年1月21日 はじめに Twitterで「有名なオープンソースソフトで今まであったおもしろいバグを解説した本とかないだろうか」とツイートしたらそれなりに需要があるようでした。そこで先ず隗より始めよという故事にのっとり、死馬の骨としてバグ解説記事を書いてみます。 今回のバグはScala 2.9の標準ライブラリに含まれるmutable.HashSet(ハッシュテーブルを使った重複無しコレクション)のコピーがJavaの標準ライブラリに含まれるHashSetの100倍遅いというバグです。並列コレクションのためにぱっと見問題の無い変更を加えたら思わぬところで影響が出たというものです。 なお、今回はScalaに関するバグですが、Scalaに

[rryu]

ハッシュテーブルへの挿入が100倍遅くなったバグとその原因。

[Naruhodius]

ふむー

[raimon49]

並列処理でCPU資源を有効活用するためにハッシュテーブルのインデックスでは下位nビットから上位nビットを使う実装に変更→ハッシュテーブルのコピーのように大量に挿入する場面で、テーブルサイズ拡大時にインデック

[t-wada]

読み物としても面白い

[hiratara]

企画として面白そうだなあ。 「> きっと世の中のBTSにはこういうおもしろいバグが沢山あるはずです。」

[twainy]

並列処理のために上位ビットをハッシュインデックスに使用していたら、連続した値の挿入時に衝突が発生しまくってパフォーマンスが劣化するという話

[takkunn1611]

バグから学ぶ計算機科学 Scalaのハッシュテーブルにおいて並列コレクションのためのコード変更が大量の衝突を引き起こした事例

[lizy]

あんまし内容には関係ないけど「parというメソッドを挟むだけで各要素を並列に処理するコレクションになります」こういう局所的なものは効果あるんだろうか