-O0 runs in constant space, -O1 and -O2 don't

[guest]

Enabling optimization changes the space complexity of this small program, which seems like a bug. Run the attached program with command line argument equal to 22 or greater.

Description of the program: given a real valued function f, compute the sum f(x_i) over an increasingly finer and finer mesh of sample points. If the new mesh shares points with the old mesh this can be computed somewhat more efficiently by reusing the previous sum.

Looking at the Time and Allocation report, it seems like the optimized versions of the program are actually computing the sum 2 ** n times instead of n times. This is probably related to what is causing the space behavior.

[igloo]

Great testcase, thanks!

[simonpj]

Ian, might you investigate a bit, pls?

[igloo]

This looks like another full-laziness issue, with [0..] being shared. If you compile with -O1 -fno-full-laziness then space usage matches -O0.

Here's a smaller program:

module Main (main) where

import Data.List

sum' :: [Double] -> Double
sum' xs = foldl' (+) 0 xs

go :: Double -> [Double]
go w = sum' xs : go (w / 2) 
    where xs = takeWhile (<= 23) [k*w | k <- [0..]]

main :: IO ()
main = mapM_ print $ take 20 $ go 22

Closing as a duplicate of #917.