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

Shiro(2009/03/12 07:33:35 PDT):

仕事で、bignumをキーにした数十Mエントリのハッシュテーブルをばかすか使っていたら、意外にメモリを食いつぶすことに気づいたのでメモ。特に32bit環境で顕著。

追って行くと、どうもconservative GCの落とし穴にひっかかっている気配。

問題

こんな感じで、equalハッシュにがつんとデータを突っ込んで前後でアクティブなメモリ使用量を比べてみる:

(use srfi-27)
(define (random32)
  (+ (ash (random-integer 256) 24)
     (ash (random-integer 256) 16)
     (ash (random-integer 256) 8)
     (random-integer 256)))

(define (build)
  (define z (make-hash-table 'equal?))
  (dotimes (i 583463)
    (hash-table-put! z i (random32)))
  z)

(define (heapcheck thunk)
  (define (get-memsize)
    (gc) (gc)
    (let1 stat (gc-stat)
      (- (cadr (assq :total-heap-size stat)) (cadr (assq :free-bytes stat)))))
  (let* ((pre (get-memsize))
         (r (thunk)))
    (print (- (get-memsize) pre))
    r))

0.8.14では、次のように、80MBくらい食う (32bitマシン)

~/src/Gauche-0.8.14/src$ ./gosh -ftest -l hashtest
gosh> (heapcheck build)
83292160
#<hash-table equal? 0x85bf0c8>

この時のハッシュテーブルはbucketが262144個。エントリは4ワード=16バイト消費するので、ハッシュテーブルだけで消費するのはだいたい 262144×4 + 583463×16 = 10MBくらい。 random32の結果がほとんどbignumになり、これが一個あたり16バイト使うので加えて583463×16 = 9MB。しめて19MBくらいのはず。

さらに、buildを繰り返すとgcしてもメモリが回収されない。ハッシュテーブルに使われたぶんがほとんど残っている感じだ。

解析

どこからも参照されないはずなのに回収されないことから、conservative GCによる false pointerを疑う。 bignum自体はATOMICでアロケートしているのでfalse pointerにはならない。

とりあえず見つけたもの

各ハッシュエントリ中にハッシュ値をキャッシュしていたんだが、これは32bit fullな整数値なのでヒープが混んでくるとfalse pointerになる可能性が非常に高い。
ハッシュテーブルはエントリ数が増えるにつれbucket vectorを拡張するが、古いbucket vectorをクリアしていないので、false pointerが古いbucket vectorを指しているとそっから指されているエントリが回収されない。

試しにハッシュ値のキャッシュをやめて、古いbucket vectorをクリアしてみたら、 32MBくらいまで減った。

~/src/Gauche/src$ ./gosh -ftest -l hashtest
gosh> (heapcheck build)
33853440
#<hash-table equal? 0x9e249d8>

heapcheckの時点でハッシュテーブルと全てのエントリはまだ生きているので、何が減ったかというとrandom32で計算される中間結果に出現するbignumが考えられる。 false pointerがこいつらを指してしまうので回収されていない、という可能性だ。実際、概算してみると中間結果が37MBくらいになるので、まあまあ合ってる。

しかしこの状態でも計算値から10MB以上大きいのは気になる。その分はまだ理由がわからない。

それから、buildを繰り返してもハッシュテーブルのメモリが回収されない問題は依然として残っている。これは、ひとつでもfalse pointerがbucket vectorを指していると、そこから全てのエントリにつながっているので丸々回収されずに残ってしまうってことだろう。bucket vectorが大きければ大きいほど false pointerがそこを指す確率が高くなる。

実際、いちいちhash-table-clear!するときちんとメモリが回収されるようになる。 hash-table-clear!はbucket vectorをNULLで埋めるからだ。

追記(2009/03/14 04:57:25 PDT): bucket vectorを指すfalse pointerのせいで使ってないハッシュテーブルが開放されない問題だが、GC_malloc_ignore_off_page()を使ったら軽減されないかと思って試してみた。これは、ポインタがメモリブロックの先頭256バイトを指していない場合、そのポインタを無視するもの。有効なbucketは常にScmHashCore構造体が先頭を指しているから、途中を指すポインタを見る必要はない。 false pointerがでかいbucket vectorの途中を指していた場合、通常のGC_malloc ではbucket vector全体がretainされてしまうが、こちらはそういうことがなくなる。

メモリの合計が100MB弱くらいになるまでじわじわ増え続け、それ以降は安定する感じ。したがって回収漏れが一定数発生するものの、その影響は定数で抑えられるっぽい。

対策

とりあえずはハッシュ値のキャッシュをやめる。rehashの際のオーバヘッドが増えるが、背に腹は変えられない。いずれはcustom markerを使うことでキャッシュ部分だけはポインタではないと示してやろう。

その次のステップとして、連続したbucket vectorを使わないようにすべきだろう。ポインタの詰まった大きなベクタはconservative GCとは相性が悪い。 Clojureがやってるような、ツリーにするのが一案。根っ子の方をfalse pointerが指してるとやっぱり丸々残っちゃうけど、その確率はずっと小さくなる。途中の枝をfalse pointerが指している場合、残るのはそっから先に部分木にとどまる。

(2009/03/22 08:55:51 PDT): 従来のhashtableとは別に、圧縮されたノードを持つtrieをバッキングストレージにしたhashtableを実装した。データ量が小さい時はアクセス時間、メモリ使用量どちらも従来のhashtableより不利なんだけど(特に64bitでは)、データ量が10^5-10^6になってくるとアクセス時間もメモリ使用量もほぼ遜色無いか逆転する。そして、そういうでかいテーブルをいくつも作ると差は圧倒的。特に32bitでのfalse pointerの影響がうんと減って、仕事で書いてるアプリがメモリ2GB以上食ってたのが500MBに収まるようになった。

このデータ構造はClojureのハッシュテーブル実装と同じで、最大32分岐のノードによるツリー。各ノードはbitmapで存在する分岐を表して、存在する分岐のぶんだけポインタの配列を持つ。存在しない枝は2bitしか消費しない。 32bitのハッシュ値は最大7段のツリーになり、完全にハッシュ値がぶつかった場合はチェインする。ハッシュ値がほどよくばらけていれば1000要素でもポインタをたどるのは2〜3段で、一方従来のhashtableもコリジョンはチェインしてるからやっぱりポインタを2〜3段たどることは多く (平均のチェイン長が3になったらリハッシュするようにしているので)、そこはあんまり違わない。今回の構造の方がビット操作の分ちょっと遅くなるけど。一方、要素の追加時にはテーブル拡張とrehashing が不要になるので、特に要素数が増えるにつれ有利になってゆく。