Opened 8 years ago

Last modified 4 years ago

#5262 new bug

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

Reported by: michal.palka Owned by:
Priority: low Milestone:
Component: Compiler Version: 7.1
Keywords: laziness, strictness, space leak Cc: michal.palka@…, dfeuer
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Runtime performance bug Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

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.

Attachments (2)

NoFullLazinessLeak.hs (1.0 KB) - added by michal.palka 8 years ago.
Program that has a space leak when compiled with -O and -fno-full-laziness.
FullLazinessLeak.hs (1010 bytes) - added by michal.palka 8 years ago.
Program that has a space leak when compiled with -O. Space leak goes away when full laziness is turned off.

Download all attachments as: .zip

Change History (14)

Changed 8 years ago by michal.palka

Attachment: NoFullLazinessLeak.hs added

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

Changed 8 years ago by michal.palka

Attachment: FullLazinessLeak.hs added

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

comment:1 Changed 8 years ago by michal.palka

Cc: michal.palka@… added

comment:2 Changed 8 years ago by simonmar

Milestone: 7.4.1
Owner: set to simonmar

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

comment:3 Changed 8 years ago by marlowsd@…

commit be5441799b7d94646dcd4bfea15407883537eaaa
Author: Simon Marlow <marlowsd@gmail.com>
Date:   Mon Jun 27 16:45:15 2011 +0100

    Add two new primops:
    
      seq#   :: a -> State# s -> (# State# s, a #)
      spark# :: a -> State# s -> (# State# s, a #)
    
    seq# is a version of seq that can be used in a State#-passing
    context.  We will use it to implement Control.Exception.evaluate and
    thus fix #5129.  Also we have plans to use it to fix #5262.
    
    spark# is to seq# as par is to pseq.  That is, it creates a spark in a
    State#-passing context.  We will use spark# and seq# to implement rpar
    and rseq respectively in an improved implementation of the Eval monad.

comment:4 Changed 8 years ago by simonmar

Owner: simonmar deleted

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

comment:5 Changed 8 years ago by igloo

Milestone: 7.4.17.6.1
Priority: normallow

comment:6 Changed 7 years ago by igloo

Milestone: 7.6.17.6.2

comment:7 Changed 5 years ago by thoughtpolice

Milestone: 7.6.27.10.1

Moving to 7.10.1.

comment:8 Changed 5 years ago by thomie

Cc: dfeuer added
difficulty: Unknown

comment:9 Changed 5 years ago by thoughtpolice

Milestone: 7.10.17.12.1

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.

comment:10 Changed 4 years ago by thoughtpolice

Milestone: 7.12.18.0.1

Milestone renamed

comment:11 Changed 4 years ago by thomie

Type of failure: Incorrect result at runtimeRuntime performance bug

comment:12 Changed 4 years ago by thomie

Milestone: 8.0.1
Note: See TracTickets for help on using tickets.