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.
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.
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.
> 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.
> 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.
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:
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:
> 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?
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.
> 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).
>> 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).
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).
>>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.
