Re: [Caml-list] HLVM

[Jon Harrop <jon@ffconsultancy.com>]

On Saturday 26 September 2009 18:21:21 David McClain wrote:
> What, in particular, sets HLVM apart. Surely not just the native
> machine types?

JIT compilation opens up several hugely-productive optimizations:

1. Polymorphism no longer persists to run-time so there is no need for a 
uniform representation. Whereas OCaml tags integers and boxes floats and 
tuples with a couple of hacks for special cases like all-float-records and 
float arrays, HLVM never boxes any of them (including 32-bit ints, 64-bit 
floats and complex numbers). Moreover, this massively reduces the stress on 
the garbage collector. For example, although OCaml has a heavily optimized GC 
it is already 50% slower than the current HLVM at computing a complex FFT 
where the complex numbers are represented by the type float * float because 
OCaml allocates every intermediate tuple on the minor heap.

2. The garbage collector is partially specialized with respect to user defined 
types. Whereas OCaml's GC blindly traverses the heap testing almost every 
word to see whether or not it is a pointer, HLVM's GC JIT compiles traversal 
code for every type it sees and that code jumps directly to the pointers in a 
value.

3. The code generator can target the exact machine being used so things like 
SSE are trivial to implement and use. For example, the integer-based 
Monte-Carlo test from the SciMark2 benchmark is up to 6x faster with LLVM 
than with OCaml.

4. You get a native code REPL for free.

5. FFI stubs are JIT compiled for you: no more hand-written C stubs!

On top of that, LLVM handles aggregate values very efficiently so HLVM lets 
you use them for tuples. That gives you value types (a feature that OCaml 
lacks, which can dramatically improve performance and interoperability) that 
work with tail calls (structs break tail calls on the CLR).

> Are you handling array references in some unusually efficient manner?

Not really. The main oddity is that references in HLVM are currently 3 word 
structs: one pointer to the run-time type, one word of metadata (e.g. array 
length) and a one word pointer that points to the real data (or NULL). That 
has three main advantages:

1. You can pass arrays of value types to and from C easily and efficiently.

2. You have a typed "null" pointer. So empty options, lists and arrays are 
represented efficiently as an unboxed value (unlike F# where empty lists and 
arrays are inefficient heap-allocated values) yet they can still be pretty 
printed correctly (which OCaml cannot even handle and F# gets wrong on 
optimized types like options which use the CLR's typeless null).

3. You can get to the run-time type directly with a single indirection rather 
than loading the value and then the run-time types from its header (two 
indirections).

> Are you avoiding unnecessary copy-on-writes of large arrays by some
> form of whole-program analysis?

No. HLVM does not yet do any program analysis at all. It is currently only 
trying to map ML-style code to assembler (via LLVM IR) differently in order 
to obtain a different performance profile. Specifically, the performance 
profile I would like. I am not a fan of non-trivial larger scale analysis and 
optimization because it renders performance unpredictable. Predictable 
performance is one of the (many) nice aspects of OCaml that I would like to 
keep.

> I still don't have a handle on HLVM... 

HLVM is an experiment to see what a next-generation implementation of a 
language like OCaml might look like, addressing all of OCaml's major 
shortcomings (interoperability, parallelism and some performance issues). My 
preliminary results proved that there is indeed a lot to be gained by doing 
this but more work is required to give HLVM all of the basic features.

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