Opened 8 years ago

Closed 8 years ago

Last modified 12 months ago

#4276 closed bug (duplicate)

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

Reported by: guest Owned by: igloo
Priority: normal Milestone: 7.4.1
Component: Compiler Version: 6.12.1
Keywords: optimization space leak, FloatOut Cc: omarab@…, daniel.is.fischer@…
Operating System: Windows Architecture: x86
Type of failure: Runtime performance bug Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

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.

Attachments (1)

test.hs (547 bytes) - added by guest 8 years ago.

Download all attachments as: .zip

Change History (6)

Changed 8 years ago by guest

Attachment: test.hs added

comment:1 Changed 8 years ago by igloo

Milestone: 7.2.1

Great testcase, thanks!

comment:2 Changed 8 years ago by daniel.is.fischer

Cc: daniel.is.fischer@… added

comment:3 Changed 8 years ago by simonpj

Owner: set to igloo

Ian, might you investigate a bit, pls?

comment:4 Changed 8 years ago by igloo

Resolution: duplicate
Status: newclosed

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.

comment:5 Changed 12 months ago by simonpj

Keywords: FloatOut added
Note: See TracTickets for help on using tickets.