From b43be28258a3d49bde40095b210047e99742f8a5 Mon Sep 17 00:00:00 2001 From: simonmar Date: Fri, 22 Apr 2005 08:58:36 +0000 Subject: [PATCH] [project @ 2005-04-22 08:58:36 by simonmar] Add a comment about possible improvement to the THUNK_SELECTOR algorithm, from discussion with Ian Lynagh --- ghc/rts/GC.c | 42 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 42 insertions(+) diff --git a/ghc/rts/GC.c b/ghc/rts/GC.c index 7074a53..545ee1c 100644 --- a/ghc/rts/GC.c +++ b/ghc/rts/GC.c @@ -1996,6 +1996,48 @@ loop: been BLACKHOLE'd, and should be updated with an indirection or a forwarding pointer. If the return value is NULL, then the selector thunk is unchanged. + + *** + ToDo: the treatment of THUNK_SELECTORS could be improved in the + following way (from a suggestion by Ian Lynagh): + + We can have a chain like this: + + sel_0 --> (a,b) + | + |-----> sel_0 --> (a,b) + | + |-----> sel_0 --> ... + + and the depth limit means we don't go all the way to the end of the + chain, which results in a space leak. This affects the recursive + call to evacuate() in the THUNK_SELECTOR case in evacuate(): *not* + the recursive call to eval_thunk_selector() in + eval_thunk_selector(). + + We could eliminate the depth bound in this case, in the following + way: + + - traverse the chain once to discover the *value* of the + THUNK_SELECTOR. Mark all THUNK_SELECTORS that we + visit on the way as having been visited already (somehow). + + - in a second pass, traverse the chain again updating all + THUNK_SEELCTORS that we find on the way with indirections to + the value. + + - if we encounter a "marked" THUNK_SELECTOR in a normal + evacuate(), we konw it can't be updated so just evac it. + + Program that illustrates the problem: + + foo [] = ([], []) + foo (x:xs) = let (ys, zs) = foo xs + in if x >= 0 then (x:ys, zs) else (ys, x:zs) + + main = bar [1..(100000000::Int)] + bar xs = (\(ys, zs) -> print ys >> print zs) (foo xs) + -------------------------------------------------------------------------- */ static inline rtsBool -- 1.7.10.4