続:Haskellのfibが遅い件

{白,黒}のカピバラの左随伴右随伴 @ainsophyao

@nishio 便利です。set log x はプロットのコマンドだったと思うので、fit は変わりましたっけ。僕は別ファイル作りましたが、using (log ($1)):(log ($2)) がいけたかと。(すいません、今サーバーが落ちていて試せないんです。) @shinh

shinichiro hamaji @shinh

@kinaba あれうーんとそれつまり 1 回の allocation に対して N 回 GC が動くってことですか？それが何故妥当なのかわからないです。あと concurrent なんかなーと思ったのはgdbのstacktraceに実行してるプログラムが入ってなかったからです。

shinichiro hamaji @shinh

@kinaba えーとつまりconcurrentっていうか、allocationのタイミングでメモリ足りないからGC呼ぶ実装なら bt で fib のスタックが見えるはずかなぁと思って、それが無いからallocationのタイミングとは別のタイミングでGC走らせてるのかなぁと

shinichiro hamaji @shinh

でその仮定が正しいのなら頻度 O(1/N) とかもそういうこともあるんかのうという気もします。妥当なのかはわかりませんが割と GC のイヤな allocation パターンになっちゃってるというような感じというか。あと Ruby の GC ってどのタイミングで起動するんだっけ…

kinaba @kinaba

@shinh ちゃいます。「N^2に比例する回数GCが動く」というのは「N^2回GCが動く」とは違います。

kinaba @kinaba

@shinh たとえば「サイズNのブロックをN回allocateする」というプログラムで、「100MBメモリをallocateするたびにGCが動く」状況だと、「1億/N 回allocateするたびにGCが動く」ので「GCの動く回数はN/(1億/N) = N^2/１億 回」です。

shinichiro hamaji @shinh

@kinaba あーなるほどつまり N が少ない時は 100 回中 1 回だった頻度が、 N が多くなったら毎回起動するようになった、みたいな話がありえるって話ですね。そうかなるほど…

kinaba @kinaba

@shinh はいはい。allocate回数Nに比例して一度に確保するメモリ量も増える変な状況じゃないとこうはならないと思いますけど、今回fibの場合は実際にNに比例してIntegerの桁数が伸びるので、そこまで大きく外してはいないんじゃないかなーと。

kinaba @kinaba

@shinh スタックはどうなるのか僕もよくわからんですね…。並列で動いてるんだろうか。この辺は @shelarcy さんならきっとご存じなような…(召還)

shinichiro hamaji @shinh

@kinaba なにか一通り納得できた気がします。というかそのくらい想像できるべきでつまり僕は手動かさずに机上で考えるとダメだな。あとは Java は何故このヘンな allocation pattern に負けてないか、とかですかねー

shinichiro hamaji @shinh

なんか今回面白いなと思ったのは GC とかって不自然にシンプルなコードに対して不可思議な挙動することがあるんだなぁということで、これはつまりマイクロベンチでの調整がしにくいということで、そのへんで GC の奥の深さみたいなのが生成されてるのかなーと

shinichiro hamaji @shinh

あと2変数で fit すると多少ヘンな関数でもそれっぽい曲線になってくれちゃうから、 0.001*N^3 + N^2 みたいなのが N^2.5 に見えたりするから気をつけよーね、ということも学んだ