[Caml-list] Google summer of Code proposal
Andrey Riabushenko
It is not mistake, in spite of ocaml does not take part in GSoC 2009, but
ocaml community still can benefit from it.
I would like to develop LLVM frontend to Ocaml language. LLVM does
participate in GSoC. LLVM do not mind to developed a ocaml frontend as LLVM
GSoC project. I want to discuss details with you before I will make an
official proposal to LLVM.
1.What is the best way to make ocaml frontend on your opinion?
I think the best would to way to develop ocaml llvm front end as a part of
ocaml distribution. I don't not want to develop yet another a separate
project, which is half-done llvm frontend that nobody uses. There are plenty
of those for other languages lying around. I propose to forget about JIT
capabilities of LLVM and concentrate on AOT compilation for now.
Ocamlopt currently generates native assembler for the following platforms:
i386, AMD64, ia64, arm, hppa, alpha, m68k, mips, powerpc, sparc assembler.
I propose to add LLVM assembler generation as another platform to ocamlopt. It
requires the least modification of ocaml source and easy to maintain. LLVM
will give ocaml an aggressive whole program optimizer and will make possible
to run ocaml on new platforms that are supported by LLVM, but not yet by
Ocaml.
Question to the Ocaml creators and maintainers.
2. Will you merge LLVM platform to the ocaml trunk assuming that it works as
it should?
Andrey Riabushenko
PhD student,
Faculty of applied mathematics
National technical university of Ukraine "KPI"
http://kpi.ua/en/
_______________________________________________
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
Seo Sanghyeon
> I would like to develop LLVM frontend to Ocaml language. LLVM does
> participate in GSoC. LLVM do not mind to developed a ocaml frontend as LLVM
> GSoC project. I want to discuss details with you before I will make an
> official proposal to LLVM.
Very cool!
> I think the best would to way to develop ocaml llvm front end as a part of
> ocaml distribution. I don't not want to develop yet another a separate
> project, which is half-done llvm frontend that nobody uses. There are plenty
> of those for other languages lying around. I propose to forget about JIT
> capabilities of LLVM and concentrate on AOT compilation for now.
This sounds reasonable.
> Ocamlopt currently generates native assembler for the following platforms:
> i386, AMD64, ia64, arm, hppa, alpha, m68k, mips, powerpc, sparc assembler.
> I propose to add LLVM assembler generation as another platform to ocamlopt. It
> requires the least modification of ocaml source and easy to maintain.
One interesting problem may be that LLVM assembler is typed, while other
assemblers are not.
> LLVM
> will give ocaml an aggressive whole program optimizer and will make possible
> to run ocaml on new platforms that are supported by LLVM, but not yet by
> Ocaml.
Is there any such platform?
> 2. Will you merge LLVM platform to the ocaml trunk assuming that it works as
> it should?
I think it should be (assuming you or someone will continue to maintain it),
but I am in no position to answer this.
--
Seo Sanghyeon
Jon Harrop
> Hi OCaml hackers,
>
> It is not mistake, in spite of ocaml does not take part in GSoC 2009, but
> ocaml community still can benefit from it.
>
> I would like to develop LLVM frontend to Ocaml language. LLVM does
> participate in GSoC. LLVM do not mind to developed a ocaml frontend as LLVM
> GSoC project. I want to discuss details with you before I will make an
> official proposal to LLVM.
I recommend you peruse the LLVM and HLVM mailing lists for information about
current work along similar lines:
http://hlvm.forge.ocamlcore.org
> 1. What is the best way to make ocaml frontend on your opinion?
The impedance mismatch between the current OCaml compilers and LLVM is high:
The OCaml compilers remove type information in the early stages of
compilation but LLVM is a typed assembler and needs that information to be
conveyed all the way through to the back end.
The OCaml compilers make no attempt to provide reusable intermediate
representations.
So you will probably end up hacking extensively on ocamlopt's internals and,
consequently, your code will be bound by the QPL license even though you will
probably not salvage much. This is why I started from scratch.
> I think the best would to way to develop ocaml llvm front end as a part of
> ocaml distribution. I don't not want to develop yet another a separate
> project, which is half-done llvm frontend that nobody uses. There are
> plenty of those for other languages lying around. I propose to forget about
> JIT capabilities of LLVM and concentrate on AOT compilation for now.
JIT is the single most important benefit of LLVM in the context of OCaml. With
JIT:
You can instantiate polymorphic definitions for each combination of type
parameters that they are used with, providing substantial performance
improvements.
You can generate code that is optimized for the current machine.
You can provide a performant top-level.
Forgetting about JIT would certainly be a mistake.
> Ocamlopt currently generates native assembler for the following platforms:
> i386, AMD64, ia64, arm, hppa, alpha, m68k, mips, powerpc, sparc assembler.
> I propose to add LLVM assembler generation as another platform to ocamlopt.
> It requires the least modification of ocaml source and easy to maintain.
There are many problems with this:
You will succumb to ocamlopt's current run-time representation which is
objectively inefficient (e.g. boxing floats, tuples, records) and was only
chosen because the compiler lacks capabilities that LLVM already provides for
you (primarily JIT compilation).
LLVM's optimization passes will not optimize the representations and,
consequently, performance will not be improved.
You will inherit ocamlopt's most serious flaws: its run-time and its FFI.
If you inherit ocamlopt's run-time then you will need to be able to generate
compliant code from LLVM which is extremely difficult, error prone and almost
entirely untested.
> LLVM will give ocaml an aggressive whole program optimizer...
I doubt you could even match the performance of OCaml's existing compiler with
that approach, much less beat it. There are two reasons for this:
Building upon ocamlopt's internal run-time representation (e.g. boxed
tuples) ties LLVM's hands behind its back when it comes to optimization. LLVM
could do very little to optimize such code.
LLVM's existing optimization passes work great on naively-generated C or C++
code but they know nothing about parametric polymorphism, closures and
pattern matching. These high-level language features are where the most
beneficial optimizations lie.
For example, applying LLVM's optimization passes to HLVM generated code only
give ~15% performance improvements.
> Question to the Ocaml creators and maintainers.
>
> 2. Will you merge LLVM platform to the ocaml trunk assuming that it works
> as it should?
Collaboration with the existing HLVM effort would probably be far more
productive.
--
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e
Andrey Riabushenko
> > LLVM
> > will give ocaml an aggressive whole program optimizer and will make
> > possible to run ocaml on new platforms that are supported by LLVM, but
> > not yet by Ocaml.
>
> Is there any such platform?
>
There are - PIC16, XCore, Cell SPU and Microsoft IL (F# reinvented :).
Many others are under development.
> > 2. Will you merge LLVM platform to the ocaml trunk assuming that it works
> > as it should?
>
> I think it should be (assuming you or someone will continue to maintain
> it), but I am in no position to answer this.
_______________________________________________
Jon Harrop
> > > LLVM
> > > will give ocaml an aggressive whole program optimizer and will make
> > > possible to run ocaml on new platforms that are supported by LLVM, but
> > > not yet by Ocaml.
> >
> > Is there any such platform?
>
> There are - PIC16, XCore, Cell SPU and Microsoft IL (F# reinvented :).
> Many others are under development.
Both OCaml and LLVM support x86, x64 and ARM as well as having backends for
many other architectures that are of questionable quality. For example,
LLVM's CIL backend was broken when I tried it and, of course, it cannot even
support generics because LLVM is incapable of expressing parametric
polymorphism. For OCaml, there is OCamIL for generating CIL but it also does
not support parametric polymorphism because it is for .NET 1.1.
I have been developing with LLVM for many months now and I have had two main
gripes:
1. LLVM calls abort() instead of raising an exception and that makes it almost
impossible to debug LLVM code because it just dies immediately upon hitting
any error and gives only the most convoluted contextless error messages. The
best solution I have found is to litter your LLVM IR emitter with debug
printfs. HLVM overcomes this problem by catching and handling type errors
appropriately, making it much easier to use.
2. Many of LLVM's features sound alluring but turn out to be unusable.
Fortunately, the two core features required to support languages like OCaml
robustly and efficiently (tail calls and first-class structs) are almost
completely working. Most of HLVM's development effort has gone into rejecting
or working around features that do not work correctly in LLVM.
Just to give some examples:
I found that LLVM's x86 backend breaks tail calls when the return type is a
first class struct. The workaround is to use sret form, having the caller
preallocate the return struct and passing a pointer to the struct as an extra
first argument.
Lennart Augustsson found that LLVM's vector intrinsics can generate broken
SSE code for 2D vectors. There is no general workaround: you are expected to
special-case this situation in all front-ends (!).
Many people have written to me because they have been unable to get LLVM's
GC API to work at all. Upon hearing the issues, I immediately opted to use a
shadow stack designed for an uncooperative environment in HLVM. This at least
works but it is needlessly inefficient.
OCaml is vastly superior to C++ for writing compilers but the OCaml bindings
to LLVM are far from complete. HLVM includes its own auxiliary bindings for
many important features such as first-class structs and enabling tail calls.
LLVM is a great tool and a wonderful opportunity but it is not a panacea and
it would be wise to learn such lessons before jumping in to LLVM-based
development.
--
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e
_______________________________________________
Joel Reymont
On Mar 21, 2009, at 1:38 PM, Jon Harrop wrote:
> . You will succumb to ocamlopt's current run-time representation
> which is
> objectively inefficient (e.g. boxing floats, tuples, records) and
> was only
> chosen because the compiler lacks capabilities that LLVM already
> provides for
> you (primarily JIT compilation).
This is probably a stupid suggestion but why not have OCaml directly
generate machine code, without the use of assembler and linker?
Wouldn't this be easier than trying to couple OCaml with LLVM?
Separately, it's sort of funny that LLVM and its users are going
through all the trouble now, when Lisp and Forth have had runtime
compilation for years and years.
---
http://linkedin.com/in/joelreymont
Joel Reymont
On Mar 21, 2009, at 2:51 PM, Jon Harrop wrote:
> . I found that LLVM's x86 backend breaks tail calls when the return
> type is a
> first class struct. The workaround is to use sret form, having the
> caller
> preallocate the return struct and passing a pointer to the struct as
> an extra
> first argument.
Returning a structure by having the caller preallocate space, etc. is
part of the Intel ABI or something like that. This is how it's done,
period.
Not sure how it relates to breaking tail calls, though.
---
http://linkedin.com/in/joelreymont
Jon Harrop
> On Mar 21, 2009, at 2:51 PM, Jon Harrop wrote:
> > . I found that LLVM's x86 backend breaks tail calls when the return
> > type is a
> > first class struct. The workaround is to use sret form, having the
> > caller
> > preallocate the return struct and passing a pointer to the struct as
> > an extra
> > first argument.
>
> Returning a structure by having the caller preallocate space, etc. is
> part of the Intel ABI or something like that. This is how it's done,
> period.
No, not at all. Other calling conventions have many benefits including better
performance and the ability to return multiple values. LLVM provides a "fast"
calling convention as well as the (Intel-compatible) C callcc for precisely
this reason. HLVM uses LLVM's fast callcc. OCaml uses its own non-standard
calling convention.
Indeed, if HLVM were not using fastcc it would not have any tail calls at all!
This raises some interesting issues. For example, HLVM allows you to declare
external C functions from your high-level language and call them directly.
But it also has first-class function pointers so it is necessary to wrap the
C calls in fastcc calls so the C functions can be used interchangeably with
internal functions. There are many such subtleties in the design of HLVM and
I described them all in the relevant OCaml Journal articles.
> Not sure how it relates to breaking tail calls, though.
A design flaw in the implementation of tail calls in LLVM requires code to be
injected by the architecture-specific code gen after the tail call and before
the actual return in order to move the struct elements into place. That
prevents such tail calls from being eliminated later in the code gen.
Fortunately the author was there to assist. Even more remarkably, the same
student is responsible for tail calls on the JVM (!). He must be busy...
--
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e
_______________________________________________
Michael Ekstrand
> On Mar 21, 2009, at 1:38 PM, Jon Harrop wrote:
>
>> . You will succumb to ocamlopt's current run-time representation
>> which is
>> objectively inefficient (e.g. boxing floats, tuples, records) and
>> was only
>> chosen because the compiler lacks capabilities that LLVM already
>> provides for
>> you (primarily JIT compilation).
>
> This is probably a stupid suggestion but why not have OCaml directly
> generate machine code, without the use of assembler and linker?
Because that would duplicate the code and logic provided by the system's
assembler and linker (esp. linker). For every platform (and there are
many possible combinations!).
If you use the existing linker, then you can depend on the expertise of
the authors for each system getting all the logic right for loading
libraries (which may be arbitrary libraries, when you're using C
extensions) and producing a binary in the correct format for that
system.
Something like LLVM means that OCaml doesn't even need to duplicate the
knowledge about how to generate code for each architecture -- the
compiler author can focus on writing a really good front end, and the
LLVM people can focus on making an excellent machine code generator. If
compilers can attract the best front-end authors, and projects like LLVM
attract people with the best grasp of optimization and other back-end
matters, then the entire compiler ecosystem benefits more than if these
experts are split amongst many compiler projects.
- Michael
--
mouse, n: A device for pointing at the xterm in which you want to type.
Confused by the strange files? I cryptographically sign my messages.
For more information see <http://www.elehack.net/resources/gpg>.
Andrey Riabushenko
>generate machine code, without the use of assembler and linker?
>Wouldn't this be easier than trying to couple OCaml with LLVM?
That is exactly what I am thinking to do. In my opinion, it is least radiсal
way and it is exactly what is needed to merge the LLVM frontend to the ocaml
trunk. Ans it is exactly my goal.
Jon Harrop
> On Mar 21, 2009, at 1:38 PM, Jon Harrop wrote:
> > . You will succumb to ocamlopt's current run-time representation
> > which is
> > objectively inefficient (e.g. boxing floats, tuples, records) and
> > was only
> > chosen because the compiler lacks capabilities that LLVM already
> > provides for
> > you (primarily JIT compilation).
>
> This is probably a stupid suggestion but why not have OCaml directly
> generate machine code, without the use of assembler and linker?
>
> Wouldn't this be easier than trying to couple OCaml with LLVM?
Had OCaml not already been coupled with LLVM, yes. However, there are quite
decent OCaml bindings to LLVM already available (in the LLVM tree).
> Separately, it's sort of funny that LLVM and its users are going
> through all the trouble now, when Lisp and Forth have had runtime
> compilation for years and years.
Yes and no. LLVM supports many features that Lisp does not (e.g. type checking
at compile time, tail calls) and its implementation and the resulting
performance are far better than any of the open source Lisp implementations.
Lisp was one of the foundations I ruled out for implementing new MLs for these
reasons.
--
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e
_______________________________________________
Fermin Reig
>
> I would like to develop LLVM frontend to Ocaml language.
Sounds cool.
> 1.What is the best way to make ocaml frontend on your opinion?
I haven't been following LLVM, but you can learn about some of the
issues you are likely to face in my PhD dissertation. Part of the work I
did was a C-- backend for Ocaml. (Available at
http://fermin.reig.googlepages.com/reig_phd_2002.pdf)
HTH,
Fermin
Xavier Leroy
> participate in GSoC. LLVM do not mind to developed a ocaml frontend as LLVM
> GSoC project. I want to discuss details with you before I will make an
>
> Do authors of ocaml has something to say about the idea?
Da. A number of things, actually.
1- I know of at least 3, maybe 4 other projects that want to do
something with OCaml and LLVM. Clearly, some coordination between
these efforts is needed.
2- If you're applying for funding through a summer of code project,
you need to articulate good reasons why you want to combine OCaml and
LLVM. "Ocaml is cool, LLVM is cool, so OCaml+LLVM would be extra
cool" is not enough. "It will generate PIC-16 code" isn't either.
Run-time code generation could be a good enough reason, but you still
need to weigh the development cost of the LLVM approach against, for
example, hacking the current OCaml code generator so that it emits
machine code in memory instead of assembly code.
3- A language implementation like OCaml breaks down in four big parts:
1- Front-end compiler
2- Back-end compiler and code emitter
3- Run-time system
4- OS interface
Of these four, the back-end is not the biggest part nor the most
complicated part. LLVM gives you part 2, but you still need to
consider the other 3 parts. Saying "I'll do 1, 3 and 4 from scratch",
Harrop-style, means a 5-year project. To get somewhere within a
reasonable amount of time, you really need to reuse large parts of the
existing OCaml code base.
4- From a quick look at LLVM specs, the two aspects that appear most
problematic w.r.t. Caml are exception handling and GC interface.
LLVM seems to implement C++/Java "zero-cost" exceptions, which are
known to be quite costly for Caml. (Been there, done that, in the
early 1990s.) I regret that LLVM does not provide support for
alternate implementations of exceptions, like the C-- intermediate
language of Ramsey et al does:
http://portal.acm.org/citation.cfm?id=349337
The big issue, however, is GC interface. There are GC techniques that
need no support from the back-end: stack maps and conservative
collection. Stack maps are very costly in execution time.
Conservative GC like the Boehm-Weiser GC is already much better. But
for full efficiency, back-end support is required. LLVM documents a
minimal interface to produce stack maps and make them available to the
GC at run-time:
http://llvm.org/docs/GarbageCollection.html
The first thing you want to investigate is whether this interface is
enough to support an exact, relocating collector such as
OCaml's. According to
http://www.nabble.com/Garbage-collection-td22219430.html
Gordon Henriksen did succeed in interfacing OCaml's GC with LLVM.
Maybe there is still some more work to do here, in which case I
recommend you look into this first.
6- Here is a schematic of the Caml compiler. (Use a fixed-width font.)
|
| parsing and preprocessing
v
Parsetree (untyped AST)
|
| type inference and checking
v
Typedtree (type-annotated AST)
|
| pattern-matching compilation, elimination of modules, classes
v
Lambda
/ \
/ \ closure conversion, inlining, uncurrying,
v \ data representation strategy
Bytecode \
\
Cmm
|
| code generation
v
Assembly code
In my opinion, the simplest approach is to start at Cmm and generate
LLVM code from there. Starting at one of the higher-level
intermediate forms would entail reimplementing large chunks of the
OCaml compiler. Note that Cmm is quite close to the C-- intermediate
language mentioned earlier, so there is a lot to learn from Fermin
Reig's experience with an OCaml/C-- back-end.
7- To finish, I'll preventively deflect some likely reactions by Jon
Harrop:
"But you'll be tied to OCaml's data representation strategy!"
Right, but 1- implementing you own data representation strategy is
a lot of work, especially if it is type-based, and 2- OCaml's
strategy is close to optimal for symbolic computing.
"But LLVM assembly is typed, so you must have types!"
Just use int32 or int64 as your universal type and cast to
appropriate pointer types in loads or stores.
"But your code will be tainted by OCaml's evil license!"
It is trivial to make ocamlopt dump Cmm code in a file or pipe.
(The -dcmm debug option already does this.) Then, you can have a
separate, untainted program that reads the Cmm code and transforms it.
"But shadow stacks are the only way to go for GC interface!"
No, it's probably the worst approach performance-wise; even a
conservative GC should work better.
Hope this helps,
- Xavier Leroy
Kuba Ober
> Joel Reymont <joe...@gmail.com> writes:
>> On Mar 21, 2009, at 1:38 PM, Jon Harrop wrote:
>>
>>> . You will succumb to ocamlopt's current run-time representation
>>> which is
>>> objectively inefficient (e.g. boxing floats, tuples, records) and
>>> was only
>>> chosen because the compiler lacks capabilities that LLVM already
>>> provides for
>>> you (primarily JIT compilation).
>>
>> This is probably a stupid suggestion but why not have OCaml directly
>> generate machine code, without the use of assembler and linker?
This won't help with anything -- why would it? How is this suggestion
relevant to current discussion?
> Because that would duplicate the code and logic provided by the
> system's
> assembler and linker (esp. linker). For every platform (and there are
> many possible combinations!).
The only problem is that the usual notion of a "linker" is somewhat
broken, even if
what we're after is an embedded platform where all of the linking is
done
before the code hits the target (no run-time linking!).
I will show a trivial example where it fails bad. The example is in C.
Suppose you have two platform-specific registers used to set the DMA
address.
The platform has 12 bit addresses.
#define DMAL (*((volatile unsigned char*)0xFFA))
#define DMAH (*((volatile unsigned char*)0xFF0))
The DMAL takes a whole least significant byte of the address. The DMAH
takes
takes one most significant nibble (bits 11:8) of the address, and the
nibble must be
left-aligned (occupy bits 7:4 of DMAH).
Now, in your code, you want to point DMA to a static buffer. Thusly
void foo(void)
{
static char buffer[128];
DMAL = (unsigned char)&buffer;
DMAH = (((unsigned int)&buffer) >> 4) & 0xF0;
..
}
Now, while all of the addresses are known constants, there's usually
no way,
in the object file, to tell the linker the expression for the value of
DMAH!
Thus, instead of what amounts to two "load immediate" instructions,
you have one immediate load, followed by a lot of brouhaha to shift
and mask what
amounts to constants known at compile/link time. That's what's usually
called
premature pessimization.
That's one issue with contemporary compile/assemble/link systems.
Never mind
that even if the assemblers would support such "elaborate" expressions
using
link-time constants, the compilers don't generate them anyway!
So, writing the code in assembly won't help you! It's only at link
time that you
know where the buffer[] will end up... You can of course hack and put
the
buffer at a fixed address -- some C implementations will even have
special
ways of doing that (say via gcc's __attribute__ mechanism). That will
backfire as
soon as you get to interface more pieces of code: you'll be spending
your time
moving stuff around just to keep the memory regions from overlapping
-- that's the
linker's job, really.
Heck -- many, many assemblers will silently generate utterly wrong
code for the load
into DMAH, *if* you code this in assembly, not C!! I've got at least a
dozen production,
shipping assemblers, that silently trip-and-fall on the code like the
one above. Of course
they only fail if you code it in assembly, as the C compiler won't
even attempt such
um, "trickery". Silly stuff, really, requiring no advanced
optimization theories, just doing
one's darn job well...
You have a choice: either put some ASTs into the object file, whenever
the
expressions involving link-time constants are involved, or you get rid
of the whole
compile-assemble-link separation and get everything into one place.
The latter, incidentally, is what I ended up doing in my godawful LISP-
on-its-way-to-ML
platform for Z8 Encore! and SX48.
This would be, "of course", taken care of by a JIT: it would figure
out that a whole lot
of nothing is done on constant memory addresses, and would replace all
the operations
by a final load. But, on a platform where the code is statically
linked on the host, there's
no need for any of that, nor for a JIT. This applies to a whole lot of
hard-realtime systems
where a lot of reasoning can be made trivial by only using
preallocated memory, and not
doing any runtime memory allocation (or at least limiting it well).
> If you use the existing linker, then you can depend on the expertise
> of
> the authors for each system getting all the logic right for loading
> libraries (which may be arbitrary libraries, when you're using C
> extensions) and producing a binary in the correct format for that
> system.
The "logic" present in many linkers is either pretty trivial, or is an
ugly hack
for lack of expressiveness in object file records. Then you have link
time optimizations,
which are really trivial to do in a whole-project compiler, but
require a lot of
extra effort in a linker, etc.
Heck, many linkers use ad-hoc horrible quadratic-or-worse time
algorithms that backfire
severely once the size of the project gets sufficiently big. Just
follow the evolution of
gnu ld in face of C++. A farce in multiple acts, at least.
Cheers, Kuba
Jon Harrop
> 3- A language implementation like OCaml breaks down in four big parts:
> 1- Front-end compiler
> 2- Back-end compiler and code emitter
> 3- Run-time system
> 4- OS interface
> Of these four, the back-end is not the biggest part nor the most
> complicated part. LLVM gives you part 2, but you still need to
> consider the other 3 parts. Saying "I'll do 1, 3 and 4 from scratch",
> Harrop-style, means a 5-year project.
On the contrary, my "style" was to provide the features that I value
(multicore & FFI) in a usable form (stop-the-world) with the shortest
possible development time (i.e. <<6 months to create something useful).
Specifically:
1- Front-end compiler: use camlp4 to provide an embedded DSL for
high-performance parallel numerics and/or reuse front-ends from existing
compilers like OCaml, PolyML, MosML, NekoML to build completely new language
implementations.
2- Back-end compiler and code emitter: reuse LLVM.
3- Run-time system: write the simplest possible precise GC and use
stop-the-world to apply it to threads that may then run in parallel.
4- OS interface: make it as easy as possible to call C directly.
HLVM had solved (2), (3) and (4) after only 3 months of part-time work. I
vindicated my style!
> 7- To finish, I'll preventively deflect some likely reactions by Jon
> Harrop:
>
> "But you'll be tied to OCaml's data representation strategy!"
> Right, but 1- implementing you own data representation strategy is
> a lot of work, especially if it is type-based, and
Actually I found that easy, not least because I wanted a user-friendly FFI so
I just used C's data representation whenever possible.
> 2- OCaml's strategy is close to optimal for symbolic computing.
Is MLton not several times faster than OCaml for symbolic computing?
> "But LLVM assembly is typed, so you must have types!"
> Just use int32 or int64 as your universal type and cast to
> appropriate pointer types in loads or stores.
That is entirely possible and could be useful as an incremental improvement to
OCaml's existing bytecode interpreter but it is not a step toward my goals.
> "But your code will be tainted by OCaml's evil license!"
> It is trivial to make ocamlopt dump Cmm code in a file or pipe.
> (The -dcmm debug option already does this.) Then, you can have a
> separate, untainted program that reads the Cmm code and transforms it.
Again, that is another technically-feasible step away from my goals because
OCaml's CMM has already been mangled for its data representation (e.g. 31-bit
ints, boxed floats).
> "But shadow stacks are the only way to go for GC interface!"
> No, it's probably the worst approach performance-wise; even a
> conservative GC should work better.
Building a state-of-the-art optimized concurrent GC Leroy-style means an
infinity-year project. =:-p
Seriously though, I think it is essential to get a first working version of a
GC that permits parallel threads. HLVM will be useful to a lot of people long
before its GC gets optimized.
--
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e
_______________________________________________
Xavier Leroy
>
> Is MLton not several times faster than OCaml for symbolic computing?
No, only in your dreams. If there was a Caml or SML compiler that was
twice as fast as Caml on codes like Coq or Isabelle/HOL, everyone (me
included) would have switched to that compiler a long time ago.
MLton can probably outperform Caml on some symbolic codes, but not by
a large factor and not because of data representation strategies (but
rather because of more aggressive inlining and the like).
- Xavier Leroy
Nicolas Cannasse
>>> 2- OCaml's strategy is close to optimal for symbolic computing.
>>
>> Is MLton not several times faster than OCaml for symbolic computing?
>
> No, only in your dreams. If there was a Caml or SML compiler that was
> twice as fast as Caml on codes like Coq or Isabelle/HOL, everyone (me
> included) would have switched to that compiler a long time ago.
> MLton can probably outperform Caml on some symbolic codes, but not by
> a large factor and not because of data representation strategies (but
> rather because of more aggressive inlining and the like).
I agree that OCaml runtime representation is already pretty good,
although it lacks some runtime inspection abilities.
IMHO, the main optimization that using LLVM can perform wrt OCaml
internal representation is the ability to fully unbox floats, including
for FFI callbacks. Of course, that might not help much for symbolic
processing...
As for 5 years for designing a whole system, thanks to today great tools
(which OCaml is part of), I was myself able to build a complete
ecosystem with haXe http://haxe.org and NekoVM in "only" 2 years, I'm
pretty sure this can be done much faster when people know exactly what
they are doing on how they want to get there.
Best,
Nicolas
Joel Reymont
http://lambda-the-ultimate.org/node/440
I'm told that not much has changed since.
---
http://tinyco.de
Mac, Lisp, OCaml
Jon Harrop
> There's a nice discussion of LLVM in the context of Alice ML here:
>
> http://lambda-the-ultimate.org/node/440
>
> I'm told that not much has changed since.
Whoever told you that was wrong: a lot has changed in LLVM over the past five
years. Indeed, it is one of the most rapidly advancing open source projects
in existence thanks to extensive contributions from the likes of Apple and
Google.
LLVM has long since had full support for tail calls. See the "tco" example in
the "test.ml" file of HLVM for an example. I tested tail calls in LLVM
extensively before choosing to build upon it. I have found and worked around
some minor bugs in their TCO implementation but Arnold Schwaighofer just
committed a fix that will be in LLVM 2.6.
The toy Scheme implementation that was in LLVM five years ago has long since
been overshadowed by full-blown FPL implementations like the Pure language:
http://pure-lang.sourceforge.net/
I don't understand Anton van Straaten's other complaint about the lack of
closures. They are trivial to implement. Again, look at the examples in HLVM
(although they are hand-coded because we don't have lambda lifting yet).
Moreover, LLVM offers huge advantages:
LLVM-generated code on x86 is often several times faster and can be up to an
order of magnitude faster than any existing FPL implementation. Moreover,
LLVM can JIT compile, making it trivial to outperform interpreted languages
like OCaml's current top-level. See HLVM's preliminary performance results,
for example:
http://flyingfrogblog.blogspot.com/2009/03/performance-ocaml-vs-hlvm-beta-04.html
LLVM generates code very quickly, rivalling ocamlopt's compile times.
SSE and atomic instructions for high-performance numerics and
parallelism/concurrency.
Mature and easy-to-use API with native OCaml bindings.
Substantial friendly community who not only explain things but fix them for
you quickly.
Commercially viable: LLVM is already shipping in products.
LLVM does have some disadvantages:
LLVM's JIT compiler is not multicore capable (but what FPL implementations
are?).
LLVM does not bundle a reusable high-performance concurrent garbage
collector (but what standalone FPLs do?).
LLVM's GC API is experimental so if you want a specialized run-time (e.g.
optimized specifically for symbolics) you have to write it yourself.
--
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e
_______________________________________________
Jon Harrop
> No, it's probably the worst approach performance-wise; even a
> conservative GC should work better.
I blogged a quick analysis of the performance of HLVM's current shadow stack
code:
http://flyingfrogblog.blogspot.com/2009/03/current-shadow-stack-overheads-in-hlvm.html
There is a lot of scope for optimization but these results were enlightening
to show where the effort should be put. In particular, shadow stack updates
by the mutator (and not the collector, as I had incorrectly assumed) account
for the entire performance difference between OCaml and HLVM on the 10-queens
benchmark.
--
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e
_______________________________________________