JIT VM in OCaml: Impossible?

JIT VM in OCaml: Impossible?

[Joel Reymont]

Folks,

Is it possible to write a JIT VM in OCaml?

It seems that this should not be possible as OCaml does not allow for  
code generation at runtime. Am I mistaken?

	Thanks, Joel

--
http://wagerlabs.com

Re: JIT VM in OCaml: Impossible?

[Sylvain Le Gall]

On 16-08-2007, Joel Reymont <joelr1@gmail.com> wrote:
> Folks,
>
> Is it possible to write a JIT VM in OCaml?
>
> It seems that this should not be possible as OCaml does not allow for  
> code generation at runtime. Am I mistaken?
>
> 	Thanks, Joel
>

What about : 
http://cristal.inria.fr/~starynke/ocamljit.html

I think this what you think is impossible to achieve ;-)

However, i don't know the state of the project.

Regards,
Sylvain Le Gall

Re: [Caml-list] JIT VM in OCaml: Impossible?

[Oliver Bandel]

Zitat von Joel Reymont <joelr1@gmail.com>:

> Folks,
>
> Is it possible to write a JIT VM in OCaml?
>
> It seems that this should not be possible as OCaml does not allow for
> code generation at runtime. Am I mistaken?
[...]


It is possible to create functions on the fly
via putting together available functions by partial function application.

If you parse a "sin" in your code, you can use the "sin" form ocaml,
applying nor arguments to it. (Like passing function pointers in C,
but it's more elegant in functional languages, and more convenient.)

So it is possible to create applicable code.
I use this in one of my tools. There I create
certain comparison functions, for example, dependend
on what I parsed from my input.

I do this by creating closures (which means that
the functions that are the closures can be applied to
the arguments later).


A not perfect example (quick but not so dirty hacked, but possible
to make it better, as I just saw, when I answered your mail and
looked again in my *.mly, but maybe it can give you an idea
about what can be done, or how it could be done) is my tool
"apalogretrieve", which makes SQL-like queries on Apache
common logfiles:

  http://www.first.in-berlin.de/software/tools/apalogretrieve/

<disclaimer>
I know, it's not perfect (so, maybe the OCaml Gurus might
laugh about it) but it works for my needs and was done in
a short time, scattered about a long time.
</disclaimer>

Maybe it give's you an idea.

For a complete language to implement your stuff might
need more code, but if you have to implement a for-loop for example,
you could parse it from your language and create a
closure, which calls an OCaml for-loop directly (in the
closures).

You can make complex things by putting together partial applicated
functions. Look at how I create the conditions in the above mentioned code.

Ciao,
   Oliver

P.S.: Functional Programming should be written in this way:
      FUNctional programming, because it really makes FUN,
      at least to me. :)

Re: [Caml-list] Re: JIT VM in OCaml: Impossible?

[Oliver Bandel]

Zitat von Sylvain Le Gall <sylvain@le-gall.net>:

> On 16-08-2007, Joel Reymont <joelr1@gmail.com> wrote:
> > Folks,
> >
> > Is it possible to write a JIT VM in OCaml?
> >
> > It seems that this should not be possible as OCaml does not allow for
> > code generation at runtime. Am I mistaken?
> >
> > 	Thanks, Joel
> >
>
> What about :
> http://cristal.inria.fr/~starynke/ocamljit.html
[...]

Oh, I may have understood the question wrong.

I thought that  the question was to implement
a self-written language, not OCaml itself...?!

But the above link looks interesting.

Ciao,
   Oliver

Re: [Caml-list] Re: JIT VM in OCaml: Impossible?

[Joel Reymont]

On Aug 16, 2007, at 4:32 PM, Oliver Bandel wrote:

> I thought that  the question was to implement
> a self-written language, not OCaml itself...?!

Right, I meant a JIT for non-OCaml bytecode, written in OCaml.

	Thanks, Joel

--
http://wagerlabs.com

Re: [Caml-list] Re: JIT VM in OCaml: Impossible?

