Jan Christiansen | 28 Oct 09:59 2010
Picon

Wadler space leak

Hi,

I have a question regarding the famous Wadler space leak. The  
following program is a variation of Wadler's example.

   let (first,rest) = break (const False) input
   in
   print (length (first ++ rest))

When I compile this program using -O2 and use a large text file as  
input the code runs in constant space. If I understand correctly, the  
program runs in constant space because ghc uses an optimization  
similar to the one proposed by Wadler/Sparud.

If I define the following function which is based on break

   splitBy :: (a -> Bool) -> [a] -> [[a]]
   splitBy _ []  = []
   splitBy p xs  =
     l : case ys of
              []   -> []
              _:zs -> splitBy' p zs
     where
       (l,ys) = break p xs

and compile the following program the behaviour is different.

   print (length (concat (splitBy (const False) input)))

In this case the memory usage is not constant. However if I use a  
(Continue reading)

Bertram Felgenhauer | 28 Oct 15:21 2010

Re: Wadler space leak

Hi,

>   let (first,rest) = break (const False) input
>   in
>   print (length (first ++ rest))
> 
> When I compile this program using -O2 and use a large text file as
> input the code runs in constant space. If I understand correctly,
> the program runs in constant space because ghc uses an optimization
> similar to the one proposed by Wadler/Sparud.

Right. The optimization works by producing special thunks for tuple
selectors which the garbage collector can recognize and evaluate
during GC.

However the implementation in GHC is quite brittle. See

    http://hackage.haskell.org/trac/ghc/ticket/2607

I suspect your program is another instance of this behaviour.

> If I define the following function which is based on break
> 
>   splitBy :: (a -> Bool) -> [a] -> [[a]]
>   splitBy _ []  = []
>   splitBy p xs  =
>     l : case ys of
>              []   -> []
>              _:zs -> splitBy' p zs
>     where
(Continue reading)

Simon Marlow | 1 Nov 10:38 2010
Picon

Re: Wadler space leak

On 28/10/2010 14:21, Bertram Felgenhauer wrote:
> Hi,
>
>>    let (first,rest) = break (const False) input
>>    in
>>    print (length (first ++ rest))
>>
>> When I compile this program using -O2 and use a large text file as
>> input the code runs in constant space. If I understand correctly,
>> the program runs in constant space because ghc uses an optimization
>> similar to the one proposed by Wadler/Sparud.
>
> Right. The optimization works by producing special thunks for tuple
> selectors which the garbage collector can recognize and evaluate
> during GC.
>
> However the implementation in GHC is quite brittle. See
>
>      http://hackage.haskell.org/trac/ghc/ticket/2607
>
> I suspect your program is another instance of this behaviour.
>
>> If I define the following function which is based on break
>>
>>    splitBy :: (a ->  Bool) ->  [a] ->  [[a]]
>>    splitBy _ []  = []
>>    splitBy p xs  =
>>      l : case ys of
>>               []   ->  []
>>               _:zs ->  splitBy' p zs
(Continue reading)

Jan Christiansen | 1 Nov 17:52 2010
Picon

Re: Wadler space leak


On 01.11.2010, at 10:38, Simon Marlow wrote:

> On 28/10/2010 14:21, Bertram Felgenhauer wrote:

>> Right. The optimization works by producing special thunks for tuple
>> selectors which the garbage collector can recognize and evaluate
>> during GC.
>>
>> However the implementation in GHC is quite brittle. See
>>
>>     http://hackage.haskell.org/trac/ghc/ticket/2607
>>
>> I suspect your program is another instance of this behaviour.
>
> Yes, that's exactly what happens.

Thanks very much for the explanation.

It seems to me that this bug is not considered as high priority. Is  
this correct? So it is not likely that this will be fixed in one of  
the next ghc releases, is it?

Thanks, Jan
Simon Marlow | 2 Nov 10:20 2010
Picon

Re: Wadler space leak

