[LLVMdev] first two chapters for the ocaml bindings in svn

[Jon Harrop]

On Tuesday 30 December 2008 13:58:09 Erick Tryzelaar wrote:
> On Sat, Sep 20, 2008 at 9:57 AM, Jon Harrop
>
> <jonathandeanharrop at googlemail.com> wrote:
> > I think your new OCaml tutorials and the original C++ ones are absolutely
> > brilliant!
>
> Thanks Jon. I'm sorry I missed this message. Now that you've had some
> more experience with llvm, would you be interested in adding to the
> doc some performance and GC stuff? I haven't personally explored that
> yet.

As much as I would love to, I have actually learned very little about this 
(assuming you mean performance of LLVM-generated code and the use of GCs with 
LLVM-generated code) and was even going to ask questions along these lines 
here.

I implemented a BF compiler from scratch in OCaml, described in the following 
OCaml Journal article:

http://ocamlnews.blogspot.com/2008/09/writing-bytecode-compiler-using-llvm.html

It turned out to be 2x slower than the C++ one in the LLVM distribution. I 
assume the reason is the C++ version manipulates the pointer into the BF heap 
directly whereas I indirected everything through int-indexed array lookups 
and LLVM failed to optimize that away. Another lesson is that enabling LLVM's 
optimization passes can make a big difference.

Other than that, I spent a few days over Christmas working on a new HLVM that 
I have described here:

http://flyingfrogblog.blogspot.com/2008/12/building-better-future-high-level.html

I think this is a very exciting project with great potential but it is a huge 
undertaking. I already have the following features:

. Values of primitive types: unit, int, float, static null-terminated strings.

. Compound types: mutable arrays.

. Arithmetic (+, -, *, /) over ints and floats.

. Comparison (<, <=, =, >=, >, <>) over ints and floats.

. Let bindings.

. If expressions.

. Function application with multiple arguments.

. Compound sequences of expressions.

. Fast calling convention for internal functions, including tail calls.

. C calling convention for external functions and a special case for C's 
(varargs) printf.

. Top-level function definitions.

. JIT compilation to high-performance native-code using LLVM.

I am in the process of implementing the shadow stack and a simple GC but I 
also want first-class function pointers, run-time types and algebraic 
datatypes before I release anything.

Early benchmarks suggest that performance is excellent:

Int Fibonacci:
OCaml: 1.11s
HLVM:  1.20s

Float Fibonacci:
OCaml: 6.10s
HLVM:  2.07s 2.9x faster!

Sieve of Eratosthenes:
OCaml: 14.9s
HLVM:   6.63s 2.2x faster!

Mandelbrot:
OCaml: 4.07s
HLVM:  1.11s 3.7x faster!

As you can see, this new LLVM-based compiler generates code that can be 
several times faster than ocamlopt's. I would like to keep it that way but 
adding a GC threatens that and some of LLVM's missing features (e.g. 
exceptions) may require costly workarounds. Regardless, I am convinced that 
LLVM is by far the best tool for the job and the OCaml bindings make it a joy 
to work with from a language that was specifically designed for writing 
compilers.

The performance characteristics surprised me. In particular, LLVM's 
optimization passes make no difference to the performance of my HLVM on any 
of my benchmarks. I assume the reason is that LLVM's direct code generation 
does an excellent job with pure code and the optimizers can do nothing 
further with my impure code (e.g. setting array elements).

However, I am adding a GC and performance will probably demand a moving 
collector. So I will need to be able to update pointers into the heap and the 
easiest way to do that is to refer to everything by pointer with value types 
on the system stack and reference types in the shadow stack. When the GC is 
invoked it can mutate the pointers in the shadow stack safe in the knowledge 
that they will be reloaded but minimal performance will (hopefully) be lost 
because LLVM's optimization passes will remove as many of the redundant loads 
and stores as possible.

Partly because I have no desire to code in C++ but also due to the absence of 
working examples, I am not building upon LLVM's GC infrastructure. Instead, I 
am constructing a shadow stack "for an uncooperative environment". This will 
allow me to implement everything I need from the comfort of OCaml and, I 
believe, performance will be adequate.

As soon as I have anything more interesting to say I will gladly augment the 
documentation but, until then, I have a lot more learning to do!

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e