[Jon Harrop]

On Thursday 16 August 2007 15:37:09 Sylvain Le Gall wrote:
> On 16-08-2007, Joel Reymont <joelr1@gmail.com> wrote:
> > Folks,
> >
> > Is it possible to write a JIT VM in OCaml?
> >
> > It seems that this should not be possible as OCaml does not allow for
> > code generation at runtime. Am I mistaken?
> >
> > 	Thanks, Joel
>
> What about :
> http://cristal.inria.fr/~starynke/ocamljit.html

As others have said, Joel wants to write a JIT in OCaml rather than for OCaml. 
Although the OCamlJIT project was a nice idea, it is based upon the now-dead 
GNU Lightning library and its functionality was more recently displaced by 
the much more performant ocamlnat.

However, I think tools to enable JIT writing using OCaml would be most 
welcome. Not only the safe staged metaprogramming approach of MetaOCaml but 
also direct code generators.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
OCaml for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists/?e

Re: [Caml-list] JIT VM in OCaml: Impossible?

[Gordon Henriksen]

[-- Attachment #1: Type: text/plain, Size: 618 bytes --]

On 2007-08-16, at 10:10, Joel Reymont wrote:

> Is it possible to write a JIT VM in OCaml?
>
> It seems that this should not be possible as OCaml does not allow  
> for code generation at runtime. Am I mistaken?

Sure. You could write a compiler and assembler in ocaml. But you'd  
need to write glue code in C or assembly to convert the ocaml  
representation to machine data structures, and to call into your  
ocaml-based compiler implementation on-demand when a function is called.

But to compile your language/bytecode to ocaml source, and then JIT  
compile that? No help there, no…

— Gordon


[-- Attachment #2: Type: text/html, Size: 4139 bytes --]

Re: [Caml-list] JIT VM in OCaml: Impossible?

[skaller]

On Thu, 2007-08-16 at 12:24 -0400, Gordon Henriksen wrote:
> On 2007-08-16, at 10:10, Joel Reymont wrote:
> 
> > Is it possible to write a JIT VM in OCaml?
> > 
> > 
> > It seems that this should not be possible as OCaml does not allow
> > for code generation at runtime. Am I mistaken?
> 
> 
> Sure. You could write a compiler and assembler in ocaml.
>  But you'd need to write glue code in C or assembly to 
> convert the ocaml representation to machine data structures,

Why? Ocaml is just as capable of generating binary data as C ..
if not more capable. You would need some glue to actually
*execute* this code, but that is also true in C. For Unix,
mmap() would probably be used.

The question is: why would you do this? Why not just generate
C (or C++ as Felix does) and compile it to a shared library,
then link and execute it? 

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

Re: [Caml-list] JIT VM in OCaml: Impossible?

[Taras Glek]

skaller wrote:
> On Thu, 2007-08-16 at 12:24 -0400, Gordon Henriksen wrote:
>   
>> On 2007-08-16, at 10:10, Joel Reymont wrote:
>>
>>     
>>> Is it possible to write a JIT VM in OCaml?
>>>
>>>
>>> It seems that this should not be possible as OCaml does not allow
>>> for code generation at runtime. Am I mistaken?
>>>       
>> Sure. You could write a compiler and assembler in ocaml.
>>  But you'd need to write glue code in C or assembly to 
>> convert the ocaml representation to machine data structures,
>>     
>
> Why? Ocaml is just as capable of generating binary data as C ..
> if not more capable. You would need some glue to actually
> *execute* this code, but that is also true in C. For Unix,
> mmap() would probably be used.
>
> The question is: why would you do this? Why not just generate
> C (or C++ as Felix does) and compile it to a shared library,
> then link and execute it? 
>   
Because that would be bloody slow and depend on having a toolchain 
installed? For a JIT you want a fast compiler that only compiles as 
little as is needed.

Taras

Re: [Caml-list] JIT VM in OCaml: Impossible?

[Jon Harrop]

On Thursday 16 August 2007 17:24:39 Gordon Henriksen wrote:
> But to compile your language/bytecode to ocaml source, and then JIT
> compile that? No help there, no…

Doesn't ocamlnat do exactly that?

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
OCaml for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists/?e

Re: [Caml-list] JIT VM in OCaml: Impossible?

[skaller]

On Thu, 2007-08-16 at 11:05 -0700, Taras Glek wrote:

> > The question is: why would you do this? Why not just generate
> > C (or C++ as Felix does) and compile it to a shared library,
> > then link and execute it? 
> >   
> Because that would be bloody slow and depend on having a toolchain 
> installed? For a JIT you want a fast compiler that only compiles as 
> little as is needed.

Yes, it does depend on having a tool. Slow? No, not really:
[AMD64 2300 1G]:

(includes parsing the file)
skaller@rosella:/work/felix/svn/felix/felix/trunk$ time f hello
Hello World

real    0m2.073s
user    0m1.972s
sys     0m0.084s

(using cached parse)
skaller@rosella:/work/felix/svn/felix/felix/trunk$ time f hello
Hello World

real    0m1.026s
user    0m0.908s
sys     0m0.100s


(using cached binary)
skaller@rosella:/work/felix/svn/felix/felix/trunk$ time flx hello
Hello World

real    0m0.039s
user    0m0.016s
sys     0m0.012s

I suspect this is actually faster than any JIT, and there's
no question it is faster if the program is reused.

Don't forget: a program has to be compiled one way or the other.
Even Python is compiled to bytecode.  The tool above (Felix)
is better than a JIT because it does whole program optimisation,
generates machine binaries.

So I don't buy 'slow' as an argument: the technique is much
FASTER than any JIT system in all aspects, in fact it IS
a JIT compiler -- it just compiles the whole program all the
way from source with disk based caching which persists over
invocations.

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

Re: [Caml-list] JIT VM in OCaml: Impossible?

[Erick Tryzelaar]

skaller wrote:
> Don't forget: a program has to be compiled one way or the other.
> Even Python is compiled to bytecode.  The tool above (Felix)
> is better than a JIT because it does whole program optimisation,
> generates machine binaries.
>
> So I don't buy 'slow' as an argument: the technique is much
> FASTER than any JIT system in all aspects, in fact it IS
> a JIT compiler -- it just compiles the whole program all the
> way from source with disk based caching which persists over
> invocations.
>   

For loose definitions of JIT :) It doesn't do runtime optimization of 
the code, of course.

And to be fair, since whole program optimization needs to start roughly 
from scratch every time, you can have some ugly compile times.

Re: [Caml-list] JIT VM in OCaml: Impossible?

[skaller]

On Thu, 2007-08-16 at 20:09 -0700, Erick Tryzelaar wrote:

> > So I don't buy 'slow' as an argument: the technique is much
> > FASTER than any JIT system in all aspects, in fact it IS
> > a JIT compiler -- it just compiles the whole program all the
> > way from source with disk based caching which persists over
> > invocations.
> >   
> 
> For loose definitions of JIT :) It doesn't do runtime optimization of 
> the code, of course.
> 
> And to be fair, since whole program optimization needs to start roughly 
> from scratch every time, you can have some ugly compile times.

