Re: [Caml-list] High-performance bytecode interpreter in OCaml

[Jon Harrop <jon@ffconsultancy.com>]

On Wednesday 15 August 2007 14:20:34 Joel wrote:
> I have an existing bytecode file that I need to execute. The bytecode
> is produced by some other compiler. Does this change anything?

Yes, that rules out most of the solutions I proposed. :-)

> I'm not sure if a term-level interpreter or rewriter applies in this
> scenario.

Indeed. If string operations turn out to be slow in OCaml and the CPS way of 
doing things is too obfuscated, you might try translating the byte array into 
an instruction array with a more OCaml-friendly notion of instruction (i.e. a 
variant type!). This would be particularly preferable if you think there are 
any simplifying transformations that you can do to reduce your workload.

> As for CPS, what I meant is implementing each bytecode instruction as
> a function that takes a continuation (next instruction?).

That should certainly work. Make sure you hoist out as much computation as 
possible from the continuation closures that you generate.

For example, make sure you change this:

  let rec compile bytecode = match bytecode with
    | 0x83::x::t ->
        (fun k ->
           print_string (String.lowercase (string_of_int x));
           k(compile t)) 

into this:

  let rec compile bytecode = match bytecode with
    | 0x83::x::t ->
        let x = String.lowercase (string_of_int x) in
        let t = compile t in
        (fun k -> print_string x; k t) 

This allows you to precompute as much as possible while you build up the 
continuation that will evaluate the program.

In particular, make sure you hoist out any lookups, such as jump labels.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
OCaml for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists/?e