Compiling with -O makes some expressions too lazy and causes space leaks

Here are some expressions that are executed in a too lazy way when optimisation is turned on in GHC. GHC is known to make some expressions too lazy when full laziness is turned on (as in #917), and indeed some of these expressions execute correctly when you add -fno-full-laziness. However, some of them are compiled too lazy even if -fno-full-laziness is present.

Here are terms that get compiled too lazy with -O only when full strictness is on:

seq (id (\a -> seq a (\b -> (undefined::Int))) (undefined::Bool))
\a -> seq (seq a (\b -> seq b null) (undefined::([] ([] Int)) -> [] Int)) (\b -> ([]::[] Int)) length
\a -> seq (id (\b -> seq b (\c -> seq)) (length a)) ([]::[] Int)

Here are terms which are compiled too lazy with -O regardless of full strictness:

seq (seq (odd (undefined::Int)) (\a -> (undefined::[] (Int -> Bool))))
foldr (\a -> seq) id ((:) True (undefined::[] Bool))
\a -> foldr (\b -> \c -> seq c (\d -> ([]::[] Int))) (undefined::Bool -> [] Int) a False
\a -> (\b -> map (seq b id) (seq b ([]::[] Int))) (seq a (\b -> (undefined::([] Bool))))
map (seq (seq (seq 0 (undefined::Bool)) (\a -> \b -> (undefined::Bool)) (undefined::Int)))
map (seq (seq (id (\a -> (undefined::Int)) ([]::[] Int)) (\a -> undefined::Bool)))
\a -> (\b -> (:) (seq b 2) (b (undefined::Int) 0)) (seq a (\b -> (undefined::Int -> [] Int)))

To discover the differences, just run the terms (whose types are [Int] -> [Int]) on some partially or fully-defined small lists.

It is possible to construct programs which exhibit space leaks only when optimisation is turned on using some of these terms (examples attached).

All programs have been tested with a pre-built GHC 7.1.20110606 on linux x86-64.

Is this a bug? Well, full laziness comes with a disclaimer that some expressions will get too lazy, but this happens even when we turn off full laziness, so it might be a legitimate bug.

Trac metadata

Trac field	Value
Version	7.1
Type	Bug
TypeOfFailure	IncorrectResultAtRuntime
Priority	normal
Resolution	Unresolved
Component	Compiler
Test case
Differential revisions
BlockedBy
Related
Blocking
CC
Operating system
Architecture

mentioned in issue #5129 (closed)

changed weight to 5

added Tbug Trac import incorrect runtime result labels

Attached file NoFullLazinessLeak.hs ($598).

Program that has a space leak when compiled with -O and -fno-full-laziness.

Attached file FullLazinessLeak.hs ($599).

Program that has a space leak when compiled with -O. Space leak goes away when full laziness is turned off.

Trac metadata

Trac field	Value
CC	→ michal.palka@poczta.fm

changed milestone to %7.4.1

assigned to @simonmar

I'm looking at #5129 (closed), and we think the same mechanism can be used to fix seq, so assigning this to me.

mentioned in commit be544179

unassigned @simonmar

unassigning me, on second thoughts I'm not sure we want to change seq to use seq#.

changed milestone to %7.6.1

changed weight to 3

Trac metadata

Trac field	Value
Priority	normal → low

changed milestone to %7.6.2

mentioned in issue #8457

changed milestone to %7.10.1

Moving to 7.10.1.

removed milestone

Moving to 7.12.1 milestone; if you feel this is an error and should be addressed sooner, please move it back to the 7.10.1 milestone.

changed milestone to %8.0.1

Milestone renamed

Trac metadata

Trac field	Value
TypeOfFailure	IncorrectResultAtRuntime → RuntimePerformance

added Plow label

I have translated as follows:

module T5262 where

import Prelude hiding (length, null, foldr)
import qualified Prelude

length :: [a] -> Int
length = Prelude.length

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr = Prelude.foldr

null :: [a] -> Bool
null = Prelude.null

e1 = id (\a -> a `seq` (\b -> (undefined::Int))) `seq` undefined::Bool
e2 = \a -> seq (seq a (\b -> seq b null) (undefined::([] ([] Int)) -> [] Int)) (\b -> ([]::[] Int)) length
e3 = \a -> seq (id (\b -> seq b (\c -> seq)) (length a)) ([]::[] Int)


s1 = ((odd (undefined::Int) `seq` (\a -> (undefined::[] (Int -> Bool)))) `seq`)
s2 = foldr (\a -> seq) id ((:) True (undefined::[] Bool))
s3 = \a -> foldr (\b -> \c -> seq c (\d -> ([]::[] Int))) (undefined::Bool -> [] Int) a False
s4 = \a -> (\b -> map (seq b id) (seq b ([]::[] Int))) (seq a (\b -> (undefined::([] Bool))))
s5 = map (seq (seq (seq 0 (undefined::Bool)) (\a -> \b -> (undefined::Bool)) (undefined::Int)))
s6 = map (seq (seq (id (\a -> (undefined::Int)) ([]::[] Int)) (\a -> undefined::Bool)))
s7 = \a -> (\b -> (:) (seq b 2) (b (undefined::Int) 0)) (seq a (\b -> (undefined::Int -> [] Int)))

To discover the differences, just run the terms (whose types are [Int] -> [Int]) on some partially or fully-defined small lists.

And looked at the Core output of e1, e2, s1, s2 and s3. I couldn't find anything suspicious. I'm inclined to close this issue as it's likely fixed. Otherwise we should perhaps mark it as info needed as it's a bit tedious to decipher what is actually wrong here.

added demand analysis float-out labels

added info needed label