fib = 1 : 1 : zipWith (+) fib (tail fib) が遅いかどうかは、使い方に依存する
Haskellでフィボナッチ数を計算するコードとして、次のものが有名だ。
fib :: [Integer] fib = 1 : 1 : zipWith (+) fib (tail fib)
これのn番目の要素を取得するコードがO(n^2)よりも遅いということを指摘した記事があった。
実はこの現象は、リストfibを先頭から順番に使っていった場合には起こらない。(!!)などでリストの途中の要素を取得して、その値をいきなり評価した場合に発生する。以下が実証用コード。
{-# OPTIONS_GHC -O3 #-} import System.Environment(getArgs) -- 最初のfib fib :: [Integer] fib = 1:1:zipWith (+) fib (tail fib) -- 明示的な末尾再帰によるfib fib_rec :: Int -> Integer fib_rec = loop 1 0 where loop a b 0 = a loop a b n = loop (a+b) a (n-1) -- (!!)と同じだが、head側も評価する (!!!) :: [a] -> Int -> a [] !!! _ = error "(!!!): index out of bounds" (x:xs) !!! n = case n of 0 -> x _ -> seq x $ xs !!! (n-1) -- tailを取ろうとすると自動的にheadも評価するように変換 force :: [a] -> [a] force = foldr (\x y -> seq x (x : y)) [] main = do [mode, sn] <- getArgs let n = read sn print $ (*0) $ case mode of "index" -> fib !! n "sum" -> sum $ take n fib "rec" -> fib_rec n "!!!" -> fib !!! n "forced" -> force fib !! n
実行結果。なおGHC 6.10.4を使っている。
$ time ./test rec 300000 # まず基準として末尾再帰版 0 real 0m1.188s user 0m1.180s sys 0m0.005s $ time ./test index 300000 # 300000番目の要素を!!で取得して表示 0 real 0m15.702s user 0m15.625s sys 0m0.034s $ time ./test sum 300000 # 最初の300000個の要素の合計 0 real 0m2.404s user 0m2.391s sys 0m0.005s
sum (take 300000 fib)の方が、単にfib !! 300000を計算するよりずっと速い。この違いは、sumがリストの要素を前から順番に評価していく*1のに対し、(!!)はそれをしないことによる。
fibの第300000要素だけが欲しい場合でも、fibを前から順番に評価するように工夫することはできる。
$ time ./test '!!!' 300000 # head側も評価するような(!!)もどきを使う 0 real 0m1.203s user 0m1.193s sys 0m0.006s $ time ./test forced 300000 # force関数を間に入れて(!!)を使う 0 real 0m1.206s user 0m1.202s sys 0m0.001s
このことから分かるように、「正しい」順番でアクセスすれば、fibは末尾再帰版に大きく劣らない性能を発揮する。だから、「let fib = 1 : 1 : zipWith (+) fib (tail fib) in fibは遅い」と一概に言うことはできない。
なぜ遅いか
(!!)を直接使ったコードでは、入力nに対してO(n)のスタック領域を使う。また、以下に示すように実行時間の大部分をGCが占めていることから、大きなスタック領域を繰り返し走査するオーバーヘッドが大きいのではないかと思う。
$ ./test index 300000 +RTS -s
./test index 300000 +RTS -s
0
4,574,137,936 bytes allocated in the heap
1,498,628,016 bytes copied during GC
16,718,640 bytes maximum residency (828 sample(s))
8,406,576 bytes maximum slop
48 MB total memory in use (0 MB lost due to fragmentation)
Generation 0: 7650 collections, 0 parallel, 11.93s, 11.96s elapsed
Generation 1: 828 collections, 0 parallel, 2.46s, 2.47s elapsed
INIT time 0.00s ( 0.00s elapsed)
MUT time 1.28s ( 1.33s elapsed)
GC time 14.39s ( 14.43s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 15.67s ( 15.76s elapsed)
%GC time 91.8% (91.5% elapsed)
Alloc rate 3,565,714,618 bytes per MUT second
Productivity 8.2% of total user, 8.1% of total elapsed
$ ./test forced 300000 +RTS -s
./test forced 300000 +RTS -s
0
4,571,729,384 bytes allocated in the heap
2,137,792 bytes copied during GC
19,072 bytes maximum residency (1 sample(s))
22,224 bytes maximum slop
2 MB total memory in use (0 MB lost due to fragmentation)
Generation 0: 8428 collections, 0 parallel, 0.05s, 0.06s elapsed
Generation 1: 1 collections, 0 parallel, 0.00s, 0.00s elapsed
INIT time 0.00s ( 0.00s elapsed)
MUT time 1.16s ( 1.16s elapsed)
GC time 0.05s ( 0.06s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 1.21s ( 1.22s elapsed)
%GC time 4.4% (4.6% elapsed)
Alloc rate 3,951,955,983 bytes per MUT second
Productivity 95.6% of total user, 94.8% of total elapsedこれと同種の問題はiterateやscanlにもある。iterateやscanlを使って生成したリストも、fibと同様に先頭から順に評価していかないとスタックを必要以上に使うことになる場合がある。
関数fをxにn回適用した値を計算するのに
iterate f x !! n
と書くというイディオムのようなものがあるが、nが大きく、なおかつfが正格な場合はオーバーヘッドが無視できない。
余談
上の実証コードも元記事のコードも、見えにくい形でGHCの最適化能力に依存していて、これを見逃すと嫌な誤解のもとになるのではないかと思う。
第一に、fibがGCに回収されることを期待している。普通、トップレベルで定義したオブジェクトはGCに回収されないはずだが、この例では回収される(なんでだろう)。GHCはトップレベルオブジェクトを普通に回収するらしい。mainの最後にprint $ fib!!3などと付け加えると回収が阻害され、振る舞いが大きく変わる。例えばn=300000では、fibの先頭三十万要素を全部メモリに保持しようとするので、indexモードだろうがforcedモードだろうがメモリ不足に陥る。これはHaskellの特性というより、大きな整数からなる大きなリストをグローバルに持つとメモリを圧迫する、というだけの話。
第二に、末尾再帰によるフィボナッチ数の計算で、再帰関数の正格性が推論されることに頼っている。上のfib_recの定義を再掲する。
fib_rec :: int -> integer fib_rec = loop 1 0 where loop a b 0 = a loop a b n = loop (a+b) a (n-1)
このコードは、loopが第一引数について正格であって、かつそれをghc -O3が理解してくれることに依存している。例えば次のように書き換えるだけで、loopがaについて正格でなくなるので破綻する。
fib_rec :: int -> integer fib_rec = loop 1 1 where loop a b 0 = b loop a b n = loop (a+b) a (n-1)
正格性を明示すればこの問題はなくなる。びっくりパターンを使うなら、
loop !a !b 0 = a loop a b n = loop (a+b) a (n-1)
Haskell 98では、
loop a b n | a `seq` b `seq` n `seq` False = undefined loop a b 0 = a loop a b n = loop (a+b) a (n-1)
