アイドル時に実行されるGC処理のパフォーマンスが悪く、フリーズすることがある

[todesking]

特定のメモリ確保パターンにおいて、メモリ解放処理(eval.c:garbage_collect())のパフォーマンスが劣化して長時間フリーズする問題があるようです。

小さな再現パターンをまだ発見できていませんが、Unite.vim で大量(数万件)のcandidateを表示させるのを何度か繰り返した後で10秒ほど放置することで再現します(放置時に裏でgarbage_collectが実行される)。

パッチは以下。

todesking/vim@eed1844

[koron]

つまり後に作った dict から順番に開放されるようなケースを作ればいいんですかね?

[koron]

今の構造なら、1000個も作れば O(n^2) で100万回オーダーでループが走りそう。

[Shougo]

👍

お疲れ様です。
私もこの問題を調べていた時がありまして、大量にメモリを消費していると(Vim のメモリ消費量 700MB 程度で確認) 10 数秒 GC で Vim がフリーズします。

unite.vim 特有の問題ではないはずですが、unite.vim を使っている時に起きやすいです。
原理上は ctrlp.vim 等でも起きると思うのですが……。

[koron]

@Shougo たとえば、ループ内でdict作って、そのメンバーとして前回のループで作ったdictを格納する、みたいなことしてますか?
コードで示すとこんな感じ

let d = {}
let i = 0
while i < 10000
  let d = { prev: d }
  let i += 1
endwhile

" use d

[Shougo]

unite.vim は前回の candidatesをキャッシュしているので、似たようなコードになっているのではないかと考えています。パフォーマンスを稼ぐために候補のキャッシュが分散しており、どこに何が格納されているかは私でさえ把握できていません。

[todesking]

まだ詳細を追っていないのですが、Vimのメモリ解放タイミングはいくつかあるようです。
例えばlet var = new_value 実行時には古い値の参照カウントを減少させて0なら開放する処理が走っている模様(set_var_lval()内でclear_tv()が呼ばれている)

それらのタイミングで開放できなかったメモリがgarbage_collect()で処理されているようですが、それがどういった条件なのかがわからず。おそらく循環参照まわりじゃないかと思いますが。

[h-east]

いちおうユーザが呼び出すことも出来るのね
:h garbagecollect()

[Shougo]

はい。その通りです。VimのGCはPythonと同じで参照カウント + Mark Sweep になっています。
参照カウントでは循環参照が開放できないので、Mark Sweep を併用しています。
コードを見た限りだと、garbage_collect() を呼んだ時、メモリが足りない時（メモリ確保失敗）、
Vim がアイドル状態の時(CursorHold のタイミング)で Mark Sweep GC が呼ばれるようです。

unite.vim の場合、リストを大量に生成しており、それらの中身も非常に複雑となっています。
循環参照が発生しやすいので Mark Sweep GC が呼ばれるのではないかと考えられます。

[todesking]

今試したら一瞬で再現出来ました(；´Д｀)

let s:hoge = {}
let s:fuga = {}
let s:arr = []

function! Prepare() abort " {{{
  let s:hoge.a1 = map(range(1, 100000), '{}')
  let s:hoge.a2 = map(range(1, 100000), '{}')
  let s:hoge.a3 = map(range(1, 100000), '{}')
  let s:hoge.fuga = s:fuga
  let s:fuga.hoge = s:hoge
endfunction " }}}

function! Release() abort " {{{
  let s:arr = s:hoge.a2
  unlet s:hoge
  unlet s:fuga
endfunction " }}}

call Prepare() -> call Release() -> call garbagecollect() でフリーズ

[Shougo]

おお、素晴らしい。

@todesking こちらでも .vimrc なし、上記の手順で再現しました。これはいけそうです。

[ynkdir]

list も同じ問題ありです

[todesking]

パッチ(改)

diff --git a/src/eval.c b/src/eval.c
index ae8331d..8fd3d99 100644
--- a/src/eval.c
+++ b/src/eval.c
@@ -6900,7 +6900,9 @@ free_unref_items(copyID)
     int copyID;
 {
     dict_T     *dd;
+    dict_T     *dd_next;
     list_T     *ll;
+    list_T     *ll_next;
     int                did_free = FALSE;

     /*
@@ -6912,11 +6914,10 @@ free_unref_items(copyID)
            /* Free the Dictionary and ordinary items it contains, but don't
             * recurse into Lists and Dictionaries, they will be in the list
             * of dicts or list of lists. */
+           dd_next = dd->dv_used_next;
            dict_free(dd, FALSE);
            did_free = TRUE;
-
-           /* restart, next dict may also have been freed */
-           dd = first_dict;
+           dd = dd_next;
        }
        else
            dd = dd->dv_used_next;
@@ -6933,11 +6934,10 @@ free_unref_items(copyID)
            /* Free the List and ordinary items it contains, but don't recurse
             * into Lists and Dictionaries, they will be in the list of dicts
             * or list of lists. */
+           ll_next = ll->lv_used_next;
            list_free(ll, FALSE);
            did_free = TRUE;
-
-           /* restart, next list may also have been freed */
-           ll = first_list;
+           ll = ll_next;
        }
        else
            ll = ll->lv_used_next;

[todesking]

"next dict/list may also have been freed" というコメントがどうにも不安なんですが、そういうケースないように見える……

[ynkdir]

ありがとうございます
dict_free, list_free に recurse が追加される前のコメントなので古いのかもしれません

[mattn]

お忙しそうな感じなので最新でパッチ作成

https://gist.github.com/0c58a7398c63ab4c3066

[mattn]

良さそうに思います。

@todesking パッチ提出お願い出来ますか？

[todesking]

了解しました(vim_devにですよね?)

