HLVM is now garbage collected!

HLVM is now garbage collected!

[Jon Harrop]

Well, I have my first working GC running in HLVM now! Woohoo!

The implementation has some interesting properties:

. The GC is written entirely in HLVM's own intermediate language.

. When a new type is defined a new function to traverse that type is JIT 
compiled. So code for the GC is generated on-the-fly.

. The GC is very simple and uses a shadow stack to track roots and an 
allocated list that stores all heap allocated locations and their mark bit.

. When the GC gets involved, performance is currently awful. Two simple 
optimizations will go a long way to curing this: touch the shadow stack only 
when necessary, and do something cleverer than the current linear lookup (!) 
of allocated pointers in the GC.

. When the heap is deep the current GC stack overflows because it is not tail 
recursive. This is easily fixed.

I have applied to the OCaml Forge to create a new project for HLVM where I 
will upload my initial prototype. Just as soon as my French gets good enough 
to understand this automated e-mail... ;-)

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

Re: [Caml-list] HLVM is now garbage collected!

[Jon Harrop]

On Sunday 08 March 2009 01:19:20 Jon Harrop wrote:
> I have applied to the OCaml Forge to create a new project for HLVM where I
> will upload my initial prototype.

The OCaml Forge has kindly accepted to host the HLVM project:

  http://hlvm.forge.ocamlcore.org

If you are interested in following, discussing or contributing to this project 
please join me on the hlvm-list:

  http://lists.forge.ocamlcore.org/cgi-bin/mailman/listinfo/hlvm-list

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

Re: [Caml-list] HLVM is now garbage collected!

[Richard Jones]

On Sun, Mar 08, 2009 at 02:45:41AM +0000, Jon Harrop wrote:
> On Sunday 08 March 2009 01:19:20 Jon Harrop wrote:
> > I have applied to the OCaml Forge to create a new project for HLVM where I
> > will upload my initial prototype.
> 
> The OCaml Forge has kindly accepted to host the HLVM project:
> 
>   http://hlvm.forge.ocamlcore.org

There's no license information in the repository or in any of the
files.  Without that, technically even looking at the software is
dangerous, and it can't be copied.  What's the license for this?

Rich.

-- 
Richard Jones
Red Hat

Re: [Caml-list] HLVM is now garbage collected!

[Jon Harrop]

On Sunday 08 March 2009 09:35:42 Richard Jones wrote:
> On Sun, Mar 08, 2009 at 02:45:41AM +0000, Jon Harrop wrote:
> > On Sunday 08 March 2009 01:19:20 Jon Harrop wrote:
> > > I have applied to the OCaml Forge to create a new project for HLVM
> > > where I will upload my initial prototype.
> >
> > The OCaml Forge has kindly accepted to host the HLVM project:
> >
> >   http://hlvm.forge.ocamlcore.org
>
> There's no license information in the repository or in any of the
> files.  Without that, technically even looking at the software is
> dangerous, and it can't be copied.  What's the license for this?

I think "dangerous" is overly excessive. ;-)

I've gone for a 2-clause BSD license which is listed on the Forge and the 
document is now in the SVN repo as well.

I've also classified this as an alpha release. Once I've fixed the bugs that I 
know about I'll move it up into a beta release.

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

HLVM numerical performance

[Jan Kybic]

> The OCaml Forge has kindly accepted to host the HLVM project:
>
>   http://hlvm.forge.ocamlcore.org
>>

Hello. Just out of curiosity: 

I recall reading that one of your priorities for HLVM is
performance of numerical code. Does it mean that you expect numerical
code to run faster than natively compiled (with ocamlopt) Ocaml?
Do you have any experiments so far to support this?

I am doing large scale numerical calculations in Ocaml and performance
is always an issue for me.

Thank you for your effort.

Yours,

Jan  


-- 
-------------------------------------------------------------------------
Jan Kybic <kybic@fel.cvut.cz>                       tel. +420 2 2435 5721
http://cmp.felk.cvut.cz/~kybic                      ICQ 200569450

Re: [Caml-list] HLVM numerical performance

[Jon Harrop]

On Monday 09 March 2009 09:04:57 Jan Kybic wrote:
> > The OCaml Forge has kindly accepted to host the HLVM project:
> >
> >   http://hlvm.forge.ocamlcore.org
>
> Hello. Just out of curiosity:
>
> I recall reading that one of your priorities for HLVM is performance of
> numerical code. 

HLVM aspires to provide the following benefits over OCaml:

. High performance numerics (often 2-4x faster than OCaml on x86).

. High performance polymorphism: polymorphic definitions are instantiated for 
different types.

. More numeric types (float32, complexes, low-dimensional vectors and 
matrices).

. More optimizations for the benefit of numerical computing: common 
subexpression elimination, hoisting of loop invariants, inlining of function 
arguments to higher-order functions.

