Gauche:MTとハッシュテーブル

Gauche:MTとハッシュテーブル

Rui (2007/05/29 20:16:12 PDT): 0.8.9のハッシュテーブルがスレッドセーフではない件について。同時にアクセスするとハッシュテーブルの内部構造が壊れてしまう、というのと、MTセーフにするにはAPIが足りない、という2点。

問題

Gaucheのハッシュテーブルは複数スレッドの同時アクセスを考慮していない。チェイン法なのでハッシュが同一のキーは連結リストに繋げられるが、こういったデータ構造でキーの追加を同時に行うと、同一のキーが複数追加されてしまったり、どちらも追加されない可能性がある。テーブルのリサイズが走った場合には、新しいテーブルサイズをセットしてから新テーブルのポインタをセットする間に別のスレッドが構造体にアクセスすると、SEGVることもありえる。

また、string->symbolなどはスレッドセーフではない。

 ScmHashEntry *e = Scm_HashTableGet(obtable, SCM_OBJ(name));
 if (e) return e->value;
 else {
     ScmObj n = Scm_CopyStringWithFlags(name, SCM_STRING_IMMUTABLE,
                                        SCM_STRING_IMMUTABLE);
     ScmSymbol *sym;
     INITSYM(sym, n);
     Scm_HashTablePut(obtable, n, SCM_OBJ(sym));
     return SCM_OBJ(sym);
 }

上はScm_Internのコードだが、HashTableGetしたあとPutするまでの間に別のスレッドがScm_Internを呼ぶとインターンされていないシンボルが返ってしまう。キーがないときに限り追加するAPIがいる。(それかScm_Internの呼び出しを排他制御するか……)

さてどうするか

Lock-free Hash Table これを実装するというのはどうでしょうか > shiroさん。MTセーフで性能もよいようなので。ただ、open addressing法なのでバケットというものがなく、APIがガラッと変わってしまいそうなんですよね。

Shiro(2007/05/29 21:16:56 PDT): 「キーが無いときに限り追加する」APIは既にあります (旧APIではScm_HashTableAdd, 新APIではScm_HashTableSetにSCM_DICT_NO_OVERWRITE フラグを渡す)。

あと、今たまたまhashtableの実装を見直してて、open addressingにするかもしれません (coalesced hashingに変えてベンチマークを取ろうとしてるところ)。 というのは今の実装だとkey-weakなweak hash tableが効率良く実装できないっぽい ことに気づいたので。APIは変えずにいけると思います。

上のlock free hashtableは注目してはいるんですが、Gaucheに適用可能かどうかは やってみないと何ともいえません。

Rui(2007/05/30 00:10:48 PDT): 「キーがないときに限り追加する」というのはMTセーフなようアトミックに追加するという意味でした。実装見直し中ということでそれを待つのがよさそうですね。

More ...