[Caml-list] AST versus Ocaml
Jan Kybic
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 <ky...@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
Kevin Cheung
it is as fast as it claims to be, then it might do what Jon Harrop is
trying to achieve with HLVM.
Kevin.
malc
> 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
>
>
--
mailto:av1...@comtv.ru
Jan Kybic
>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.
Jon Harrop
> > 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
Jan Kybic
> 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 <ky...@fel.cvut.cz> tel. +420 2 2435 5721
http://cmp.felk.cvut.cz/~kybic ICQ 200569450
_______________________________________________
Jon Harrop
> > 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
_______________________________________________
Jan Kybic
>> > 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 <ky...@fel.cvut.cz> tel. +420 2 2435 5721
http://cmp.felk.cvut.cz/~kybic ICQ 200569450
_______________________________________________
Sylvain Le Gall
>> 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
Mauricio Fernandez
> 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
Jan Kybic
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 <ky...@fel.cvut.cz> tel. +420 2 2435 5721
http://cmp.felk.cvut.cz/~kybic ICQ 200569450
_______________________________________________
Jacques Garrigue
>>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
Jon Harrop
> >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
_______________________________________________