[Haskell-cafe] more sharing in generated code

[Peter Divianszky]

On 03/11/2012 11:20, Peter Divianszky wrote:
> 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.

a small correction on cond-update:

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

Evaluation of x_new should be OK because we need x_new eventually.
With this change, nested record updates with identical values behave 
like an identical function with sharing I think.

Peter