続:Haskellのfibが遅い件

chunjp @chunjp

@tanakh ヒント： http://d.hatena.ne.jp/camlspotter/20100128/1264678903 [要出典]

Hideyuki Tanaka @tanakh

@chunjp な、なるほど・・・

Hideyuki Tanaka @tanakh

@camlspotter まあ私も言われるまで気付かなかったクチです

kinaba @kinaba

ものすごい長いサンクの連鎖を評価している最中は全部のサンクがスタックに乗った感じになるので、実はスタックの上の人たちは世代とか関係なく全部なめてしまうので、そういう時に限りやたらGCに時間がかかるのではなかろうか！！！という閃きを得た。検証せず寝る #haskell_fib

kinaba @kinaba

#haskell_fib やっぱりスタックは全スキャンしてる (rts/sm/GC.c→rts/Capabitiliy.c:markSomeCapabilities→...→rts/sm/Scav.c:scavangeTSO, scavenge_stack)

kinaba @kinaba

#haskell_fib +RTS -AxxxK でマイナGCヒープのサイズをどう変えても、前半(スタック短)と後半(スタック長)で１回辺りのマイナGC時間の"差"がほぼ一定で、この差は入力Nに対しO(N)。後半のみ、マイナGCでも全生存オブジェクト数に比例する時間がかかってる。

Ikegami Daisuke @ikegami__

ghc で作るプログラムは、メモリオプションが複数。「トレードオフすれ」、これを『Haskell は』というのはアレだと思います : http://haskell.org/ghc/docs/6.12.1/html/users_guide/runtime-control.html

Ikegami Daisuke @ikegami__

6.12.3 が stable release なのに、6.12.1 のドキュメントをうっかり貼ってしまった

kinaba @kinaba

#ghc_fib マイナGCは連続allocationが起きてると一定間隔(デフォルトでは512KB毎)で動くので、つまり後半ではN/512K回動くので、１回当たりO(N)時間かかるなら合計ではO(N^2)時間かかっている（ただし1/512Kという小さい係数）という状況

kinaba @kinaba

#ghc_fib というわけで、fib::[Int] = 1:1:zipWith fib (tail fib) にかかる時間がO(N)になってない挙動は http://bit.ly/9S44AQ （に加えて http://bit.ly/dy2MsG ) で説明がつくと思う。

kinaba @kinaba

#ghc_fib なんだか話を聞いた瞬間0.01秒でまずそれを考えろ俺という感じの説明だった。 / fib::[Integer] の場合は遅くなる現象は手元で再現できてないのでわからない。32bitsと64bitsで違ったりとかだろうか…

NISHIO Hirokazu @nishio

@kinaba とりあえず僕は64bit。光成さんにも聞いておくー

NISHIO Hirokazu @nishio

@kinaba 64bit環境で7::Integerをn回掛けるコードがO(n ^ 2.7)みたい

kinaba @kinaba

@nishio こちらは32bitです。hmm

NISHIO Hirokazu @nishio

@kinaba 残念ながら光成さんは32bitだったのでそこの違いではなさそうです…

kinaba @kinaba

あれ？ちょま、再現した #ghc_fib

kinaba @kinaba

@nishio ひーすみませんもう一度実験やりなおしてみたらこっちの32bit機でも遅くなりました。http://twitter.com/kinaba/status/16819284827 この時は 6.10.1 で、今 6.12.3 なのでその差だろうか…orz

NISHIO Hirokazu @nishio

ついでにカピバラさんのデータを「300000からわずかにO(n ^ 2)を外れる」と書いているからその手前まででフィッティングしたらO(n ^ 2.4)だった件

kinaba @kinaba

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

shelarcy（しぇらーしぃ） @shelarcy

fib の話ですが、とりあえず、GHC が現在対応している最適化レベルは -O2 までですよ [http://bit.ly/bE1to8 ]、あと正格性解析が有効になるのは -O オプションからです [http://bit.ly/cXdkyQ ] 、とだけ。 #ghc_fib

shelarcy（しぇらーしぃ） @shelarcy

GHCi で sum が……というのは、正格性解析が有効になっていないからです。

NISHIO Hirokazu @nishio

@kinaba 6.10.2でそれが入ったということなら、僕の環境は6.10.4だったのでありえます RT http://hackage.haskell.org/trac/ghc/ticket/2747

kinaba @kinaba

@nishio 手元に6.10.1と6.10.2をインストールし直して試してみたところ6.10.2は以降のバージョンと変わらない動きをするので、このfixが理由かどうかはともかく、6.10.1→6.10.2 が境界なのは確かなようです。

kinaba @kinaba

@nishio Integerのfibも7**nも、+RTS -sしてみるとGCの回数が線形では抑えられない感じに増えてますね（細かい率は調べてませんが…）。マイナGCヒープをすぐ埋め尽くすような巨大オブジェクトが大量に生成される状態はプログラマが注意せよ、ってことじゃないかなあ

kinaba @kinaba

#ghc_fib は「スタックが凄く深い所で大量にアロケーション＆GCすると大変」の一言でマトメたい気分。@nishio さんのpow http://bit.ly/abRZR4 も末尾再帰ならGCの回数は変わらないけど実行時間は段違い。他の言語についてはshinhさん頼みである。