Bytecode has to be compiled too. If you have a one-off script which
doesn't benefit from optimisation much, then it is a toss up whether
a bytecode compilation followed by JIT based machine code generation
has higher cost than C code generation followed by C compilation.

If the code has to run for a long time, or be re-run often,
then the C compilation wins hands down. you would need a
VERY sophisticated JIT to actually use runtime information
to tune code generation, beyond 'it got used at least once'
of course. OTOH traditional compilers can apply all sorts of
static analysis driven optimisations a JIT cannot, because it
is looking at a bigger picture.

So roughly my feeling is that JIT offers NO performance advantages.
It's the worst possible combination you can have.

The advantage of JIT is that you can improve the performance
of a VM when you have to use a VM either because you're stuck
using rubbish like JVM for political reasons, or you need to
maintain a secure, restricted environment, for example running
scripts from a web-server. In the latter case a properly designed
language translator can make the same guarantees, but correctness
of translator based security assurance is probably harder to 
demonstrate than for a VM.

I do agree a *sophisticated* JIT could outperform compiled native
code IF it were able to dynamically generate code based on real
time feedback from actually running code, but this is a 
VERY difficult job *especially* with modern processors which
already do exactly this kind of thing with branch prediction etc:
the JIT now has to second guess the CPU circuitry to be able
to calculate alternative encodings.

