[Haskell-cafe] more sharing in generated code

[Peter Divianszky]

On 03/11/2012 10:47, Andreas Abel wrote:
> On 03.11.12 10:05 AM, Peter Divianszky wrote:
>> Suppose we have a record update
>>
>>    r { x = f (r x)}
>>
>> and suppose that most of the time f returns it's argument unchanged.
>>
>>     Recently I've heard about Q-combinators.
>>     Central idea: Change (f :: a -> a) to (f' :: a -> Maybe a) returning
>>     Nothing when the value didn't change.
>>     Then we can replace the record update with smarter code which
>>     preserves more sharing.
>
> Just adding a remark here:  I actually played with these Q-combinators,
> they actually worsened performance of Agda.  The problem is that they
> make the code strict.  The performance loss due to strictness
> outweighted the potential performance gain by increased sharing.
> Q-combinators were developed by John Harrison in the context of ML,
> which is strict anyway.
>
> I guess a compiler support for smart record update would not have the
> strictness penalty.

Yes, for that we need a copy first and an update later.
This can be implemented by replacing every record update

    r' = r { x = y }

with

    r' = r { x = unsafePerformIO (cond-update r r' (x r) y) }

where we keep the current record update mechanism and implement 
cond-update like

cond-update :: r -> r -> x -> IO x
cond-update r_old r_new x_old x_new = do
     b <- x_old === x_new
     when b (replace r_new r_old)
     return x_new

where (===) is pointer-equality and replace is a low-level function 
which replaces thunks in the heap.

Peter