On 01/11/2010 16:52, Jan Christiansen wrote:
>
> On 01.11.2010, at 10:38, Simon Marlow wrote:
>
>> On 28/10/2010 14:21, Bertram Felgenhauer wrote:
>
>>> Right. The optimization works by producing special thunks for tuple
>>> selectors which the garbage collector can recognize and evaluate
>>> during GC.
>>>
>>> However the implementation in GHC is quite brittle. See
>>>
>>> http://hackage.haskell.org/trac/ghc/ticket/2607
>>>
>>> I suspect your program is another instance of this behaviour.
>>
>> Yes, that's exactly what happens.
>
> Thanks very much for the explanation.
>
> It seems to me that this bug is not considered as high priority. Is this
> correct? So it is not likely that this will be fixed in one of the next
> ghc releases, is it?

It's not really a question of priority, rather that we don't know of a 
good way to fix it!

Cheers,
	Simon
(Continue reading)

Jan Christiansen | 7 Nov 18:47 2010
Picon

Re: Wadler space leak


On 02.11.2010, at 10:20, Simon Marlow wrote:

> It's not really a question of priority, rather that we don't know of  
> a good way to fix it!

I would not have guessed that there exists a Haskell related problem  
that cannot immediately be fixed by the ghc headquarters ; )

If I understand correctly, the problem is to keep the selectors  
recognizable while still performing optimizations that might "destroy"  
the selector structure. In Bertram's example the resulting expression  
looked as follows.

>   l : case q of (_, ys) ->  case ys of
>                                               []   ->  []
>                                               _:zs ->  splitBy' p zs

Is it correct that the selector is not recognizable in this case  
because the right hand side fo the outermost case expression is not a  
simple variable but a case expression? It is probably quite naive to  
assume that the problem can be solved by looking for a structure like

   case q of
           (_,ys) -> e

where ys is a free variable in e. There are probably cases where  
further optimizations prevent this. Or do I miss the real problem in  
identifying selectors?

(Continue reading)

Simon Marlow | 8 Nov 14:28 2010
Picon

Re: Wadler space leak

On 07/11/2010 17:47, Jan Christiansen wrote:
>
> On 02.11.2010, at 10:20, Simon Marlow wrote:
>
>> It's not really a question of priority, rather that we don't know of a
>> good way to fix it!
>
> I would not have guessed that there exists a Haskell related problem
> that cannot immediately be fixed by the ghc headquarters ; )
>
> If I understand correctly, the problem is to keep the selectors
> recognizable while still performing optimizations that might "destroy"
> the selector structure. In Bertram's example the resulting expression
> looked as follows.
>
>> l : case q of (_, ys) -> case ys of
>> [] -> []
>> _:zs -> splitBy' p zs
>
> Is it correct that the selector is not recognizable in this case because
> the right hand side fo the outermost case expression is not a simple
> variable but a case expression? It is probably quite naive to assume
> that the problem can be solved by looking for a structure like
>
> case q of
> (_,ys) -> e
>
> where ys is a free variable in e. There are probably cases where further
> optimizations prevent this. Or do I miss the real problem in identifying
> selectors?
(Continue reading)

Duncan Coutts | 9 Nov 08:58 2010

Re: Wadler space leak

On 8 November 2010 13:28, Simon Marlow <marlowsd <at> gmail.com> wrote:
>
> There's another approach in Jan Sparud's paper here:
>
> http://portal.acm.org/citation.cfm?id=165196
>
> although it's not clear that this interacts very well with inlining either,
> and it has a suspicious-looking side-effecting operation.  It also looks
> like it creates a circular reference between the thunk and the selectors,
> which might hinder optimisations, and would probably also make things slower
> (by adding extra free variables to the thunk).

This proposal is mentioned favourably by Jörgen Gustavsson David Sands
in [1] (see section 6, case study 6). They mention that there is a
formalisation in Gustavsson's thesis [2]. That may say something about
inlining, since that's just the kind of transformation they'd want to
show is a space improvement.

[1]: Possibilities and Limitations of Call-by-Need Space Improvement (2001)
      http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.8.4097

[2]: Space-Safe Transformations and Usage Analysis for Call-by-Need
Languages (2001)
      (which I cannot immediately find online)

Duncan
Max Bolingbroke | 9 Nov 13:50 2010
Picon

Re: Wadler space leak

