『Javaの理論と実践: 優れたHashMapの構築』を読んで間違いを見つけた
優れたHashMapの構築
記事：
メモ：
- CuncurrentHashMap の実装を見てみる
- スループットが最適化されている
- 複数の書き込みロック。ハッシュバケットに対する 32 のロックコレクション。
- size() や isEmpty() についても、操作のセマンティクスを変更することで全体をロックする必要がなくなった。
- map rehashing （バケット数の再配分）のような操作は全体に対する排他アクセスが必要
- JMM（Java Memory Model）の概念
- あるスレッドのメモリへのアクションが、他のスレッドのメモリアクションにどう影響するかを定義
- パフォーマンのためにメモリの可視性をゆるめた定義になっている
- 明示的な同期化がない場合、実装はメインメモリーを自由に更新可能
- 同期化の役割
- アトミック性
- 可視性
- 順序
- アトミック性に焦点がいきがちだが、可視性と順序も重要
- モニタ取得時に読み込みバリアを実行
- キャッシュを無効にし、メインメモリから読み込む
- モニタ解放時に書き込みバリアの実行
- キャッシュを無効にし、メインメモリに書き込む
- ConcurrentHashMap の実装について
- 取得（get）
- ロックを取得しない
- => 不整合を検知する実装が必要。
- エントリー要素を不変にする
- 要素は先頭に追加
- 古い JMM に対応するために null チェックして、おかしければ再度同期化してという二重構造
- 値エントリは volatile になっている
- 削除（remove）
- 値エントリを null にする。 volatile なのですぐ可視になる。
- 検索時に値エントリが null だと不整合なので、同期化して再検索する。
- 実装が間違ってる？
- 追加（put）
- バケットロックを取得して普通に更新
- 走査（iterator)
- fail-fast ではなく、弱い整合性を保つ
- 各連鎖の headPointer は最新になる
- 各連鎖への挿入は反映されるかは分からない
- 値の更新・削除は反映される（値フィールドは volatile だから）
- ConcurrentModificaitonException はスローしない
- ハッシュバケットの変更（rehasing）
- 連鎖の長さを調べて、一定数以上の連鎖が一定数以上増えるとロックを取得しながら再帰的に各バケットを広いハッシュ表にする
- get ロックフリーなのか？
- value フィールドは volatile なのでロックフリーだと思われがちである
- ただし JMM 上は volatile も syhchronization も同様のキャッシュ整合性プリミティブなので、ロッキングされてるともいえる
感想
感想というか、この記事に間違いを見つけた。
以下の箇所。
Javaの理論と実践: 優れたHashMapの構築：削除オペレーション
ここで例示されてるソースコード（『リスト3. ConcurrentHashMap.remove()実装』）と削除後の結果（『図2. 要素の削除』）があってない。
Entry first = tab[index]; ... （省略）... // e は削除対象の要素 Entry head = e.next; for (Entry p = first; p != e; p = p.next) head = new Entry(p.hash, p.key, p.value, head);
この部分、見つかった要素を除外してリストを再構築している。 for 文をリストの最初から最後に向かってまわしているので、2->1->4 となるのが正しいはずだが、1->2->4 と説明されている。
（ref: http://www.ibm.com/developerworks/jp/java/library/j-jtp08223/#3.4）
最近はドキュメントを github で管理しているサイトも多くて、そういう場合にはなるべく見つけたミスを修正して PR するようにしているのだけど、今回はどうしようかな。ずいぶんと前の記事だし…。
（追記） 英語版の方では何件か「間違ってるよ」コメントがついてた。 Java theory and practice: Building a better HashMap
