HLVM

HLVM

[David McClain]

Wow! Thanks for that much more substantive feedback on HLVM.

I am not intimately familiar with LLVM. I am surprised that JIT can  
offer speedups over statically compiled code.

And forgive me for asking what may seem a question with an obvious  
answer... but now don't you also have to change the OCaml compiler  
back end to target the HLVM?

Dr. David McClain
dbm@refined-audiometrics.com

Re: [Caml-list] HLVM

[Alp Mestan]

[-- Attachment #1: Type: text/plain, Size: 668 bytes --]

On Sun, Sep 27, 2009 at 6:57 PM, David McClain <dbm@refined-audiometrics.com
> wrote:

> And forgive me for asking what may seem a question with an obvious
> answer... but now don't you also have to change the OCaml compiler back end
> to target the HLVM?
>

The current "example" provided with HLVM is a very minimal ML-style language
implementation. However, there was a Jane Street Summer Project proposal to
port OCaml's current compiler to HLVM/LLVM. It hasn't been accepted.

But if HLVM gets more complete and enhanced, yeah, it would require porting
the compiler to target HLVM/LLVM.

Regards.

-- 
Alp Mestan
http://blog.mestan.fr/
http://alp.developpez.com/

[-- Attachment #2: Type: text/html, Size: 1070 bytes --]

Re: [Caml-list] HLVM...

[Richard Jones]

On Sun, Sep 27, 2009 at 03:09:02PM -0700, David McClain wrote:
> ... remember too, in signal and image processing applications,  
> converting to raw machine integers and plowing ahead is often  
> counterproductive.
> 
> Rather we need saturating arithmetic to avoid abrupt transitions on  
> overflow conditions, or modulo addressing. Neither of these is native  
> to SSM, and have to be synthesized. DSP chips on the other hand almost  
> always offer these variations implicitly or explicitly.

Please confine messages about HLVM to one thread, and don't
start a new thread for every message you post.

Rich.

-- 
Richard Jones
Red Hat

Re: [Caml-list] HLVM...

[Jon Harrop]

On Sunday 27 September 2009 23:09:02 David McClain wrote:
> ... remember too, in signal and image processing applications,
> converting to raw machine integers and plowing ahead is often
> counterproductive.
>
> Rather we need saturating arithmetic to avoid abrupt transitions on
> overflow conditions, or modulo addressing. Neither of these is native
> to SSM, and have to be synthesized. DSP chips on the other hand almost
> always offer these variations implicitly or explicitly.

Sure. That does not change the fact that unnecessarily boxing these primitive 
types severely degrades performance.

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

Re: [Caml-list] HLVM

[Jon Harrop]

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