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