Wadler space leak

[Simon Marlow]

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?

The problem is that a "selector" has to be an expression of the form

   case x of
     C y1 .. yn -> yi

for some i.  The RTS contains pre-compiled selectors for values of i up 
to 16.  The garbage collector recognises selectors where x is already 
evaluated, and replaces them with the value.

So you can't do this for an arbitrary expression without generalising 
the mechanism.  Perhaps you could annotate an arbitrary thunk to say 
something like

   I select field N from free variable x

and then the GC could null out all fields except for N, as long as x was 
not required elsewhere.  But this has other problems - apart from being 
a lot more complicated in terms of what information we attach to thunks 
and what the GC has to do, it doesn't immediately eliminate the 
constructor, only the unreferenced fields, so you could still get 
certain kinds of leak.

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).

I haven't given it a great deal of thought though, maybe it could be 
made to work in GHC.

Cheers,
	Simon