Re: [Caml-list] How to write an efficient interpreter

[Gerd Stolpmann <info@gerd-stolpmann.de>]

Am Montag, den 24.10.2011, 11:58 +0200 schrieb Gabriel Scherer:
> Even staying at the "interpreter" stage, you can probably improve your
> performance seriously by being careful about your implementation : use
> efficient data structure (what is your implementation of variable
> lookup?), avoid unnecessary allocation, use tail-recursive functions
> where possible, etc. Try to find a time-consuming script example that
> exercise the type of computations you'll usually perform, and profile
> your interpreter with gprof (compiled natively), try to optimize the
> parts that show high in the profile, rinse and repeat.
> 
> The natural next step is to use a bytecode instead of interpreting an
> AST directly. You can probably find something relatively simple and
> yet have a net efficiency gain over direct interpretation, because the
> bytecode structure is more linear and can be interpreted more
> efficiently; in a way, you compiled away the tree traversal. 

Well, I wouldn't be too optimistic that this also works for an
interpreter written in Ocaml. Bytecode profits a lot from cache
locality, i.e. all bytecode instructions in a single cache line are
loaded at once from RAM. Cache lines are short, though, usually only 64
bytes. If the bytecode is an int array, this translates to 8 or 16 array
elements (64/32 bit platforms). If you stick to the int array, you
probably get the performance benefit, but you have to live with the
integer representation, which will make other parts of the interpreter
difficult (e.g. representation of values). If you use an instruction
array, where "instruction" is a variant type with and without arguments,
the performance benefit is probably completely lost, because you deviate
too much from the linear memory representation.

Also, anything in the direction of good bytecode is really complicated.
What about this alternative: It is much simpler to "JIT"-compile to
ocaml (i.e. dump your AST in a different syntax), compile the ocaml code
by invoking ocamlc or ocamlopt, and to load the compiled code
dynamically (I'm just guessing that you have a dynamic environment).
There are only a few drawbacks of this approach, namely that you need
ocamlc or ocamlopt at runtime (plus "helper files", i.e. the cmi's of
the standard library), and that you cannot delete code from RAM once it
is loaded. The latter is usually not too problematic if there is a
possibility to restart the system now and then.

Gerd

> At this
> level, you become quite sensible to micro-optimisation : bytecode
> interpreters written in C have access to efficiency tricks (direct
> threaded code and the like, or even pinning registers directly) that
> are difficult or impossible to emulate in OCaml, even if you can get
> something reasonable with mutually tail-recursive functions. As a
> single point of measure, I spent a few hours hacking an OCaml bytecode
> interpreter for a very small subset of Caml recently, and got within
> 5x-10x slower than the OCaml bytecode interpreter itself for favorable
> cases. It's not very good, or not very bad, depending on what you
> expect (but definitely slower than the ocaml native compiler, or even
> the various JIT projects).
> 
> Of course, if possible, you could also target an existing bytecode or
> intermediate representation, or even compile to an existing language
> with a rich enough runtime. If you're familiar, for example, with
> either JVM or LLVM, those are the popular choices these days. I don't
> know how that would mix with inline Javascript, though (I suppose both
> environments have a javascript interpreter). You could also compile to
> OCaml code or Javascript directly, and reuse their implementation, GC,
> etc. With the current Javascript engines, you can get very good
> performances if you compile in a way that resemble the ugly Javascript
> code they're trying to optimize. For example, js_of_ocaml compiles
> OCaml bytecode into Javascript and the result performs better than
> using OCaml bytecode interpreter (written in C and well designed for
> efficiency) directly. That's already quite a lot more work, however,
> than a good interpreter or a simple home-made bytecode.
> 
> On Mon, Oct 24, 2011 at 11:10 AM, Diego Olivier Fernandez Pons
> <dofp.ocaml@gmail.com> wrote:
> >     Caml-list,
> > I have to write an interpreter for a datatype rich purely applicative
> > language. I have already written a naive interpreter (like in programming
> > languages class) and was wondering what where the options for writing
> > something that would perform better while keeping it maintainable by a
> > single person < 5% dedicated and preferably only in core-ML (no C code or
> > fancy ML extensions).
> > The language could be described as a rich datastructure typed SQL with a
> > programming language syntax
> > - first class sets, arrays, dictionaries, lists and their corresponding
> > comprehensions
> > - tuples and records merged into a single concept (accessible per position
> > like in (x, y) = ... or per label like in for t in tupleSet if t.label == 3
> > then)
> > - only applicative functions (no lambda operator, no partial application)
> > - simple types are int, double and string
> > - only user declared types are tuples-records
> > It is mainly used for data transformation : take a list of countries,
> > extract from an database the international airports of those countries,
> > geolocalize them using city/location table, generate a distance table using
> > a great-circle distance, assign to each size of plane the legs they can do
> > based on their maximum fight range, etc.
> > The language has a JavaScript inline capability
> >     execute JavaScript {
> >         //write your javascript code here
> >     }
> > that's typically used to define functions, unroll comprehensions to make
> > them more efficient and to call external libraries (JavaScript has full
> > visibility on all the language objects and can read/write directly inside,
> > probably the existing interpreter was written in JavaScript), so I am
> > considering allowing those features in the core language and only supporting
> > a very slow JavaScript deprecated compatibility mode.
> >
> >          Diego Olivier
> 
> 

-- 
------------------------------------------------------------
Gerd Stolpmann, Darmstadt, Germany    gerd@gerd-stolpmann.de
Creator of GODI and camlcity.org.
Contact details:        http://www.camlcity.org/contact.html
Company homepage:       http://www.gerd-stolpmann.de
*** Searching for new projects! Need consulting for system
*** programming in Ocaml? Gerd Stolpmann can help you.
------------------------------------------------------------