conservative optimizations
Alexei Kitaev
kitaev at iqi.caltech.edu
Fri Nov 27 01:59:26 EST 2009
Dear GHC team,
I have observed a space leak in a simple program compiled with -O
option. The problem is to compute the "Fibonacci rabbit sequence":
[1,0,1,1,0,1,0,1,1,0,1,1,0,...] see e.g., this Haskell Cafe discussion:
http://www.haskell.org/pipermail/haskell-cafe/2007-November/034236.html
I like this problem because I studied the spectrum of the Schrodinger
operator defined by this sequence a while ago. Anyway, here are two
slightly different programs that compute the rabbit sequence:
-- Version 1: O(n) time, O(n) space
rs :: [Int]
rs = 1: tail [x | r <- rs, x <- f r]
where
f 0 = [1]
f 1 = [1,0]
main :: IO ()
main = print $ take 100 rs
-- Version 2: O(n) time, O(log n) space
rs :: () -> [Int]
rs () = 1: tail [x | r <- rs(), x <- f r]
where
f 0 = [1]
f 1 = [1,0]
-- test of memory usage
main :: IO ()
main = print $ rs() !! (10^8)
When the second program is compiled with -O flag (using GHC-6.10.4 or
the latest version, 6.13.20091125), it eats up a lot of memory. After
some web searching and experimentation, I found that the space leak can
be fixed by compiling with -fno-full-laziness and inserting
{-# NOINLINE rs #-}
However, I still have a few of questions:
1) Why would inlining introduce a space leak? This looks like a compiler
bug to me.
2) Is there a set of "safe" or, if this is a better word, "conservative"
optimizations that never increase the running time or space usage more
than by a constant factor? This leads to another question: relative to
what? I understand that prescribing the exact evaluation order and other
details would be impractical, but is it possible to define *some*
aspects of the program behavior that would allow the programmer to
guarantee the correct asymptotic efficiency?
Thank you,
Alexei Kitaev
More information about the Glasgow-haskell-users
mailing list