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

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にはならない。

とりあえず見つけたもの

試しにハッシュ値のキャッシュをやめて、古い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 が不要になるので、特に要素数が増えるにつれ有利になってゆく。

More ...