. Faster and easier FFI for external libraries like FFTW and LAPACK.

. Dynamic capabilities such as generic printing, hashing, comparison, 
serialization and run-time type information.

. Community led development: you can contribute to the open source HLVM code 
base.

. Commerce friendly design so it will be viable for you to buy and sell 
libraries written for HLVM.

. A common language run-time so you can safely consume and produce libraries 
written in any languages with implementations that target HLVM.

> Does it mean that you expect numerical code to run faster than natively
> compiled (with ocamlopt) Ocaml? 

Absolutely. Most numerical code already runs a lot faster in HLVM than it does 
in ocamlopt if you disable GC in any inner loops that act upon arrays. In the 
future, I expect HLVM to be a lot faster still because it will generate SSE 
instructions (using LLVM's vector intrinsics) and perform many optimizations 
of its own (such as hoisting the GC code automatically).

> Do you have any experiments so far to support this?

Yes. The "test.ml" file from the HLVM subversion repository contains over 500 
lines of test code that includes a few simple benchmarks. Here is a 
comparison of the performance of ordinary OCaml with the best performance I 
have been able to obtain using HLVM:

Float Fibonacci (recursive floating point functions)
OCaml: 6.10s
HLVM:  1.74s  3.5x faster than ocamlopt

Mandelbrot (complex arithmetic)
OCaml: 4.39s
HLVM:  1.89s  2.3x faster than ocamlopt

Sieve of Eratosthenes (int arrays)
OCaml: 14.9s  (had to use big arrays)
HLVM:  7.05s  2.1x faster than ocamlopt

As you can see HLVM is already generating much faster code than ocamlopt. Note 
that the OCaml code can be improved (e.g. by avoiding OCaml's complex number 
type) but the point is that idiomatic code is much faster with HLVM.

> I am doing large scale numerical calculations in Ocaml and performance
> is always an issue for me.

A lot of people have adopted OCaml for number crunching and string munging 
(bioinformatics). Although ocamlopt is an excellent compiler, HLVM has shown 
that it is possible to do much better still. I hope HLVM will form the 
backbone of an OCaml variant designed specifically for technical computing.

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

Re: [Caml-list] HLVM numerical performance

[Jon Harrop]

On Monday 09 March 2009 11:37:52 Jon Harrop wrote:
> HLVM aspires to provide the following benefits over OCaml:

I forgot the second most important goal (!):

. Easy and efficient parallelism to leverage multicores.

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

Re: [Caml-list] HLVM is now garbage collected!

[Richard Jones]

On Mon, Mar 09, 2009 at 04:13:11AM +0000, Jon Harrop wrote:
> On Sunday 08 March 2009 09:35:42 Richard Jones wrote:
> > On Sun, Mar 08, 2009 at 02:45:41AM +0000, Jon Harrop wrote:
> > > On Sunday 08 March 2009 01:19:20 Jon Harrop wrote:
> > > > I have applied to the OCaml Forge to create a new project for HLVM
> > > > where I will upload my initial prototype.
> > >
> > > The OCaml Forge has kindly accepted to host the HLVM project:
> > >
> > >   http://hlvm.forge.ocamlcore.org
> >
> > There's no license information in the repository or in any of the
> > files.  Without that, technically even looking at the software is
> > dangerous, and it can't be copied.  What's the license for this?
> 
> I think "dangerous" is overly excessive. ;-)
> 
> I've gone for a 2-clause BSD license which is listed on the Forge and the 
> document is now in the SVN repo as well.

Thanks Jon, that's excellent news.

Rich.

-- 
Richard Jones
Red Hat

Re: [Caml-list] HLVM is now garbage collected!

[Joel Reymont]

On Mar 8, 2009, at 2:45 AM, Jon Harrop wrote:

> The OCaml Forge has kindly accepted to host the HLVM project:
>
>  http://hlvm.forge.ocamlcore.org


Am I the only one who VASTLY prefers the clean, uncluttered and easy  
to use GitHub interface to the *Forge one?

---
http://tinyco.de
Mac, C++, OCaml

Re: HLVM is now garbage collected!

[Sylvain Le Gall]

Hello,

On 08-03-2009, Joel Reymont <joelr1@gmail.com> wrote:
>
> On Mar 8, 2009, at 2:45 AM, Jon Harrop wrote:
>
>> The OCaml Forge has kindly accepted to host the HLVM project:
>>
>>  http://hlvm.forge.ocamlcore.org
>
>
> Am I the only one who VASTLY prefers the clean, uncluttered and easy  
> to use GitHub interface to the *Forge one?
>

AFAIK, Github host only git repository. Forge.ocamlcore.org not only
host repository but also mailing-list, bug tracker and file section. 

Moreover, hlvm is a SVN repository which makes github a non-sense for
this project. 

We do also have a git repository for projects (git.ocamlcore.org) though
not as shiny as github.

