Haskell compiling with -O2 drastically increases memory usage

Question

This simple program runs in constant memory space when compiled with no flags with ghc:

import Data.List
f x = x*x
g a = foldl' (+) (f a) [1..(1073741824-1)]
main = do putStrLn $ show $ foldl' (+) 0 $ map g [0,1]

When compiled with ghc -O2 the memory usage exceeds the system resources (8GB).

Changing main to:

main = do putStrLn $ show $ foldl' (+) 0 [g 0, g 1]

alleviates the problem so it appears to be something to do with the map.

Can anyone explain the behaviour and perhaps how to work around it?

GHC version is: Glasgow Haskell Compiler, Version 7.4.1, stage 2 booted by GHC version 7.4.1

I suggest you file a bug report for this, since GHC -O2 is not supposed to degrade performance like this, I think... — Dominique Devriese, Oct 12 '14 at 05:50

score 11 · Accepted Answer · answered Oct 12 '14 at 05:55

11

This is the full laziness "optimization" biting you. When it works right, it can provide an asymptotic improvement in run time. When it works wrong... This happens.

The full laziness transform moves constants out of bindings to the enclosing scope. In this case, it's picking up on the [1..(1073741824-1)] constant, and moving it to the enclosing scope. However, that's.. completely wrong. It causes it to be shared between the two calls, meaning that it can't stream efficiently the first time.

There is no reliable way to defeat the full laziness transformation, except for compiling without -O2.

answered Oct 12 '14 at 05:55

Carl

26,500
4
65
86

12

You could compile with `-O2 -fno-full-laziness`. – David Young Oct 12 '14 at 05:59
1

David is correct and -fno-full-laziness fixed the problem. Thanks to Carl for the explanation. – lenguador Oct 12 '14 at 10:51

Random Dev · Answer 2 · 2014-10-12T06:42:21.947

3

The reason was explained by Carl really good and I don't think I can help you there any more.

But I can show you how to work around this.

First your g really just does sum up to 1073741823 and add f a.

There is a simple formula to sum up the numbers from 1 to n without that many additions (Gauss is said to have found it in primary-school):

sumUp :: (Integral a) => a -> a
sumUp n = n * (n+1) `div` 2

with this you can write

f x = x*x
g a = sumUp (1073741824-1) + f a
main = do putStrLn $ show $ foldl' (+) 0 $ map g [0,1]

remarks

You can hava a look at the link to see intuitively why this holds or try to find the proof yourself - it's really easy using induction :D

edited Oct 12 '14 at 06:42

answered Oct 12 '14 at 06:36

Random Dev

51,810
9
92
119

1

I know this is old, but a comment for the author: OP's example was almost certainly reduced from a much more complex problem in a real program. He was giving a simple example that exhibits a complex problem involving the runtime and compiler. Showing him a different way to solve that toy problem doesn't help. – James Koppel Sep 28 '17 at 00:32

Haskell compiling with -O2 drastically increases memory usage

2 Answers2

remarks

Linked