Rui:ThreadLibrary:NonBlockingHashTable

（編集中です）

目的

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

背景

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

• スレッドセーフではない 複数のスレッドから同時にアクセスするとデータが壊れることがあり得る。ハッシュテーブルはGaucheの中のさまざまな場所で使っているので、ユーザプログラムがハッシュテーブルをmutexで保護していても、知らないところで問題が起きることがある。たとえばシンボルテーブルはハッシュテーブルだが、これへのアクセスは排他制御されていないので、複数のスレッドが同時にシンボルを作成するとシンボルテーブルが壊れる可能性がある。Mutexで保護するとパフォーマンスに影響がある。
• キーをや値をweak参照にできない Weakハッシュテーブルがなない。Weakハッシュテーブルが便利な場面はたとえばGauche:シンボルのgcを参照。

概要

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状態を足した次のようになります:

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をルックアップしているということがありえないからです。

（続く）

• Shiro: 書きかけにコメントも何なのですが、Gaucheの組み込みハッシュテーブル 自身をnon-blockingにしたいと思っていました。そのための第一段階として現在chainingに なってるのをopen addressingに変えようと思ってるとこで止まっていたのですが… なので(拡張モジュールとしてでなく)組み込みハッシュテーブルをこれで置き換えられたら うれしいです。(ただ、現在のScm_HashCore系APIはScmDictEntry*を返すので そのままでは対応しにくいかも。Scm_HashTable系APIは実装だけすげかえることを 考えてああいうふうにしたのですが)。
  compare-and-swapについては、Boehm GC内のatomic_opsを使えるんじゃないかと 思っています。どうせリンクしているわけなんで。

• Rui: そうですね、組み込みハッシュテーブルを置き換えられる形で開発しようと思います。ScmDictEntry*を返す現状のAPI（旧API）を維持するのは難しそうなので、新しいAPIに移行したいところですが、しばらくは両方の実装とAPIを残す必要がありそうです。現状のハッシュテーブルに新APIのラッパーを実装したうえで、Gauche本体についてはすべて新APIを使うように変更、当面はGAUCHE_NEW_HASHTABLE_APIが定義されているときのみnon-blockingハッシュテーブルが有効になる、という感じがいいでしょうか。GAUCHE_NEW_HASHTABLE_APIを定義してGaucheをビルドすると、新APIに移行していないモジュールはコンパイルできなくなりますが、デフォルトで定義するまでに移行してもらうということで。

• Shiro: HashCoreのAPIは比較的新しいんで、実はそれほど使われてないんじゃないかって 気もします。CoreとTableの区別は主として、前者はintptr_tを扱う、後者はScmObjを扱う、 って分け方だったような。 ただ、HashCore APIはTreeCore APIと対になってるんで、変えるなら両方変える必要が ありますね…
  むしろ、ScmHashCoreとScmHashTableを切り離す方がいいかも。
  1. non-blocking実装に適した下位レイヤのAPIの定義と実装 (仮にScmHashBase, ScmTreeBaseとする。)
  2. ScmHashTableの下位実装をScmHashBaseにすげ変える。Gauche内部で下位レイヤに依存してるところもScmHashBaseを使って書き直す。
  3. ScmHashCoreは互換ライブラリとして独立させてしばらく残した後、フェードアウト。

• Rui: Scm_HashTableGetで見つかったScmHashEntry*のvalueを直接変更しているコードが結構あるんですが、こういうコードは安全には動きませんよね。エントリを見つけた後、変更する前に、rehashingが走ってしまうと、古いテーブルをだけを変更することになるので。となるとCoreだけではなくTableのAPIも変えないといけないような？ ハッシュテーブルへのアクセスは完全に隠蔽して、get操作はScmHashEntry*ではなく見つかった値そのものを返す、変更はそれ用のAPIを追加する、というふうにしようかなと思うのですが。

• Shiro: ああ、Scm_HashTable{Get|Add|Put}はもうだいぶ長い間deprecatedなんで、この機会にフェードアウトさせちゃう方がいいと思います。Scm_HashTable{Ref|Set}が現在の正式なAPIです。

技術的なメモ

• コンペア・アンド・スワップ、Lock-freeとWait-freeアルゴリズム - Wikipediaの記事
• x86のメモリモデルは、Intel 64 and IA-32 Architectures Software Developer's Manual Volume 3A: System Programming Guideの7章に説明がある。
• nbds: Lock-freeなハッシュテーブル、リスト、スキップリストのCによる実装。パブリックドメイン。