In some sense I make the argument strongly AGAINST VM implementations. 
I would argue *source code* is the proper object to execute, and a
traditional compiler driven by changes to the source is the correct
way to execute source: binary code should be regarded as a cache,
not the final product.

It's clear that this is entirely possible for Ocaml with 
a suitable harness and minor language tweaks: Ocamlopt.opt 
is very fast and Ocaml sources are quite portable, so 
executing Ocaml *source* code is the proper
model of program execution -- the native code compilation should
be regarded just like a JIT optimisation.

The biggest obstacle here is the trivial lack of a proper 
language construction to state dependencies, and a proper
packaging model. Felix does this right. Ocaml (with Ocamldep
and some fiddling) could do it too.

With such a program for Ocaml, Debian packagers would be ecstatic --
no more binaries. Just distribute and execute source.

BTW: AFAICS Alain Frisch patch to run ocamltop as native code
with native code dynamic loading comes very close to realising this.


-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

Re: [Caml-list] JIT VM in OCaml: Impossible?

[Joel Reymont]

Just to focus the discussion a bit, I want to use OCaml to write a VM  
for Erlang. I don't want to write a compiler just yet so I have to  
deal with pre-built Erlang bytecode.

My question was about JIT-compiling that bytecode in OCaml once it's  
loaded into my VM.

	Thanks, Joel

--
http://wagerlabs.com

Re: [Caml-list] JIT VM in OCaml: Impossible?

[Jon Harrop]

On Friday 17 August 2007 08:52:22 Joel Reymont wrote:
> Just to focus the discussion a bit, I want to use OCaml to write a VM
> for Erlang. I don't want to write a compiler just yet so I have to
> deal with pre-built Erlang bytecode.
>
> My question was about JIT-compiling that bytecode in OCaml once it's
> loaded into my VM.

If you can do that, you can probably JIT compile to native code just as easily 
using the natdynlink branch (its awesome, BTW).

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
OCaml for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists/?e

Re: [Caml-list] JIT VM in OCaml: Impossible?

[Jon Harrop]

On Friday 17 August 2007 03:50:00 skaller wrote:
> Slow? No, not really: [AMD64 2300 1G]:
>
> (includes parsing the file)
> skaller@rosella:/work/felix/svn/felix/felix/trunk$ time f hello
> Hello World
>
> real    0m2.073s
> user    0m1.972s
> sys     0m0.084s

[AMD64 2200 2G]

$ cat >test.ml
print_endline "Hello world"
$ time ocamlnat test.ml
Hello world

real    0m0.063s
user    0m0.033s
sys     0m0.029s

Thats 33x faster on a slower machine.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
OCaml for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists/?e

Re: [Caml-list] JIT VM in OCaml: Impossible?

[Joel Reymont]

Jon,

On Aug 17, 2007, at 9:36 AM, Jon Harrop wrote:

> If you can do that, you can probably JIT compile to native code  
> just as easily using the natdynlink branch (its awesome, BTW).

Are you saying that I can easily compile _Erlang bytecode_ to native  
code with the natdynlink branch? :-)

Are you suggesting, perhaps, that once the chain of OCaml closures is  
built it can be compiled to native code? How would you do it exactly  
with natdynlink?

	Thanks, Joel

--
http://wagerlabs.com