On 9 November 2010 07:58, Duncan Coutts <duncan.coutts <at> googlemail.com> wrote:
> This proposal is mentioned favourably by Jörgen Gustavsson David Sands
> in [1] (see section 6, case study 6). They mention that there is a
> formalisation in Gustavsson's thesis [2]. That may say something about
> inlining, since that's just the kind of transformation they'd want to
> show is a space improvement.

During development of my supercompiler, I noticed that a feature like
this one (explicit thunk update in the intermidate language) would
enable more deforestation in rare circumstances.

First step is to build an alternative operational semantics for Core
which includes explicit thunk update. First, we add to the term syntax
something of the form "update x v e" where:
 * x is a variable
 * v is either
   1) A syntactic value
   2) Or a variable pointing to something that is certainly evaluated,
by which we mean that the corresponding binding is either:
     a) The "wildcard" binder of a case expression (or equivalently
the variable bound by its default alternative)
     b) A let with a value RHS
 * e is a term

We give this new syntax this operational semantics in the standard
Sestoft abstract machine for call by need:

< H | update x v e | K > --> < H, x |-> v | e | K >

We also need to change the variable rule in the standard semantics from:
(Continue reading)

Josef Svenningsson | 9 Nov 19:06 2010
Picon

Re: Wadler space leak

Let me clarify a bit exactly how Gustavsson and Sands (I'll refer to them as GS) handled the issue of the Wadler space leak. It's true that they adopted an approach similar to Sparud in that they extended their core calculus with a new language construct which could solve the problem. This is contrast to Wadler who changed the garbage collector instead, something that GS said would lead to bad behavior in their calculus. 

BUT, GS did not adopt exactly the construct that Sparud suggested. Sparud's suggestion was to add an updatePat primitive to the language. This was inspired by how the G-machine work, it had update instructions which where typically executed after a value was computed. It's a rather bad fit for the STG-machine which pushes update markers on the stack whenever it starts to evaluate a thunk. Updates are performed whenever there is an update marker on the stack when it has computed something to WHNF.
The language construct that GS chose was to have pattern bindings as primitive in the language. So the code snippet below (taken from Jörgen's thesis) would be a valid core program. It would not be desugared into case expressions.
~~~
let (ps,qs) = split ys
in (y:ps,qs)
~~~
The semantics of pattern bindings involves a new kind of update marker which, in the example above, will update both ps and qs, whenever the 'split ys' is computed to WHNF. This neatly solves the space leak problem. And it is a much closer fit to the STG-machine in that uses update markers on the stack to coordinate the graph reduction.
 
I think the solution GS chose should work much better for GHC than Sparud's suggestion. But it would no doubt be an invasive change to GHC as Core would have to be changed to support pattern bindings. 

Cheers,

Josef

On Tue, Nov 9, 2010 at 8:58 AM, Duncan Coutts <duncan.coutts <at> googlemail.com> wrote:
On 8 November 2010 13:28, Simon Marlow <marlowsd <at> gmail.com> wrote:
>
> There's another approach in Jan Sparud's paper here:
>
> http://portal.acm.org/citation.cfm?id=165196
>
> although it's not clear that this interacts very well with inlining either,
> and it has a suspicious-looking side-effecting operation.  It also looks
> like it creates a circular reference between the thunk and the selectors,
> which might hinder optimisations, and would probably also make things slower
> (by adding extra free variables to the thunk).

This proposal is mentioned favourably by Jörgen Gustavsson David Sands
in [1] (see section 6, case study 6). They mention that there is a
formalisation in Gustavsson's thesis [2]. That may say something about
inlining, since that's just the kind of transformation they'd want to
show is a space improvement.

[1]: Possibilities and Limitations of Call-by-Need Space Improvement (2001)
     http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.8.4097

[2]: Space-Safe Transformations and Usage Analysis for Call-by-Need
Languages (2001)
     (which I cannot immediately find online)

Duncan
_______________________________________________
Glasgow-haskell-users mailing list
Glasgow-haskell-users <at> haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users

_______________________________________________
Glasgow-haskell-users mailing list
Glasgow-haskell-users <at> haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users

Gmane