------- Forwarded Message Follows -------
From: Rob MacAulay <[EMAIL PROTECTED]>
To: [EMAIL PROTECTED]
Subject: Re: runtime optimization of haskell
Date sent: Fri, 24 Mar 2000 10:59:33 -0000
Date sent: Thu, 23 Mar 2000 12:19:21 -0500 (EST)
From: Jan-Willem Maessen <[EMAIL PROTECTED]>
To: [EMAIL PROTECTED]
Subject: Re: runtime optimization of haskell
Send reply to: [EMAIL PROTECTED]
I am not at all an expert on this sort of thing, but has anyone
looked at Juice? This was an alternative to a bytecode intermediate
form originally developed for Oberon. Instead of using bytecodes, it
used snippets of code trees, which could be re-used for common
subexpressions (sound familiar?). The authors have since been
working on the dynamic optimisation of this type of code
representation.
I keep losing the URL, but I think this ponts to the right place:
http://caesar.ics.uci.edu/kistler/
Rob MacAulay
> I'm not currently working on dynamic compilation, but I went to
> Vasanth Bala's talks at the Dynamic Compilation Workshop before PoPL
> and later at MIT. I, too, was intrigued by the possibility of doing
> this sort of dynamic compilation for functional languages. I've given
> the technical points some thought, so I thought I'd share what I'd
> come up with.
>
> First, Dynamo, Crusoe, and their ken focus on optimization of run-time
> program traces. It was quite clear from Bala's talk that traces
> should not be assumed to match function boundaries; we may compile
> some trace through a function (the recursive case, for example) while
> interpreting the rest (eg. the base case). The efficiency of the
> technique depends on the fact that we compile _only_ the code which is
> being frequently executed, as we have a limited cache to hold that
> compiled code.
>
> The biggest promise of this approach is that it eliminates most
> unknown control flow. In C code this is things like function return
> (a trace doesn't necessarily end when a function returns), calls to
> dynamically-linked functions, and calls to function pointers/virtual
> functions. All of these are far more common in Haskell than in C;
> this makes the technique look very attractive indeed.
>
> On the other hand, Dynamo at least does not always succeed. Very
> unstructured symbolic code such as GCC and Go slow down and cause
> Dynamo to give up. This is less promising; symbolic applications seem
> like just the sort of thing we want to re-code in Haskell, as they
> involve the complex data structure manipulation that is so much easier
> with algebraic types.
>
> A good step toward trying this out, though, would be to devise a
> trace-compilable bytecode for Haskell. I'm not sure that e.g. G-code
> really fits the bill---we want a bytecode that we can unroll
> dynamically without having to keep track a lot of context information
> (such as what's on the stack). We would also want "usual case"
> bytecodes that would verify unknown control flow against a guess at
> the actual control flow.
>
> I suspect producing traces of pure bytecode which unroll control flow
> with guesses ought to produce pretty good speedups when compared to
> current bytecode interpreters (hugs, nhc); I'd be very interested to
> see if this approach can compete with machine code that doesn't do any
> guessing. In any case, this seems like a good proof of concept---if
> we can't speed byte code up in this way, I wouldn't expect trace
> compilation to do any better than any other kind of JIT compilation.
>
> I'd love to get the chance to do this experiment some day.
>
> -Jan-Willem Maessen
> [EMAIL PROTECTED]
>
>
> Here are some references, btw:
>
> Dynamo: http://www.hpl.hp.com/cambridge/projects/Dynamo
>
> Read the tech report from HP, as it contains a fair level of detail
> and gives a pretty good feel for the strengths and weaknesses of the
> approach. As I say, it really wins when there's lots of unknown
> control flow (jumps to addresses in registers) that turns out to be
> fairly predictable in practice.
>
>
> The best chance I've seen at matching this statically was the GRIN
> project, which Thomas Johnsson was pursuing a while back at Chalmers.
> He used an exhaustive control-flow analysis to reduce each instance of
> unknown control flow (eg. the forcing of a thunk) to a small set of
> known destinations (eg. the possible thunks that actually reach that
> program point). Combine that with interprocedural register allocation
> (courtesy Urban Boquist) and you get the fastest Haskell code I've
> seen. Any comments on this from the Chalmers folks? Alas I don't
> think this ever made it past the prototyping stage, and of course it
> required exhaustive whole-program analysis:
>
> T. Johnsson, Analysing Heap Contents in a Graph Reduction Intermediate
> Language, in Proc. Glasgow FP Workshop, Ullapool 1990.
> How to resolve the control flow...
>
> U. Boquist & T. Johnsson, The GRIN Project: A Highly Optimising Back
> End for Lazy Functional Languages.
> I found this on the web ages and ages ago. It gives some
> results for small programs, and details the compilation
> techniques.
>
Rob MacAulay Vulcan Asic ___________
email : [EMAIL PROTECTED] \ |####/
http : www.vulcanasic.com \ |###/
Tel +[44] 1763 247624 (direct) \ |##/
Tel +[44] 1763 248163 (office) \ |#/
Fax +[44] 1763 241291 \|/
