deeqSeq proposal

[John Meacham]

On Mon, Apr 10, 2006 at 02:40:44PM -0700, Andy Gill wrote:
> >it is unlikely it will even be possible to implement in jhc without
> >radical changes to its internals. there is just no where to attach
> >a bit
> >to, and even if there were, there is no generic way to evaluate
> >something to WHNF, or even a concept of WHNF in final grin. (grin code
> >can look inside unevaluated closures, hopefully making the thunk
> >non-updatable)
>
> I do not understand.
>
> - (A) I'm calling for a recursive descent function that does seq. I
> could
> write it in Haskell, for any specific type.  How is seq implemented jhs?

it is true, if you can express it in core, then jhc can implement it.
but there is no way to express 'the bit you want to steal' in core.
indeed there is no where to steal a bit from. there isn't a thunk type
at runtime in jhc. so implementing deepSeq in the traditinal way is
fine, optimizing it in the way you describe is not.

> - (B) Once we have this recursive function, I'm advocating for an
> optimization
> which will make it cheap. Why can't we just steal a bit in the (GHC)
> info table,
> rather than mess with LSB of pointers, or have two info tables?
>
> Yes, in grin this information would need to be used at compile time
>  but the resulting code would be considerably faster. A deepSeq is
> a gift to the compiler from the programmer.

actually, it may be slower in jhc. reducing to normal form is not
necessarily a win in jhc, and if you do do it, you want to evaluate a
function as _early_ as possible, as in, as close to its definition
point. 'evals' are inlined to have a branch for every possible way a
value could come about, since you could deepseq pretty much any type of
object, you would end up with huge expanded evals, but worse, it would
cause all these thunks to be updatable when they didn't need to be.

imagine a use of a thunk, rather than evaluate it to WHNF, jhc will just
pull the components right out of the unevaluated thunk, if at some point
in the past it might have been deepsequed, you suddenly need a case
statement to determine whether it has been evaluated or not. knowing
something has not been evaluated is just as valuable as knowing it has
definitely been.

for a quick example, imagine you have this function and it is not
optimized away in core for some reason or another.

> mktup x y = (y,x)

> foo x = case x of (x,y) -> bar x y
> main = let ... in foo (mktup a b)

now we convert to grin

> fmktup x y = do
>         return (CTuple y x)
>
> ffoo x = do
>         y <- eval x
>         update x y
>         (CTuple a b) <- y
>         bar a b
>
> main = do
>         ...
>         x <- Store (Fmktup a b)
>         ffoo x

things starting with capital letters are tags, parenthesized things are
nodes on the heap.


now, we do eval-expansion in ffoo, points to analysis determines a
suspended Fmktup may be passed into ffoo.

> ffoo x = do
>         x' <- fetch x
>         y <- case x' of
>                 (Fmktup a b) ->
>                         fmktup a b
>         update x y
>         (CTuple a b) <- y
>         bar a b

now, the case-of-case code motion (the y scrutinization is treated as a
simple case pulls the code into ffoo


> ffoo x = do
>         x' <- fetch x
>         case x' of
>                 (Fmktup a b) ->
>                         y <- fmktup a b
>                         update x y
>                         (CTuple a b) <- y
>                         bar a b

now, points-to analysis showed that nothing scrutinized this memory
location looking for a CTuple, therefor the update is uneeded.

also, fmktup is trivial so it is inlined

> ffoo x = do
>         x' <- fetch x
>         case x' of
>                 (Fmktup a b) ->
>                         y <- Return (CTuple b a)  -- inlined fmktup
>                         (CTuple a b) <- y
>                         bar a b

wrich trivially simplifise too

> ffoo x = do
>         x' <- fetch x
>         case x' of
>                 (Fmktup a b) ->
>                         bar b a
>
> ffoo x = do
>         (Fmktup a b) <- fetch x
>         bar b a

notice, there is no longer a concept of WHNF, Fmktup effectivly has
become the head normal form of that call due to standard optimization,
this type of transformation might happen to some suspended versions of
mktup, but not others, there is no way to tell from the heap location
itself whether it should be evaluated into WHNF or if uses are going to
pull its arguments right out of its closure or not.

deepseqing this case would only hurt performance as it would mean we couldn't
get rid of the 'update' or 'check if it is already a tuple' case. of
course, if mktup were some expensive call, then the opposite might be
true. in any case, deepseq is not always a win.

the above ffoo actually has another optimization waiting, arity raising,
since it knows x is always a pointer to a Fmktup, it pulls the arguments
out and passes 'a and b' to ffoo directly. since all function calls are
explicit in grin, we just go through and modify each call site
accordingly.


        John




--
John Meacham - ⑆repetae.net⑆john⑈