ハッシュが楽しい
イタリア人ハッカーが中心になって作ってる"Redis"が面白い。memcachedとかTokyo TyrantみたいなキーバリューのKVSに分類されるんだろうけど、リストやセットが扱えたり、keyを指定してintのincrementとかできる。ネットワーク帯域がやたら速くなって、バカみたいにメモリが安くなって来たので、これまでCで使ってきたデータ構造とか、Rubyみたいな言語のコアに組み込まれてたデータ構造をTCP/IP越しにやろうって話なのかな、という理解。
サーバ・クライアント方式でロックが不要だから、実はタプルスペースとして分散処理の集計サーバとかタスクキューに使えるんだとか、なんとなく楽しそうな感じ。FAQページの考察が面白い。Redisの実装自体は、たぶん目新しいものは何もなくて教科書的。しかも短く完結している。だから、コードの書き方、まとめ方なんかで、今のぼくにはとても勉強になる。
たとえば、"Doubly linked list"の実装は、見るからにお手本。文字列処理関連の関数群や、ソケット通信のラッパーだとか、イベント処理の自作ライブラリもなるほどなぁという感じ。mallocのラッパーは何をしてるのかなと見てみてたら、メモリ確保をカウントアップしてて、消費メモリ量をモニターしてるらしい、とか。mallocを自前のxmallocでラップする目的でよくあるのは参照カウンタを実装して、ぶら下がりポインタ防止とかなのかしらとか、そういうことを聞いたこともある。
で、いろいろと読んでいたらdict.cというハッシュテーブルの実装で、以下のような奇っ怪な関数にぶち当たった。
/* Thomas Wang's 32 bit Mix Function */ unsigned int dictIntHashFunction(unsigned int key) { key += ~(key << 15); key ^= (key >> 10); key += (key << 3); key ^= (key >> 6); key += ~(key << 11); key ^= (key >> 16); return key; }
まったく意味が分からない。謎めきすぎ。
ガチャリガチャリというエニグマ暗号機の音が聞こえてきそうな関数じゃないか。ハッシュというからには、きれいに分散するんだろうと思って、この関数に数値をいろいろ突っ込んでグラフにしてみたら、なんか周期性というかパターンが見える。うーん、あれ、ハッシュってそもそも何だっけ、この関数は何を目標にしてるんだと思いつつ、とりあえず「Thomas Wang」とかでググると、int->intのhash実装のあれこれが書いてある「"Integer Hash Function"」というページが出てきた。
これを起点にハッシュ関数について調べてみたら、これがすごく面白かった。奥村晴彦先生のアルゴリズム教科書にあるM系列乱数の話、線形合同の特徴と限界、メルセンヌ・ツイスターを発明した松本氏の乱数系列の話（ついでに松本氏の"エッセイ"とかも面白い）、FNV Hash、MD5やsha1が「破られた」話とか、もう延々とネタが尽きない。処理系によって乱数の実装がひどいこともあるのだと知った。MD5の値を一致させたままWindows用の実行バイナリをすり替える話とか、ちょっとワクワクする。
でもまあ、データ構造としてのハッシュについて言えば、Rubyのハッシュ、Linuxカーネルのハッシュとかを見て、それほど工夫の余地がないし、案外シンプルなので充分役立つのかなという気もしたりした。
線形合同のハッシュを計算するときにやる掛け算は、多くのプロセッサでビットシフト演算を使うほうが高速だけど、ふつうは掛け算として記述すればコンパイラが勝手に最適化してくれるのだということもLinuxカーネルのコメントを見ていて想像ができた（確認してないけど）。Linuxがキャッシュバッファとかにも使っているハッシュ関数の64ビット版はビットシフトをやっていて、「gccは最適化してくれないんだ」とため息が書かれていたりして。
(linux/hash.h) 26 static inline unsigned long hash_long(unsigned long val, unsigned int bits) 27 { 28 unsigned long hash = val; 29 30 #if BITS_PER_LONG == 64 31 /* Sigh, gcc can't optimise this alone like it does for 32 bits. */ 32 unsigned long n = hash; 33 n <<= 18; 34 hash -= n; 35 n <<= 33; 36 hash -= n; 37 n <<= 3; 38 hash += n; 39 n <<= 3; 40 hash -= n; 41 n <<= 4; 42 hash += n; 43 n <<= 2; 44 hash += n; 45 #else 46 /* On some cpus multiply is faster, on others gcc will do shifts */ 47 hash *= GOLDEN_RATIO_PRIME; 48 #endif 49 50 /* High bits are more random, so use them. */ 51 return hash >> (BITS_PER_LONG - bits); 52 }
ハッシュを調べてるうちに、クヌース御大のページにたどり着いた。FAQを見ると、人生最大最重要のプロジェクトであるThe Art of Computer Programmingを完成させるために、早期退職して、電子メールも読まないようにして、執筆活動を続けてると書いてある。プログラミングってどんだけ奥が深いんだと改めて思ったりしつつ。