If you do prefer github for your repository, you can of course host BTS,
mailing-list and files section on forge.ocamlcore.org and your git
repository on github. There is nothing that prevent it. 

The purpose of forge.ocamlcore.org is to have a more central point for
OCaml projects, giving visibility to OCaml community 

Regards,
Sylvain Le Gall

Re: HLVM is now garbage collected!

[Sylvain Le Gall]

On 08-03-2009, Sylvain Le Gall <sylvain@le-gall.net> wrote:
> Hello,
>
> On 08-03-2009, Joel Reymont <joelr1@gmail.com> wrote:
>>
>> On Mar 8, 2009, at 2:45 AM, Jon Harrop wrote:
>>
>>> The OCaml Forge has kindly accepted to host the HLVM project:
>>>
>>>  http://hlvm.forge.ocamlcore.org
>>
>>
>> Am I the only one who VASTLY prefers the clean, uncluttered and easy  
>> to use GitHub interface to the *Forge one?
>>
>
> AFAIK, Github host only git repository. Forge.ocamlcore.org not only
> host repository but also mailing-list, bug tracker and file section. 
>

Looking more closely, it seems there is Downloads/Wiki and some stats.
Though it remains git-centric and not particularly OCaml related (only 2
repository seems to be related to OCaml). 

Github seems to have evolve since last time I take a look at it...
(toward more *forge features)

> If you do prefer github for your repository, you can of course host BTS,
> mailing-list and files section on forge.ocamlcore.org and your git
> repository on github. There is nothing that prevent it. 
>
> The purpose of forge.ocamlcore.org is to have a more central point for
> OCaml projects, giving visibility to OCaml community 
>

This point is still very important, giving visibility to OCaml community
is to my mind the best thing to do. Having multiple project hosted
everywhere just "dilute" OCaml in more mainstream language projects. 

Regards,
Sylvain Le Gall

Re: [Caml-list] HLVM is now garbage collected!

[Jon Harrop]

On Sunday 08 March 2009 09:43:37 Joel Reymont wrote:
> On Mar 8, 2009, at 2:45 AM, Jon Harrop wrote:
> > The OCaml Forge has kindly accepted to host the HLVM project:
> >
> >  http://hlvm.forge.ocamlcore.org
>
> Am I the only one who VASTLY prefers the clean, uncluttered and easy
> to use GitHub interface to the *Forge one?

I haven't tried GitHub but the OCamlForge is really rather cool.

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

Re: [Caml-list] HLVM is now garbage collected!

[Jon Harrop]

On Sunday 08 March 2009 01:19:20 Jon Harrop wrote:
> Well, I have my first working GC running in HLVM now! Woohoo!

I have just updated HLVM's GC to use a hash table instead of a linear search 
of the allocated list. This brings GC time down from O(n^2) to amortized 
O(n). In practice, the benchmarks are up to 100x faster than they were and, 
in the worst case, HLVM is now only 5x slower than OCaml.

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

Re: [Caml-list] HLVM is now garbage collected!

[Mikkel Fahnøe Jørgensen]

2009/3/13 Jon Harrop <jon@ffconsultancy.com>:
> On Sunday 08 March 2009 01:19:20 Jon Harrop wrote:
>> Well, I have my first working GC running in HLVM now! Woohoo!
>
> I have just updated HLVM's GC to use a hash table instead of a linear search
> of the allocated list. This brings GC time down from O(n^2) to amortized
> O(n). In practice, the benchmarks are up to 100x faster than they were and,
> in the worst case, HLVM is now only 5x slower than OCaml.

Keep up the good work.

I'm still a bit worried about that 60MB runtime though ...

Are you looking into trace trees for JIT?

Mikkel

Re: [Caml-list] HLVM is now garbage collected!

[Jon Harrop]

On Friday 13 March 2009 20:40:10 Mikkel Fahnøe Jørgensen wrote:
> 2009/3/13 Jon Harrop <jon@ffconsultancy.com>:
> > On Sunday 08 March 2009 01:19:20 Jon Harrop wrote:
> >> Well, I have my first working GC running in HLVM now! Woohoo!
> >
> > I have just updated HLVM's GC to use a hash table instead of a linear
> > search of the allocated list. This brings GC time down from O(n^2) to
> > amortized O(n). In practice, the benchmarks are up to 100x faster than
> > they were and, in the worst case, HLVM is now only 5x slower than OCaml.
>
> Keep up the good work.
>
> I'm still a bit worried about that 60MB runtime though ...

I was wrong about that actually. It was only 60Mb because I had compiled LLVM 
with debugging on. Now that I have LLVM 2.5 compiled for release my HLVM 
executable is under 10Mb. Still large but I'm happy with that.

> Are you looking into trace trees for JIT?

You mean for the code fed into HLVM? No, not yet. We need more code to feed 
into it before that will become interesting!

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