Revert a CAF?

[Simon Marlow]

On 06/12/2011 17:48, wren ng thornton wrote:
> So, I have an optimization/internals question. Does the GHC API have any
> hooks for being able to revert a CAF to the original expression, thus
> discarding the previously computed result?
>
> The reason I'm wanting this is that I have a particular CAF which is an
> infinite list. Unfolding that list takes a fair deal of work, so we want
> to share it whenever possible; however it doesn't take an overwhelming
> amount of work, so if we know we've evaluated more of the list than
> necessary (for a long while), it'd be nice to be able to revert the
> evaluation in order to save on memory overhead (e.g., by calling relax
> :: IO()).
>
> I could hack something together based on unsafePerformIO and top-level
> IORefs, and it's clear that this is in fact a safe thing to do, but I'm
> worried about the semantic issues inherent in unsafePerformIOed
> top-level IORefs (e.g., the fact that their scope isn't particularly
> well defined: is it per library instance? per runtime?...).
> Unfortunately, for what I'm doing, it isn't really feasible to just
> leave the IO type in there nor to pass around the infinite list so we
> can use scoping rules to decide when to free it.
>
> (Feel free to offer alternative suggestions to handling this situation
> too.)

It would be possible, but it's not quite as straightforward as you might 
think.  Suppose you have a program like this:

xs = [1..100000]
evens = filter ((==0) . (`mod` 2)) xs

and you fully evaluate "evens".  Now, GHC will garbage collect "xs", 
because it isn't required any more.  However, if you revert "evens" to a 
CAF, now we require "xs" again, so we have to either revert that to a 
CAF or arrange to retain it in the first place on the grounds that we 
might need it again if some other CAF is reverted.

Reverting xs to a CAF is not hard - we could have the GC revert CAFs as 
soon as they become unreachable.  Arranging to retain it is harder.

GHCi gets around this by reverting *all* CAFs at the same time when you 
say :load.

There's one other thing: GHC doesn't support reverting CAFs in 
interpreted code at the moment, you have to reload the module.

So you need the following things:

  - modify the GC to revert CAFs when they become garbage

  - add a primop to revert a single CAF

not too hard, I would think...

Cheers,
	Simon