Haskellの「fib = 1:1:zipWith (+) fib (tail fib)」がとても遅い件のまとめ
前日話の流れを時系列でまとめかけたけど、もはや情報量が多すぎて流れを追っていなかった人にとってはキャッチアップが困難かと思うので改めてまとめてみる。(情報量の多いほうがいい人はこちら: 続:Haskellのfibが遅い件)
fib = 1:1:zipWith (+) fib (tail fib)
が有名であり、Wikipediaには「次の定義は線形時間でフィボナッチ数列のリストを生成する」と紹介されている。しかし、少なくとも n = 10000 〜 300000 くらいの範囲ではO(n^2.6)くらいの計算時間が掛かっていて、事実に反する。 (グラフはこちら: はじめてのにき(2010-07-19))
2.6という値がどこから出てきたのか?これはGCにO(n^3)くらいの時間がかかっていて、それが小さい係数で本来の計算時間O(n^2)に混ざっているため、O(n^2.6)ぐらいに見えている。
なぜGCにO(n^3)ぐらいの時間がかかるのか?HaskellのGCは世代別GCであり、固定長のマイナーヒープがいっぱいになるとGCを始める。このとき、スタック上のオブジェクトはGCのルートとして使われるのでスタックの深さをmとしたときにO(m)の時間がかかる。今回のケースでは、スタックの深さをmとした場合にO(m)のメモリを確保するので、i回目のGCが起きたときの消費時間mは係数無視してi^0.5になり、これをiについて足しあわせるので積分してi^1.5になり、iがいくらまで増えるかというとメモリの消費量をマイナーヒープのサイズで割ったものだから係数無視してn^2なので、これを代入してn^3になる。というわけでGCの計算量はO(n^3)になる。
この挙動はGHC 6.10.1以前では再現しないので、6.10.2で行われたGCに関する修正(#2747 (Excessive Memory Usage: space leak with foldl' on Integer) – GHC)が原因と思われる。6.10.1ではnの2乗くらいのオーダーになるらしい。
また、「スタックの上に大量の巨大なIntegerがある状況」が問題を引き起こしているので、Haskellでも素朴に末尾再帰で書けばO(n^2)になる。計算順序によっても挙動が変わる(無限リストを使っているfibでは30万番目を取るより30万番目までの和を取るほうが速い)し、評価戦略でも変わる(正格評価するzipWith'を作れば速い)
無限リストが絡むことで見かけが複雑になっているので、よりシンプルな「末尾再帰でない再帰呼び出しでnに比例して大きくなるメモリを確保しようとしたときにO(n ^ 2.6)の時間がかかる」事例(Haskellで単にn回7を掛けるだけでもO(n ^ 2.6)の時間がかかる)を先に見たほうが分かりやすいのかも知れない
「Haskellが遅い」という主張にエアリーディングした人もいたようだが、あくまで「fib = 1:1:zipWith (+) fib (tail fib)が遅い(n = 100000ではPythonで素朴にループで書いたコードよりも!)」ということなので勘違いなさらないよう。実際最初のエントリーでも素朴な末尾再帰で書いて速くなってるわけだし。
こんな感じですかね。なんか間違っていたらご指摘よろしくお願いします。