続:Haskellのfibが遅い件
-
- いいね！0
shelarcy（しぇらーしぃ）
@shelarcy
GHC 6.12.1 以降で Integer 型を使う場合、まずは ghc-pkg list integer-* コマンドなどで gmp を使った高速な実装（integer-gmp）になっているかどうか調べてみること!！ http://bit.ly/9mRWiF #ghc_fib
2010-07-21 19:34:57
shelarcy（しぇらーしぃ）
@shelarcy
今回は（6.10.x を使っているようなので）関係ないみたいですが、元々遅い実装（integer-simple）を使っている場合、Integer 型を使うと Int 型に比べて計算が遅くなって当然なので。 #ghc_fib
2010-07-21 19:40:01
shinichiro hamaji
@shinh
@kinaba 全スタックをなめてるってのはどうも理由を説明できてないような気がするんですがどんなもんなんでしょう。というのはスタックのサイズは O(N) なので、これをなめる GC を N 回走らせてもせいぜい O(N^2) だにゃーという。
2010-07-21 23:02:31
shinichiro hamaji
@shinh
@kinaba インクリメンタル GC がやりなおしになっちゃって O(N) の空間なめるのに O(N) 以上かかっちゃってる！とかならわかるんですが、まぁなんかそいうもう一手が必要な気がするんですよね
2010-07-21 23:03:23
kinaba
@kinaba
@shinh GC、O(N^2)…まで行くかは調べてませんがO(N)回よりは大きいオーダで走ってます (+RTS -s 調べ) http://twitter.com/kinaba/statuses/19061276519 なのでこれと掛ければO(N^2.6)に見えてもアリかなーと
2010-07-21 23:05:37
shinichiro hamaji
@shinh
@kinaba にゃるほど回数の方が O(N) 越えしちゃうんですね。つーことは多倍長整数の足し算の最中に複数回 allocation が起きてるか、リストなりなんなりの遅延のほげほげがおかしなことになってるってことですかね…
2010-07-21 23:09:21
kinaba
@kinaba
@shinh GCがそれだけ頻繁に走る理由は説明できてませんが、メモリの述べアロケート量は遅延評価でも結局O(N^2)なので、マイナーGC（ヒープサイズが定数512K）でこれらに全部一度は触れるとなるとN^2/512K 回くらい走って不思議はないかなーという気もしなくもないです
2010-07-21 23:11:47
Hideyuki Tanaka
@tanakh
GHCのGCは数KB以上のでかいオブジェクトは別管理されててリストになってたから、それがすごいたくさんあったら開放の際に領域の併合とかするためにO(N)で走らない…ような気がする。
2010-07-21 23:13:37
shinichiro hamaji
@shinh
@kinaba 普通に O(N^2) な問題なら不思議はないんですが、今回は fib なので普通に考えると allocation 回数は O(N) じゃね…って気がして、 Haskell に関してはなんかこれバグってないですかねえ…古いヤツなら速かったということですし
2010-07-21 23:21:50
{白,黒}のカピバラの左随伴右随伴
@ainsophyao
誤差は時間に比例なので log log にするか using 1:2:2 しないと駄目ですよ。RT @nishio ついでにカピバラさんのデータを「300000からわずかにO(n ^ 2)を外れる」と書いているからその手前まででフィッティングしたらO(n ^ 2.4)だった件
2010-07-21 23:24:09
shinichiro hamaji
@shinh
@kinaba ていうか今gdbで止めてみて気付いたんですが、なんかghcはconcurrent GCですかねコレ。それならGC回数がallocation回数より多いのは不思議じゃないかも。ただinfo threadsで1個しか出てこないのはこれ user thread なんかな
2010-07-21 23:26:50
Hideyuki Tanaka
@tanakh
ロボット組み込みLispですか。確かにそこはこだわりどころですね RT @nfunato: GHCじゃないけど、EusLispはこの辺にコダワリがあって、fibonacci buddy使ってましたね(少なくとも私の知る昔は) RT @tanakh...
2010-07-21 23:29:29
kinaba
@kinaba
@shinh いや、allocation回数がO(N)で、GC頻度が「O(1/N)回のallocationにつき１回」だったら、自然に、GC回数のはO(N^2)になります。今回の場合1回でアロケートされるメモリのサイズがO(N)なので、GC頻度がO(1/N)というのはわりと妥当げ
2010-07-21 23:33:25
Hideyuki Tanaka
@tanakh
なんか昔GHCのGCをリアルタイム化ってのをやってて、そのとき領域併合のコードが線形探索になってるのを見つけて、これだめじゃんということになった。結局汎用的ではない手法でアドホックに解決したけど、このへんの実装は最近の実装ではどうなってるのだろうか。
2010-07-21 23:33:32
kinaba
@kinaba
ランダウの記号はもっと注意深く使わねばならん http://d.hatena.ne.jp/nuc/20100716/p17 というのは本当まったくその通りなので反省する…
2010-07-21 23:39:55
NISHIO Hirokazu
@nishio
@ainsophyao なるほど、どうやって重み付けを変えるのかわからなかったのだけどそうするんですね＞using 1:2:2 or set log x set log y
2010-07-21 23:50:45
kinaba
@kinaba
@shinh 今 Ruby の GC::Profiler で fib 1万 から fib 10万 までGC回数しらべてみたところ 2,5,11,18,28,40,54,70,87,108 という直線にはのらなそうな増加具合だったので、Ruby でもGC回数の事情は同じかもです
2010-07-21 23:51:50
shelarcy（しぇらーしぃ）
@shelarcy
@tanakh 当該部分に対する変更かどうかは（ちゃんと見ていないので）分かりませんが、線形走査をしないようにしたという変更が幾つか入っていた気がしますね。例えば、これとか http://bit.ly/cmfFQS （patch へのリンクは死んでいますが……。）
2010-07-21 23:52:08