AST versus Ocaml

AST versus Ocaml

[Jan Kybic]

Dear all,

I am an Ocaml user but execution speed is very important for me, so I am
constantly looking for ways to make my programs faster, if possible
without sacrificing the high-level language benefits (genericity,
garbage collection, safety).  I have just come across a language
called AST (http://www.ats-lang.org/) which claims to be functional,
based on ML (or Ocaml), and at the same time very efficient, perhaps
as efficient as C. (AST has some other features (theorem proving)
which I cannot fully appreciate at the moment.)

Some of the benchmarks definitely seem to support the speed claim,
others are more suspicious as they are actually partly coded in C.

Before devoting more time to investigating AST, I wanted to ask if you
perhaps already have some experience with this language and can make a
comparison to Ocaml. I have already observed that the type inference
seems to be weaker in AST so the function types have to be explicitely
given. 

Thank you for your comments.

Jan

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

Re: [Caml-list] AST versus Ocaml

[Kevin Cheung]

Unfortunately, I don't have much to say about AST at the moment.  But if 
it is as fast as it claims to be, then it might do what Jon Harrop is 
trying to achieve with HLVM.

Kevin.

On Wed, 4 Nov 2009, Jan Kybic wrote:

> I am an Ocaml user but execution speed is very important for me, so I am
> constantly looking for ways to make my programs faster, if possible
> without sacrificing the high-level language benefits (genericity,
> garbage collection, safety).  I have just come across a language
> called AST (http://www.ats-lang.org/) which claims to be functional,
> based on ML (or Ocaml), and at the same time very efficient, perhaps
> as efficient as C. (AST has some other features (theorem proving)
> which I cannot fully appreciate at the moment.)
>
> Some of the benchmarks definitely seem to support the speed claim,
> others are more suspicious as they are actually partly coded in C.
>
> Before devoting more time to investigating AST, I wanted to ask if you
> perhaps already have some experience with this language and can make a
> comparison to Ocaml. I have already observed that the type inference
> seems to be weaker in AST so the function types have to be explicitely
> given.
>
> Thank you for your comments.
>
> Jan
>
> -- 
> -------------------------------------------------------------------------
> Jan Kybic <kybic@fel.cvut.cz>                       tel. +420 2 2435 5721
> http://cmp.felk.cvut.cz/~kybic                      ICQ 200569450
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>

Re: [Caml-list] AST versus Ocaml

[malc]

On Wed, 4 Nov 2009, Jan Kybic wrote:

> Dear all,
> 
> I am an Ocaml user but execution speed is very important for me, so I am
> constantly looking for ways to make my programs faster, if possible
> without sacrificing the high-level language benefits (genericity,
> garbage collection, safety).  I have just come across a language
> called AST (http://www.ats-lang.org/) which claims to be functional,
> based on ML (or Ocaml), and at the same time very efficient, perhaps
> as efficient as C. (AST has some other features (theorem proving)
> which I cannot fully appreciate at the moment.)
> 
> Some of the benchmarks definitely seem to support the speed claim,
> others are more suspicious as they are actually partly coded in C.

http://www.reddit.com/r/programming/comments/72hmw/language_shootout_ats_is_the_new_top_gunslinger/c05iq0a

> 
> Before devoting more time to investigating AST, I wanted to ask if you
> perhaps already have some experience with this language and can make a
> comparison to Ocaml. I have already observed that the type inference
> seems to be weaker in AST so the function types have to be explicitely
> given. 
> 
> Thank you for your comments.
> 
> Jan
> 
> 

-- 
mailto:av1474@comtv.ru

Re: [Caml-list] AST versus Ocaml

[Jan Kybic]

>  Shivkumar Chandrasekara said:
>I switched from OCaml to ATS for numerical computations. I did this
>because I was thinking of switching to some low-level language anyway
>(for efficiency). I think ATS is a good fit for OCaml types who also
>want low-level control of memory and CPU. (You can always turn on the
>GC in ATS and code in an OCaml-like fashion if you wish.)

Thank you, that sounds very encouraging. So are you saying that if you
turn on the GC in ATS, the performance is not so different?

And yes, I misspelled the name, the correct one is ATS, I am sorry.

> Kevin Cheung said:
> Unfortunately, I don't have much to say about AST at the moment.  But
> if it is as fast as it claims to be, then it might do what Jon Harrop
> is trying to achieve with HLVM.

Yes, exactly, fast Ocaml based on HLVM would be ideal. However
HLVM+Ocaml is probably still years away, while ATS can be used right
now.

Jan

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

Re: [Caml-list] AST versus Ocaml

[Jon Harrop]

On Wednesday 04 November 2009 15:42:42 Jan Kybic wrote:
> >  Shivkumar Chandrasekara said:
> >I switched from OCaml to ATS for numerical computations. I did this
> >because I was thinking of switching to some low-level language anyway
> >(for efficiency). I think ATS is a good fit for OCaml types who also
> >want low-level control of memory and CPU. (You can always turn on the
> >GC in ATS and code in an OCaml-like fashion if you wish.)
>
> Thank you, that sounds very encouraging. So are you saying that if you
> turn on the GC in ATS, the performance is not so different?

I haven't found the time to give ATSLang a serious test drive but I had a 
brief conversation with Hongwei Xi about his work and goals. He is into 
systems programming, which is closely related to high performance programming 
in the context of serial code but foundations for easy parallel programming 
are missing. I don't know what the state of ATS' memory model is so things 
like non-blocking algorithms might be tricky. Another concern is that ATS' 
code gen goes via GCC and GCC is quite a sucky compiler with poor compilation 
times, poor generated code and, of course, missing features like tail calls 
requiring elaborate and usually slow and uninteroperable workarounds. ATS 
also lacks a performant REPL, a build system, DLLs and package management. I 
don't know what the state of editors/IDEs is.

Given that ATSLang uses the Boehm GC, my main concerns would be about leaks 
and crashes rather than performance. Moreover, I would note that the 
performant ATS code out there seems to go to *great* lengths to avoid the GC 
whenever possible, so I suspect it is extremely slow in the context of 
heavily allocating code or many short-lived values (much like HLVM). For 
example, binary trees:

http://shootout.alioth.debian.org/u64q/benchmark.php?test=binarytrees&lang=ats&id=2#about

OCaml:  58 LOC
C:     122 LOC
ATS:   191 LOC

My guess is that safe ATS code will be slow if it allocates much. Also, I 
don't know how well its allocator scales across multiple threads.

> > Kevin Cheung said:
> > Unfortunately, I don't have much to say about AST at the moment.  But
> > if it is as fast as it claims to be, then it might do what Jon Harrop
> > is trying to achieve with HLVM.
>
> Yes, exactly, fast Ocaml based on HLVM would be ideal. However
> HLVM+Ocaml is probably still years away...

My vision for the OCaml+HLVM combo is the ability to use HLVM from your OCaml 
projects to generate and execute high performance parallel numerical code 
on-the-fly.

Hopefully I'll be implementing HLVM's first concurrent GC soon, based upon the 
following VCGC design:

  http://doc.cat-v.org/inferno/concurrent_gc/

In the meantime, you can still use HLVM to generate serial numerical code that 
is typically 2-3x faster than the equivalent OCaml code.

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

Re: [Caml-list] AST versus Ocaml

[Jan Kybic]

> I haven't found the time to give ATSLang a serious test drive but I had a 
> brief conversation with Hongwei Xi about his work and goals. He is into 
> systems programming, which is closely related to high performance programming 
> in the context of serial code but foundations for easy parallel programming 
> are missing. 

Jon, thank you for your comments. Parallel programming support through
threads is not a showstopper for me - my problems can usually be
parallelized easily using processes or via message passing (on a cluster).

> like non-blocking algorithms might be tricky. Another concern is that ATS' 
> code gen goes via GCC and GCC is quite a sucky compiler with poor compilation 

I am not worried about that either, I have been living happily with
gcc for a long time and if needed, I imagine that the code can be
compiled by another C compiler.

> and crashes rather than performance. Moreover, I would note that the 
> performant ATS code out there seems to go to *great* lengths to avoid the GC 
> whenever possible, so I suspect it is extremely slow in the context of 
> heavily allocating code or many short-lived values (much like HLVM). For 

This will be easy to test.

> My vision for the OCaml+HLVM combo is the ability to use HLVM from your OCaml 
> projects to generate and execute high performance parallel numerical code 
> on-the-fly.

So you do not plan to write a full compiler for Ocaml with HLVM
output?  That would be disappointing. I must say, I do not have much need to
generate and execute code on the fly. I was hoping that Ocaml+HLVM
would allow me to write a more generic code without the performance
penalty it now incurs.

> In the meantime, you can still use HLVM to generate serial numerical code that 
> is typically 2-3x faster than the equivalent OCaml code.

Yes, but if I understand correctly, the language you can use for that
is rather restricted. If I write a code like that (no polymorphic
functions, no functors, no objects), Ocaml is already fast enough for
me. And are you not better off using for example MetaOcaml with
offshoring to C?

Yours,

Jan

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

Re: [Caml-list] AST versus Ocaml

[Jon Harrop]

On Wednesday 04 November 2009 22:21:24 Jan Kybic wrote:
> > and crashes rather than performance. Moreover, I would note that the
> > performant ATS code out there seems to go to *great* lengths to avoid the
> > GC whenever possible, so I suspect it is extremely slow in the context of
> > heavily allocating code or many short-lived values (much like HLVM). For
>
> This will be easy to test.

I'd like to know what you find in this respect.

> > My vision for the OCaml+HLVM combo is the ability to use HLVM from your
> > OCaml projects to generate and execute high performance parallel
> > numerical code on-the-fly.
>
> So you do not plan to write a full compiler for Ocaml with HLVM
> output?

Correct.

> That would be disappointing.

There are two main problems:

1. The OCaml compiler is a very old school design that strips out essential 
information (e.g. untyped IRs) early in the compilation process.

2. Some obscure features of the OCaml language (e.g. polymorphic recursion) 
cannot be fitted into an HLVM-like infrastructure easily.

> I must say, I do not have much need  
> to generate and execute code on the fly. I was hoping that Ocaml+HLVM would
> allow me to write a more generic code without the performance penalty it
> now incurs.

That's the idea.

> > In the meantime, you can still use HLVM to generate serial numerical code
> > that is typically 2-3x faster than the equivalent OCaml code.
>
> Yes, but if I understand correctly, the language you can use for that
> is rather restricted.

Currently, yes. The main restriction is the lack of global variables. The main 
productivity feature is the lack of a front-end language with a decent syntax 
and type inference.

> If I write a code like that (no polymorphic functions, no functors, no
> objects), 

Polymorphism is easily implemented by parameterising your HLVM code 
definitions over the types they use. For example, HLVM's own source code 
already included several "polymorphic" definitions such as filling in the 
elements of an array of any element type.

Functors and objects are a long way off.

I intend to get parallelism working first and then go back and finish a simple 
ML front-end for HLVM.

> Ocaml is already fast enough for me. And are you not better off using for
> example MetaOcaml with offshoring to C?

I did some experiments with MetaOCaml. Firstly, it is x86 only and not x64 
which means poor floating-point performance, many times slower than HLVM's. 
The language itself is also very restrictive, e.g. you cannot generate 
pattern matches dynamically so you cannot leverage the pattern match 
compiler, which is a huge loss. In essence, effective use of MetaOCaml 
requires writing in continuation passing style which OCaml and, therefore, 
MetaOCaml do not handle well (closure invocations are slow in OCaml and CPS 
is not optimized back into anything sane). So I do not consider MetaOCaml to 
be a viable option for performance users.

But the motivation for HLVM's JIT compilation is not metaprogramming like 
MetaOCaml but, rather, to build a performant REPL.

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

Re: [Caml-list] ATS versus Ocaml

[Jan Kybic]

> On Wednesday 04 November 2009 22:21:24 Jan Kybic wrote:
>> > and crashes rather than performance. Moreover, I would note that the
>> > performant ATS code out there seems to go to *great* lengths to avoid the
>> > GC whenever possible, so I suspect it is extremely slow in the context of
>> > heavily allocating code or many short-lived values (much like HLVM). For
>>
>> This will be easy to test.
>
> I'd like to know what you find in this respect.

Here are my preliminary results. Please note that I am a beginner in
ATS so my ATS code is rather ugly. But it is  a more or less direct
translation from Ocaml. I imagine the ATS results can be improved. 
I have asked at the ATS list about that.

I have implemented two benchmarks:

- eight queens, I actually used ten. I believe the original Ocaml
  implementation was probably yours. It uses lists as a primary
  structure, so there is a lot of allocations. On this task, ATS needs
  about 50% more time than Ocaml.

- bubble sort on an array of doubles. Here ATS is more than 10 times
  faster than Ocaml (for n=10000).

My code can be found at http://cmp.felk.cvut.cz/~kybic/share/ats_tests.zip

Jan

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

Re: ATS versus Ocaml

[Sylvain Le Gall]

On 06-11-2009, Jan Kybic <kybic@fel.cvut.cz> wrote:
>> On Wednesday 04 November 2009 22:21:24 Jan Kybic wrote:
>>> > and crashes rather than performance. Moreover, I would note that the
>>> > performant ATS code out there seems to go to *great* lengths to avoid the
>>> > GC whenever possible, so I suspect it is extremely slow in the context of
>>> > heavily allocating code or many short-lived values (much like HLVM). For
>>>
>>> This will be easy to test.
>>
>> I'd like to know what you find in this respect.
>
> Here are my preliminary results. Please note that I am a beginner in
> ATS so my ATS code is rather ugly. But it is  a more or less direct
> translation from Ocaml. I imagine the ATS results can be improved. 
> I have asked at the ATS list about that.
>
> I have implemented two benchmarks:
>
> - eight queens, I actually used ten. I believe the original Ocaml
>   implementation was probably yours. It uses lists as a primary
>   structure, so there is a lot of allocations. On this task, ATS needs
>   about 50% more time than Ocaml.
>
> - bubble sort on an array of doubles. Here ATS is more than 10 times
>   faster than Ocaml (for n=10000).
>

Are you using amd64 architecture ?

Regards,
Sylvain Le Gall

Re: [Caml-list] ATS versus Ocaml

[Mauricio Fernandez]

On Fri, Nov 06, 2009 at 12:48:56PM +0100, Jan Kybic wrote:
> I have implemented two benchmarks:
> 
> - eight queens, I actually used ten. I believe the original Ocaml
>   implementation was probably yours. It uses lists as a primary
>   structure, so there is a lot of allocations. On this task, ATS needs
>   about 50% more time than Ocaml.
> 
> - bubble sort on an array of doubles. Here ATS is more than 10 times
>   faster than Ocaml (for n=10000).
>
> My code can be found at http://cmp.felk.cvut.cz/~kybic/share/ats_tests.zip

I notice that in ATS you have to give the type of the array explicitly

  fn bubble_sort (a : array0 double ) : void =

so you should also do so in the OCaml code, using

  let bubble_sort (a : float array) =

instead of 

  let bubble_sort a

This makes the OCaml bsort over 13 times faster here (1.75 vs 0.13s).

Do you know if ATS is performing array bound checking? The OCaml code is
nearly 2X faster with -unsafe than without.

-- 
Mauricio Fernandez  -   http://eigenclass.org

Re: [Caml-list] Re: ATS versus Ocaml

[Jan Kybic]

>I notice that in ATS you have to give the type of the array explicitly

  fn bubble_sort (a : array0 double ) : void =

> so you should also do so in the OCaml code, using

You are right, I am sorry for this omission. Having done that, the
ration between Ocaml and ATS times drops to 3:1 (Ocaml being slower).

>Do you know if ATS is performing array bound checking? The OCaml code is
>nearly 2X faster with -unsafe than without.

Yes, I think the ATS code does perform bound checking. There is
probably a way to avoid it but I do not know how to do it yet.

With "ocamlopt -unsafe", the ratio drops further to 2:1 

> Are you using amd64 architecture ?

No. Standard Intel x86.

Jan

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

Re: [Caml-list] Re: ATS versus Ocaml

[Jacques Garrigue]

From: Jan Kybic <kybic@fel.cvut.cz>
>>Do you know if ATS is performing array bound checking? The OCaml code is
>>nearly 2X faster with -unsafe than without.
> 
> Yes, I think the ATS code does perform bound checking. There is
> probably a way to avoid it but I do not know how to do it yet.

The whole point of ATS is to use a richer type system to avoid many
runtime checks. Static check of bounds is supposedly one of them.
If your program is written with the clever .<n>. annotations (I don't
remember the exact syntax), then there should be no bound checks at
runtime.
Not that this is not equivalent to ocaml's -unsafe: the program is
still safe, since the checks were done at compile time.

Jacques Garrigue

Re: [Caml-list] Re: ATS versus Ocaml

[Jon Harrop]

On Friday 06 November 2009 15:38:27 Jan Kybic wrote:
> >I notice that in ATS you have to give the type of the array explicitly
>
>   fn bubble_sort (a : array0 double ) : void =
>
> > so you should also do so in the OCaml code, using
>
> You are right, I am sorry for this omission. Having done that, the
> ration between Ocaml and ATS times drops to 3:1 (Ocaml being slower).

On x86, I get:

ATS:   0.189s
HLVM:  0.486s
OCaml: 0.552s

On x64, I get:

OCaml: 0.299s

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