https://twitter.com/kinaba のログ (twilog の方が便利です。)
| 『俳句 - 四合目からの出発』 http://www.amazon.co.jp/dp/4061586319 という本を読んでました。初心者の句15万句を集めてダメな部分を分類してまとめたので、読者諸君はこの罠はさっさと全部切り抜けて先へ向かいたまえ、という、なにか異彩を放つ一冊。 | |
| 内容の善し悪しを判断できるほど僕は俳句に明るくないのですが、それでもわかるのは、とにかく論旨が異様に明確。何をやってはいけないか、俳句とは何をどういう言葉で詠う文学であるのか、とても判断しやすい言葉で書かれている。すごい。小学校の国語の時間とかもこうやって教えればいいのにね。 | |
| ものすごい長いサンクの連鎖を評価している最中は全部のサンクがスタックに乗った感じになるので、実はスタックの上の人たちは世代とか関係なく全部なめてしまうので、そういう時に限りやたらGCに時間がかかるのではなかろうか！！！という閃きを得た。検証せず寝る #haskell_fib | |
| #haskell_fib やっぱりスタックは全スキャンしてる (rts/sm/GC.c→rts/Capabitiliy.c:markSomeCapabilities→...→rts/sm/Scav.c:scavangeTSO, scavenge_stack) | |
| #haskell_fib +RTS -AxxxK でマイナGCヒープのサイズをどう変えても、前半(スタック短)と後半(スタック長)で１回辺りのマイナGC時間の"差"がほぼ一定で、この差は入力Nに対しO(N)。後半のみ、マイナGCでも全生存オブジェクト数に比例する時間がかかってる。 | |
| #ghc_fib マイナGCは連続allocationが起きてると一定間隔(デフォルトでは512KB毎)で動くので、つまり後半ではN/512K回動くので、１回当たりO(N)時間かかるなら合計ではO(N^2)時間かかっている（ただし1/512Kという小さい係数）という状況 | |
| #ghc_fib というわけで、fib::[Int] = 1:1:zipWith fib (tail fib) にかかる時間がO(N)になってない挙動は http://twitter.com/kinaba/status/19012642038 （に加えて http://shinh.skr.jp/m/?date=20100721#p01 ) で説明がつくと思う。 | |
| #ghc_fib なんだか話を聞いた瞬間0.01秒でまずそれを考えろ俺という感じの説明だった。 / fib::[Integer] の場合は遅くなる現象は手元で再現できてないのでわからない。32bitsと64bitsで違ったりとかだろうか… | |
| @ysks この辺 http://shinh.skr.jp/m/?date=20100706#p01 C++のアロケータインターフェイスの都合 | |
| @esumii @yoriyuki 単純型付きだと http://portal.acm.org/citation.cfm?id=864416 こういう話がありますね。（中身は精読していないので、どこまで信頼に足る論文かは不明です。） | |
| @nishio こちらは32bitです。hmm | |
| あれ？ちょま、再現した #ghc_fib | |
| @nishio ひーすみませんもう一度実験やりなおしてみたらこっちの32bit機でも遅くなりました。http://twitter.com/kinaba/status/16819284827 この時は 6.10.1 で、今 6.12.3 なのでその差だろうか…orz | |
| 6.10.1との差は多分これだなー http://hackage.haskell.org/trac/ghc/ticket/2747 …so a program that allocates all or mostly large objects can use… #ghc_fib | |
| @nishio 手元に6.10.1と6.10.2をインストールし直して試してみたところ6.10.2は以降のバージョンと変わらない動きをするので、このfixが理由かどうかはともかく、6.10.1→6.10.2 が境界なのは確かなようです。 | |
| @nishio Integerのfibも7**nも、+RTS -sしてみるとGCの回数が線形では抑えられない感じに増えてますね（細かい率は調べてませんが…）。マイナGCヒープをすぐ埋め尽くすような巨大オブジェクトが大量に生成される状態はプログラマが注意せよ、ってことじゃないかなあ | |
| PythonやRubyでもGCの動きのログを取るようなオプションってあるのかな。気になってきた | |
| @finalfusion たとえばHaskellのghcだと http://www.kmonos.net/wlog/sub/fibrep.txt こんな感じに、GCの開始/終了時刻とそのとき生き延びたバイト数とかが取れるんですが、こんな雰囲気で | |
| これか module GC::Profiler http://doc.okkez.net/static/191/class/GC=3a=3aProfiler.html | |
| #ghc_fib は「スタックが凄く深い所で大量にアロケーション＆GCすると大変」の一言でマトメたい気分。@nishio さんのpow http://d.hatena.ne.jp/nishiohirokazu/20100721/1279687613 も末尾再帰ならGCの回数は変わらないけど実行時間は段違い。他の言語についてはshinhさん頼みである。 | |
| @mametter @finalfusion やーありがとうございます。こういうのがサクッと出せるのは便利でよいですね | |
| ところで僕が @mametter さんと @mattenner さんを見間違えた回数と @nishio さんと @nushio さんを見間違えた回数のログを取って比較するようなオプションが欲しい | |
| 回数のログを取るというのは記録を取るという意味であって、指数関数的な回数見間違えているためその対数をとって比較したいという意味ではない | |
| Pythonは http://docs.python.org/release/3.1/library/gc.html か…と思ったけどそれ以前に、Pythonは基本的には参照カウントだっけ。今回の例くらいならGCの出番はないな。 | |
| @shinh GC、O(N^2)…まで行くかは調べてませんがO(N)回よりは大きいオーダで走ってます (+RTS -s 調べ) http://twitter.com/kinaba/statuses/19061276519 なのでこれと掛ければO(N^2.6)に見えてもアリかなーと | |
| @shinh GCがそれだけ頻繁に走る理由は説明できてませんが、メモリの述べアロケート量は遅延評価でも結局O(N^2)なので、マイナーGC（ヒープサイズが定数512K）でこれらに全部一度は触れるとなるとN^2/512K 回くらい走って不思議はないかなーという気もしなくもないです | |
| @shinh はい、具体的にどのタイミングでGCが起きてるのかはよーわかりませんが、なんかそのへんのどれかだと思います | |
| 日本の古来伝統のAAEとかのオートトレーサーと比べてどんなもんなんだろ ＞ Structure-based ASCII art http://portal.acm.org/citation.cfm?doid=1833349.1778789 (via http://twitter.com/Cryolite/statuses/19076387723 ) | |
| @shinh いや、allocation回数がO(N)で、GC頻度が「O(1/N)回のallocationにつき１回」だったら、自然に、GC回数のはO(N^2)になります。今回の場合1回でアロケートされるメモリのサイズがO(N)なので、GC頻度がO(1/N)というのはわりと妥当げ | |
| 今の説明でオーダー記法を使うのは（N→∞にすると話がおかしくなる話なので）非常によろしくないのだけどまあだいたいそんな感じで…。 | |
| @shinh concurrentにもできますけど特に何もオプションつけないで動かしたらシングルスレッドだった、はず… | |
| ランダウの記号はもっと注意深く使わねばならん http://d.hatena.ne.jp/nuc/20100716/p17 というのは本当まったくその通りなので反省する… | |
| @shinh 今 Ruby の GC::Profiler で fib 1万 から fib 10万 までGC回数しらべてみたところ 2,5,11,18,28,40,54,70,87,108 という直線にはのらなそうな増加具合だったので、Ruby でもGC回数の事情は同じかもです |