maphashによる各エントリへのアクセスはO(1)とは限らない

SBCLのハッシュテーブルについて。

ハッシュテーブルのキーをなんでもいいから1つ消したいとする。ANSI CLのハッシュテーブルに該当する機能はない。しかし、そういう関数を定義するのは特に難しくなさそう:

(defun pophash (hash-table)
  (maphash (lambda (key _)
             (remhash key hash-table)
             (return-from pophash key))
           hash-table))

maphashの中で受け取ったエントリを消去するのは許されているので、pophashは意図通り動作する。しかし……

(defun test-pophash (size)
  (let ((table (make-hash-table :size size)))
    (dotimes (i size)
      (setf (gethash i table) t))
    (dotimes (i size)
      (pophash table))))

(time (test-pophash 200000))
;; Evaluation took:
;;   15.268 seconds of real time
;;   15.265625 seconds of total run time (15.265625 user, 0.000000 system)
;;   99.99% CPU
;;   38,084,922,378 processor cycles
;;   5,848,704 bytes consed

たった$4 \times 10^5$回の操作に時間が掛かりすぎである。

もちろん、次のようにremhashするだけなら計算量の問題はない。

(defun test-pophash2 (size)
  (let ((table (make-hash-table :size size)))
    (dotimes (i size)
      (setf (gethash i table) t))
    (dotimes (i size)
      (remhash i table))))

(time (test-pophash2 200000))

;; Evaluation took:
;;   0.016 seconds of real time
;;   0.015625 seconds of total run time (0.015625 user, 0.000000 system)
;;   100.00% CPU
;;   37,052,672 processor cycles
;;   5,848,704 bytes consed

---

そもそもchainingによるハッシュテーブルがキーをどう管理するか考えてみると、pophashがだめなのはそれはそうという感じだった。以下、手短に動作を見てみる:

CL-USER> (let ((table (make-hash-table)))
	   (setf (gethash 3 table) 8
		 (gethash 5 table) 32
		 (gethash 7 table) 128)
	   (print (sb-impl::hash-table-pairs table))
	   (remhash 5 table)
	   (print (sb-impl::hash-table-pairs table))
	   (setf (gethash 11 table) 2048)
	   (print (sb-impl::hash-table-pairs table)))

#(3 0 3 8 5 32 7 128 #<unbound> #<unbound> ... #<unbound>
  #(0 60102308 60102306 60102304 0 0 0 0 0 0 0 0 0 0 0)) 
;; キー5を消す
#(3 0 3 8 #<unbound> #<unbound> 7 128 #<unbound> #<unbound> ... #<unbound>
  #(0 60102308 60102306 60102304 0 0 0 0 0 0 0 0 0 0 0)) 
;; キー11を追加する
#(3 0 3 8 11 2048 7 128 #<unbound> #<unbound> ... #<unbound>
  #(0 60102308 60102317 60102304 0 0 0 0 0 0 0 0 0 0 0)) 

上のように¹、ハッシュテーブルの中身は単に配列に並んでいて、remhashによって消されるとそこが消えるだけである。unboundになったインデックスはうまく連鎖的に管理されていて、次に追加する時にはそこが埋まるようになっている。²

さて、maphashだが、実装を見ればわかるように、pairsを先頭から末尾まで走査するだけだ。つまり、上のpophashは常に先頭から走査して見つけたキーを消すように動くので、全体では${\mathcal O}(N^2)$になってしまう。

また、同じような理由で次のコードも計算量の問題がある:

(defun test-maphash (size)
  (let ((table (make-hash-table :size size))
        (sum 0))
    (dotimes (i size)
      (setf (gethash i table) t))
    (dotimes (i (- size 1))
      (remhash i table))
    (dotimes (i size)
      (maphash (lambda (x _) (incf sum x)) table))
    sum))

(time (test-maphash 200000))
;; Evaluation took:
;;   34.567 seconds of real time
;;   34.562500 seconds of total run time (34.562500 user, 0.000000 system)
;;   99.99% CPU
;;   86,197,938,782 processor cycles
;;   5,848,704 bytes consed

ハッシュテーブルに$200000$個のキーを登録したあと$1$個まで減らし、そのテーブルに対してmaphashを$200000$回適用している。これも、同じ原理で${\mathcal O}(N^2)$になる。maphashによる走査は確かに${\mathcal O}(N)$だけれど、テーブルの今の要素数に対する${\mathcal O}(N)$ではなく、過去に到達した最大要素数に対する${\mathcal O}(N)$なので、各エントリへのアクセスが${\mathcal O}(1)$になるとは限らないのだった。³

この最大要素数はSBCL内部ではhigh-water-markと呼ばれている。こういう実装になったのはバージョン1.5.5からで、それ以前は事前に確保したサイズに対する${\mathcal O}(N)$だったようだ。該当コミットはこれ。次のコードで違いがわかる:

(defun test-maphash2 (size)
  (let ((table (make-hash-table :size size))
        (sum 0))
    (setf (gethash 0 table) t)
    (dotimes (i size)
      (maphash (lambda (x _) (incf sum x)) table))
    sum))

(time (test-maphash2 200000))
;; SBCL 1.5.8, O(n)
;; Evaluation took:
;;   0.016 seconds of real time
;;   0.015625 seconds of total run time (0.015625 user, 0.000000 system)
;;   100.00% CPU
;;   16,126,752 processor cycles
;;   5,848,704 bytes consed
  
;; SBCL 1.4.14, O(n^2)
;; Evaluation took:
;;   47.615 seconds of real time
;;   47.625000 seconds of total run time (47.625000 user, 0.000000 system)
;;   100.02% CPU
;;   118,798,016,334 processor cycles
;;   8,497,264 bytes consed

ハッシュテーブルの要素数が大きくなるかもしれない場合に、リハッシュの回数を減らそうとして最初に:sizeを大きめに取っておくという発想は普通っぽい感じだけど、1.5.5より前のバージョンでは逆に遅くなる可能性がある。

---

maphashが今の要素数に対する${\mathcal O}(N)$になるような実装って可能かな？ と少し考えていたけど、とりあえず既存のエントリ全体（と消したエントリ全体）のチェインをnext-vectorとは別に持てばできそう？ 定数倍が重くなるわりに、できるようになることが大したことない感じだけど……

---

1. pairsの最初の2つのエントリと末尾のエントリはテーブルの管理に使われている。また、SBCLのハッシュテーブルの実装は最近変わったので、上のコードはたぶんバージョン1.5.5以降でないと動かない。 ↩︎

2. sb-impl::hash-table-next-vectorがインデックスの管理に使われる。 ↩︎

3. 最初は「ならしで${\mathcal O}(1)$」と書いたけど、よく考えるとおかしかった。アクセスが最悪$\omega (1)$で償却${\mathcal O}(1)$にするには別の例を挙げる必要がありそう。$N$個登録した後$N/2$個消すとか？ ↩︎