[mattn]

そのとおり！

[h-east]

「このscriptがxx秒掛かっていたけどこのpatchをあてたらyy秒に改善されたぜ！」みたいな数値的があればgood.

[mattn]

@todesking お忙しい様なら送信代行(お名前は存じております)出来ますがどうしましょうか？

[Shougo]

「このscriptがxx秒掛かっていたけどこのpatchをあてたらyy秒に改善されたぜ！」みたいな数値的があればgood.

let s:hoge = {}
let s:fuga = {}
let s:arr = []

function! Prepare() abort " {{{
  let s:hoge.a1 = map(range(1, 100000), '{}')
  let s:hoge.a2 = map(range(1, 100000), '{}')
  let s:hoge.a3 = map(range(1, 100000), '{}')
  let s:hoge.fuga = s:fuga
  let s:fuga.hoge = s:hoge
endfunction " }}}

function! Release() abort " {{{
  let s:arr = s:hoge.a2
  unlet s:hoge
  unlet s:fuga
endfunction " }}}

let start = reltime()
call Prepare()
call Release()
call garbagecollect()
echomsg string(reltimestr(reltime(start)))

上記スクリプトで測定したかったのですが、私の環境ではパッチなし状態ではスクリプト実行後にフリーズするので測定が不能です。パッチを当てると0.2598sで処理が終わります。
こういう情報でもよいでしょうか。

[h-east]

@Shougo 👍
range(1, 100000)の数値を減らしてpatch前の時間も計測出来るようにしてpatch前後で処理時間比較を提示するとbetterだと思いました。(in my opinion)

[ujihisa]

👍

[Shougo]

let s:hoge = {}
let s:fuga = {}
let s:arr = []

function! Prepare() abort " {{{
  let s:hoge.a1 = map(range(1, 50000), '{}')
  let s:hoge.a2 = map(range(1, 50000), '{}')
  let s:hoge.a3 = map(range(1, 50000), '{}')
  let s:hoge.fuga = s:fuga
  let s:fuga.hoge = s:hoge
endfunction " }}}

function! Release() abort " {{{
  let s:arr = s:hoge.a2
  unlet s:hoge
  unlet s:fuga
endfunction " }}}

let start = reltime()
call Prepare()
call Release()
call garbagecollect()
echomsg string(reltimestr(reltime(start)))

上記スクリプトで、
パッチなし： 100 秒
パッチあり： 0.133967 秒

備考：なぜか GC はスクリプトの実行後に発動するのでパッチ無し状態はストップウォッチにて測定しています。

[mattn]

👍

[todesking]

お忙しい様なら送信代行(お名前は存じております)出来ますがどうしましょうか？

申し訳ございません、お願いします

[mattn]

申し訳ございません、お願いします

LGTM

[mattn]

https://groups.google.com/forum/#!topic/vim_dev/DBYOdHQWvqY

[Shougo]

👍

[mattn]

This looks too simple. There is a remark that the next dict may have
been freed, I think that was there for a good reason (dict containing a
dict). On the other hand, the comment just a few lines up suggests that
this is not possible. I wonder which one of the two comments is
outdated...

It's possible to pass dd_next to dict_free() (or use an ugly global
variable) and set it to NULL if it gets freed.

こう言われてますが、何か反論のある方はいますか？

[koron]

現在の1つ解放するたびに先頭からやりなおすのは明らかにやり過ぎ。
かといえ指摘されているように、パッチのまったくやり直さないってのも問題。
たぶん辞書の作成順序と格納関係を逆にするとリークするか、
まったく速くならないことが考えられる。

解決策なんですが、こんな風に折衷案にするのはどうでしょう。

1. 先頭から順番に、解放されるべきかチェックする。
2. 解法されるべきオブジェクトが見つかったら、実際に解放し、「解放したフラグ」を立てる。
3. 末尾までチェックし終わったら、「解放したフラグ」をチェックし、立っていなければGC終了。
4. 立っていたらフラグを寝かせて 1 からやり直し。

[todesking]

This looks too simple. There is a remark that the next dict may have been freed, I think that was there for a good reason (dict containing a dict). On the other hand, the comment just a few lines up suggests that this is not possible. I wonder which one of the two comments is outdated...

「コメントには"next dict may also have been freed"と書いてあるのでこのパッチだと不十分ではないか。しかしちょっと上のコメントには矛盾するようなこと(再帰的な開放は行わない)が書いてあってどっちが正しいんだろう。」という意見ですよね。

これはたぶん上のコメントが正しくて、現在はdictやlistの中身を再帰的に開放はしないのでこのままの処理でいいんじゃないかと思ってます。ソースを見る限りはそうなっているように見える。

[Shougo]

このパッチですが、現在どういうステータスなのでしょうか。
vim_dev に投げられているものの、todo リストには入っておらず長期間放置されているように見えます。
パッチが既に完成しているのなら、todo に入っていない理由をvim_dev 上で尋ねてみる必要があると思います。

[Shougo]

mattn さん対応有難うございます。

https://groups.google.com/d/msg/vim_dev/DBYOdHQWvqY/asNnl1fVBQgJ

[mattn]

7.4.615 https://groups.google.com/forum/#!topic/vim_dev/pXjj7rww5RY

@todesking ++

[ujihisa]

おおおおおおおおおおおおおおおおおおおおおおおおおおおおお

[rhysd]

🎉

[Shougo]

👍

[crazymaster]

👏

[todesking]

皆さんありがとうございました！！！

[koron]

👍
2015/02/04 13:58 "todesking" notifications@github.com:

皆さんありがとうございました！！！

—
Reply to this email directly or view it on GitHub
#608 (comment).

[ujihisa]

感極まってきました

[todashuta]

㊗️