Rui:ThreadLibrary:NonBlockingHashTable

Rui:ThreadLibrary:NonBlockingHashTable

(編集中です)

目的

Gaucheの組み込みハッシュテーブルを、Non-blockingなハッシュテーブルで置き換える。

背景

組み込みのハッシュテーブルにはいくつか欠点がある。

概要

Click Cliff Jr.のnon-blockingハッシュテーブルを実装する。このハッシュテーブルはスレッドセーフだが、普通のハッシュテーブルと比べてシングルスレッドでのアクセスで性能がほぼ同じ、さらに数100スレッドからの同時アクセスでほぼ性能がリニアに伸びるというものである。


Click Cliff Jr.のnon-blocking hashtableを実装しようと思います。オリジナルのnon-blocking hashtableのアルゴリズムはとても洗練されており、rehashingをインクリメンタルに行って待ち時間が極力少なくなるよう工夫されていますが、そのぶんアルゴリズムが複雑です。ここでは複数のスレッドから安全に更新可能で、かつスレッドアンセーフなハッシュテーブルと遜色のないパフォーマンスの実装をGauche向けに作ることが目的なので、安全性に影響を与えない工夫は省くことにします。つまり、rehashingをインクリメンタルには行いません。(ちなみに手元のマシンではハッシュテーブルへのアクセスをmutexで保護すると1割ほどパフォーマンスが落ちます。)

これはClozure CLのnearly-lock-free hash tableとほぼ同じ方針です。ただし、Clozure CLではrehashing中にハッシュテーブルにアクセスしようとしたスレッドはロック待ちさせられるのですが、ここでの実装では、そういうスレッドは新しいハッシュテーブルへのエントリのコピーを手伝う(並行してコピーする)ようにしようと思います。

ハッシュテーブルのエントリの取りうる状態は、Clozure CLのそれにREHASHED状態を足した次のようになります:

State Key Value
DELETED1 object free-marker
DELETED2 deleted-marker free-marker
IN-USE object object
FREE free-marker free-marker
REHASHING object rehashing-marker
REHASHING free-marker rehashing-marker
REHASHING deleted-marker rehashing-marker
REHASHED rehashed rehashing-marker

REHASHED状態は、ハッシュテーブルのベクタをクリアするために足された状態です。Rehashingが完了して、かつそのテーブルをiterateしているスレッドがない場合に限り、rehashingを完了させたスレッドが元のテーブルをクリアします。Iterateしているスレッドがあった場合は、そのスレッドがクリアする責任を負います。ベクタをクリアするのはGC-frienlyにするためです。

DELETED2状態は、weak-keyハッシュテーブルの場合にのみ存在する、GCがキーをdeleted-markerで上書きした後の状態です。ハッシュテーブルを並行に更新しているときにキーを削除するのは一般には危険です。なぜなら、スレッドAがテーブルからキーKを見つけた直後に、スレッドBがそのキーを削除して新たにその空きエントリにキーK'、値V'を書き込むと、スレッドAは間違った値V'を読んでしまうからです。しかしweakハッシュテーブルの場合は安全です。というのもGCがKをdeleted-markerで更新しようとしているときには、Kはすでに参照不可能になっているので、あるスレッドがKをルックアップしているということがありえないからです。

(続く)

技術的なメモ

More ...