SBCLのハッシュテーブルについて。
リストをハッシュテーブルのキーにしてequal（もしくはequalp）で比較する時、非常に遅くなることがある:
(defun test1 (size)
(declare (optimize (speed 3))
(fixnum size))
(let ((table (make-hash-table :test 'equal)))
(dotimes (x size)
(setf (gethash (list 0 0 0 0 x) table) t))))
(time (test1 20000))
;; Evaluation took:
;; 7.287 seconds of real time
;; 7.296875 seconds of total run time (7.296875 user, 0.000000 system)
;; 100.14% CPU
;; 18,175,364,371 processor cycles
;; 3,686,448 bytes consed
高々20000個のキーの登録に7秒かかるのは明らかにおかしい。この現象はテスト関数をequalpにしても変わらないのだが、次のように些細な変更をするだけで普通の処理時間になる:
(defun test2 (size)
(declare (optimize (speed 3))
(fixnum size))
(let ((table (make-hash-table :test 'equal)))
(dotimes (x size)
(setf (gethash (list 0 0 0 x 0) table) t))))
(time (test2 20000))
;; Evaluation took:
;; 0.006 seconds of real time
;; 0.000000 seconds of total run time (0.000000 user, 0.000000 system)
;; 0.00% CPU
;; 14,992,420 processor cycles
;; 3,622,624 bytes consed
test2は(list 0 0 0 0 x)の部分を(list 0 0 0 x 0)に変えただけである。
こうなる原因は、SBCLのsxhashがリストを一定の深さまでしか走査しないことにある。この深さはsb-impl::+max-hash-depthoid+として定められていて、4になっている。
CL-USER> (sxhash '(0 0 0 0 0))
75491649990944584
CL-USER> (sxhash '(0 0 0 0 1))
75491649990944584
CL-USER> (sxhash '(0 0 0 1 0))
2843277705398422980
つまり、上のように(0 0 0 0 ...)というリストは以降のセルに関係なく同じハッシュ値になるので、test1ではすべてのハッシュ値が等しくなっている。キーが全部衝突すると既存のキーとマッチングする処理がになるので、test1はということになる。1
回避策はいろいろありそう。とりあえず、equalpで配列や構造体を使えばこの問題は起こらない。あくまでリストを使いたければ、適当なハッシュ関数を与えればよい:
(defun list-sxhash (x &optional (depthoid 100))
(declare (optimize (speed 3))
(fixnum depthoid))
;; sxhashの該当部分をそのまま使っている
(typecase x
(null (sxhash x))
(cons (if (plusp depthoid)
(sb-int:mix (list-sxhash (car x) (1- depthoid))
(list-sxhash (cdr x) (1- depthoid)))
261835505))
(t (sxhash x))))
(defun test3 (size)
(declare (optimize (speed 3))
(fixnum size))
(let ((table (make-hash-table :test 'equal
:hash-function #'list-sxhash)))
(dotimes (x size)
(setf (gethash (list 0 0 0 0 x) table) t))
table))
(time (test3 20000))
;; Evaluation took:
;; 0.012 seconds of real time
;; 0.000000 seconds of total run time (0.000000 user, 0.000000 system)
;; 0.00% CPU
;; 31,158,036 processor cycles
;; 3,676,928 bytes consed
sb-int:psxhash（equalp用のハッシュ関数）には深さが指定できるので、:testをequalpをにしてこれを:hash-functionに与えるのが一番簡単かと思ったのだが、psxhashに与える深さは+max-hash-depthoid+以下でなければならないようで、この方法は不可能だった。なぜそんな制限があるのかはよくわからない。
以前に気づいた現象だったが、自分の記事を見返していてやっぱり何かおかしいなと思って調べたら、意外と単純な話だった。
+max-hash-depthoid+がかなり小さい値になっている理由は特に書かれていないけど、キーに循環構造がある場合は+max-hash-depthoid+いっぱいまで走査することになるのであまり大きくはできないだろうなという理解。
追記: ハッシュテーブルの挙動メモ
sb-int:psxhashによるベクタのハッシュ値の計算、つまりテスト関数がequalpの時の処理では、次の型が特別にディスパッチされているので、この中のどれかなら少し速い:
simple-base-string(simple-array character (*))simple-vector(simple-array (unsigned-byte 8) (*))(simple-array fixnum (*))
ただし、(unsigned-byte 8)をワード毎にまとめて計算とかは基本的にやっていない。それをやるのはたぶんsimple-bit-vectorに対するsxhashだけ。
また、ハッシュテーブルに最後に登録・アクセスしたキーは特別に保持され、gethashを呼ぶたびにeqで比較される。つまり、例えばキーの存在判定をして無ければ登録する、みたいな処理をする時、2回gethashを呼んだらキーが2回走査されて遅いかもという心配はあまりしなくてよい。
g000001さんによると、どの処理系でもだいたい事情は同じらしい。
