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
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
