deeqSeq proposal

[Simon Marlow]

On 07 April 2006 22:38, Andy Gill wrote:

> On Apr 7, 2006, at 3:59 AM, Rene de Visser wrote:
> 
>> Hello,
>> 
>> As deepSeq has a non local effect, I think it requires a non-local
>> source transformation to implement it. One option would be for the
>> compiler to create a second deepSeq version of every function
>> definition. 
>> 
>> e.g.
>> 
>> If the user defines a function f
>> 
>> f x = g h x
>> 
>> then the compile creates an additional function !!f
>> 
>> !!f x = temp `seq` temp
>>          where temp = !!g !!h x
>> 
>> which uses the compiler generated functions !!g and !!h.
>> 
>> It looks like library writers are increasingly doing this manually.
>> Creating a strict and non strict version of a number of the
>> functions provided. This would automate that.
>> 
>> Rene.
>> 
> 
> It depend on the semantics of deepSeq. If deepSeq just performs seq
> on all constructors recursively, then
> that can be implemented as a runtime primitive. If deepSeq is making
> all embedded partial applications
> strict, then yes this might be a non-local effect.
> 
> What are the semantics of !!(\ x -> ...)?
> 
> I am calling for the version of deepSeq/strict that evaluates all
> thunks, but does not strictify the arguments
> to partial application, because
>   - I believe this is straightforward to implement

It's not *completely* straightforward to implement, at least in GHC, and
at least if you want to implement it in a modular way (i.e. without
touching lots of different parts of the system).

The obvious way to "add a bit to a closure" is to use the LSB of the
info pointer, which currently is always 0.  However, that means masking
out this bit every time you want to get the info pointer of a closure,
which means lots of changes to the runtime.  The price seems pretty
high.

An alternative is to have two info tables for every constructor, one
normal one and one "deepSeq'd", and the normal one probably needs to
point to the deepSeq'd version.  This doesn't require masking out any
bits, but it does increase code size (one extra info table + entry code
for every constructor, except possibly those that don't contain any
pointer fields), and one extra field in a constructor's info table.
Plus associated cache pollution.

Yet another alternative is to store fully evaluated data in a segregated
part of the heap.  The garbage collector could do this - indeed we
already do something similar, in that data that has no pointer fields is
kept separate.  Checking the "deepSeq" bit on a closure is then more
complicated - but this has the advantage that only the GC and storage
manager are affected.

None of these solutions is as simple and self-contained as I'd like :-(

Cheers,
	Simon