[Caml-list] The Bytecode Interpreter...

[Caml-list] The Bytecode Interpreter...

[Jonathan Roewen]

Hi,

I'm having a few reservations over ocaml native code as an OS/kernel,
due to some limitations with the language environment (no dynamic
libraries for ocaml libs or runtime, no concurrent GC).

How does the toplevel differ from the bytecode interpreter? Am I right
that bytecode just runs in a VM? Also, is the VM written in OCaml
itself?

Jonathan

Re: [Caml-list] The Bytecode Interpreter...

[David MENTRE]

Hello,

2005/10/21, Jonathan Roewen <jonathan.roewen@gmail.com>:
> How does the toplevel differ from the bytecode interpreter?

No difference. Toplevel expression are compiled as bytecode and then
executed by bytecode interpreter.

> Am I right that bytecode just runs in a VM?

Yes.

> Also, is the VM written in OCaml itself?

No, in C (see directory byterun/ in ocaml source code).

Yours,
d.

Re: [Caml-list] The Bytecode Interpreter...

[Jonathan Roewen]

I've noted on the computer language shootout that ocaml bytecode is
slow compared to Java. I'm curious, are there any plans to optimise
the shit out of the bytecode interpreter? I know it has been a goal to
not be much more than 1.3x slower than C -- but this only covers
ocamlopt/native code. Don't you think bytecode should have some
endeavour to match or better some other language too (Java seems best
case to me in this scenario).

About the only thing the shootout proves is that ocaml bytecode has
very good memory use compared to Java.

On 10/22/05, David MENTRE <david.mentre@gmail.com> wrote:
> Hello,
>
> 2005/10/21, Jonathan Roewen <jonathan.roewen@gmail.com>:
> > How does the toplevel differ from the bytecode interpreter?
>
> No difference. Toplevel expression are compiled as bytecode and then
> executed by bytecode interpreter.
>
> > Am I right that bytecode just runs in a VM?
>
> Yes.
>
> > Also, is the VM written in OCaml itself?
>
> No, in C (see directory byterun/ in ocaml source code).
>
> Yours,
> d.
>

Re: [Caml-list] The Bytecode Interpreter...

[Oliver Bandel]

On Sat, Oct 22, 2005 at 11:24:10AM +1300, Jonathan Roewen wrote:
> I've noted on the computer language shootout that ocaml bytecode is
> slow compared to Java. I'm curious, are there any plans to optimise
> the shit out of the bytecode interpreter? I know it has been a goal to
> not be much more than 1.3x slower than C -- but this only covers
> ocamlopt/native code. Don't you think bytecode should have some
> endeavour to match or better some other language too (Java seems best
> case to me in this scenario).
> 
> About the only thing the shootout proves is that ocaml bytecode has
> very good memory use compared to Java.


You will have the best performance and maybe the best memory
usage, when writing all your programs in Assembler.

Well, I really like fast langauges, but performance is not all
(even if all is nothing when the performance is bad).


Is performance the only or the biggest thing you look for,
when deciding fo a programming langauge?


Ciao,
  Oliver

Re: [Caml-list] The Bytecode Interpreter...

[Jon Harrop]

On Friday 21 October 2005 23:24, Jonathan Roewen wrote:
> I've noted on the computer language shootout that ocaml bytecode is
> slow compared to Java. I'm curious, are there any plans to optimise
> the shit out of the bytecode interpreter? I know it has been a goal to
> not be much more than 1.3x slower than C -- but this only covers
> ocamlopt/native code. Don't you think bytecode should have some
> endeavour to match or better some other language too (Java seems best
> case to me in this scenario).

You may be interested in Basile's ocamljit.

> About the only thing the shootout proves is that ocaml bytecode has
> very good memory use compared to Java.

and brevity.

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

Re: [Caml-list] The Bytecode Interpreter...

[Jonathan Roewen]

Hi Again,

I have a few more questions about the toplevel/bytecode interpreter.

I've noted in startup.c that caml_main tries to open itself, and do
some sort of work on the file. The problem is that I want to be able
to run the ocaml toplevel on the bare metal (and later extend it into
an operating system of sorts). I've seen there is a caml_startup_code
function in startup.c that appears to setup the caml environment
without reading itself: however, how do I find all the values to pass
to it?

Alternatively, another idea, which I'd like some feedback on for suitability is:
- load the 'kernel' as a module as well as the kernel itself (so I
suppose mapped into memory twice).
- provide some dummy C functions that a) let us open the 'kernel', and
b) provide read-only access to the file.
- let caml_main use this in-memory representation of the 'kernel' to
start itself up.

I'm wondering what kind of other obstacles would also affect my desire
to achieve this as well.

One last thing =) How does the toplevel get initialised, etc., and
started running? Does it depend on ocamlrun being in the path, and
being able to load it into memory or something?

Jonathan

Re: [Caml-list] The Bytecode Interpreter...

[Jacques Garrigue]

From: Jonathan Roewen <jonathan.roewen@gmail.com>

> I've noted on the computer language shootout that ocaml bytecode is
> slow compared to Java. I'm curious, are there any plans to optimise
> the shit out of the bytecode interpreter? I know it has been a goal to
> not be much more than 1.3x slower than C -- but this only covers
> ocamlopt/native code. Don't you think bytecode should have some
> endeavour to match or better some other language too (Java seems best
> case to me in this scenario).
> 
> About the only thing the shootout proves is that ocaml bytecode has
> very good memory use compared to Java.

This is not at all surprising: you are comparing two very different
things. OCaml has a pure bytecode interpreter, while Java is a mix of
interpreter and run-time compiler (the famous "JIT"). Microsoft's CLR
is even more extreme, as all execution goes through the JIT. Their
only common point is that they take bytecode as input, but they run it
very differently. For a pure bytecode interpreter OCaml is pretty fast
(faster than caml-light, which was already very fast), but it cannot
compete with a compiler. There is also an experimental JIT runtime for
OCaml (ocamljitrun), but it suffers from the difference in the
bytecode design: OCaml bytecode is designed to run on a pure bytecode
interpreter, so it drops all type and control flow information (which
Java bytecode keeps), as it would not be useful for such an
interpreter. The advantage is compactness, and good memory use. This
also means that there is very little the JIT will be able to
optimize. Nonetheless ocamljitrun is about twice as fast as ocamlrun,
just because modern processors are very much geared towards compilers.

So your question could be expressed as: is there any plan for a more
expressive bytecode, that would allow JIT optimizations.
The answer is that I'm not aware of any.
A connected topic may be the language F#: a cousin of ocaml, built on
top of Microsoft's CLR, and as such benefiting from a very good JIT
runtime.

That's all I know.

Jacques Garrigue

Re: [Caml-list] The Bytecode Interpreter...

[Jonathan Roewen]

> Is performance the only or the biggest thing you look for,
> when deciding fo a programming langauge?

No need to be a troll Oliver. I am more than satisfied with the
answers I received, thanks.

Re: [Caml-list] The Bytecode Interpreter...

[Jonathan Roewen]

> No difference. Toplevel expression are compiled as bytecode and then
> executed by bytecode interpreter.

I think I'm starting to understand some of how the toplevel & bytecode
interpreter work. Some of it, I don't understand why, so will continue
from there ;-)

In the toplevel, you can #load in an ocaml library, but you still need
all the .cmi files in order to open/use them. Why is that? Shouldn't
it be in the library?

Also, I presume loading libraries on the fly, and having access to
-all- symbols defined in .cmi files available does -not- use the
Dynlink module. Is this correct?

How can a bytecode program do the same things as the toplevel in terms
of #load-ing libraries and accessing any given value as specifed in
the compiled interface files?

Lastly, why is the Dynlink module unable to provide the ability to
access any given value in a compiled interface file when loading a
bytecode object? Or can it? The comments for the Dynlink module
specify that this -isn't- possible. However, it -can- access values
from the program the loads the .cmo -- is that correct?

Jonathan

Re: [Caml-list] The Bytecode Interpreter...

[Gerd Stolpmann]

Am Sonntag, den 23.10.2005, 14:03 +1300 schrieb Jonathan Roewen:
> > No difference. Toplevel expression are compiled as bytecode and then
> > executed by bytecode interpreter.
> 
> I think I'm starting to understand some of how the toplevel & bytecode
> interpreter work. Some of it, I don't understand why, so will continue
> from there ;-)
> 
> In the toplevel, you can #load in an ocaml library, but you still need
> all the .cmi files in order to open/use them. Why is that? Shouldn't
> it be in the library?

I don't know exactly the reasons, but I think this scheme is driven by
the needs of ocamlc, not the toplevel. If the interfaces were packed
into the .cma files, one would have to specify the .cma even for ocamlc
-c. As the command-line of ocamlc is patterned after the C compiler
command syntax, this would be quite surprising. Some hacks would become
impossible (e.g. several .cma implementations for the same set of .cmi).
I think the idea is not bad. One clear disadvantage would be that the
interfaces would be stored twice (in .cma and .cmxa) if one had both a
bytecode and a native code version of the library.

> Also, I presume loading libraries on the fly, and having access to
> -all- symbols defined in .cmi files available does -not- use the
> Dynlink module. Is this correct?

As far as I know, both Dynlink and the toplevel share parts of the
infrastructure needed for that. Dynlink only loads the bytecode,
relocates it, and resolves symbols pointing to already loaded libraries.
For this purpose, Dynlink maintains a symbol table (i.e. a mapping from
identifiers to addresses).

When one #loads within a toploop, more or less the same happens.
However, the toploop is a full compiler, and does not only have the
symbol table, but also the current environment, i.e. the set of
currently visible types and values with the still-needed parts of their
definitions. As far as I know, #load does not modify the environment
(because nothing changes - the loaded modules are already in scope when
the .cmi file is in the search path).

> How can a bytecode program do the same things as the toplevel in terms
> of #load-ing libraries and accessing any given value as specifed in
> the compiled interface files?

Because it has the symbol table. It is part of every bytecode executable
and .cmo file, but normally not loaded, because not needed for
execution. When Dynlink is initialized, the symbol table is extracted
from the bytecode executable.

> Lastly, why is the Dynlink module unable to provide the ability to
> access any given value in a compiled interface file when loading a
> bytecode object? Or can it? The comments for the Dynlink module
> specify that this -isn't- possible. However, it -can- access values
> from the program the loads the .cmo -- is that correct?

In principle, it can. As mentioned, it has the symbol table, so it can
look up every symbol.

However, the question arises how to access symbols at runtime while
keeping type safety. A function like dlopen cannot be type safe and is
not provided (or better, this interface is not installed - see the
compiler module Symtable for direct access, it is part of Dynlink).

To ensure type safety at runtime, O'Caml uses interface hashes (MD5
sums). A new module can only access already loaded modules when it knows
the MD5 sums, i.e. is compiled against the same interfaces. So the
reason for the restriction of only being able to "look back" from the
new module to the existing modules is that this scheme opens a way to
check type safety. 

Gerd
-- 
------------------------------------------------------------
Gerd Stolpmann * Viktoriastr. 45 * 64293 Darmstadt * Germany 
gerd@gerd-stolpmann.de          http://www.gerd-stolpmann.de
Telefon: 06151/153855                  Telefax: 06151/997714
------------------------------------------------------------

Re: [Caml-list] The Bytecode Interpreter...

[Jonathan Roewen]

> When one #loads within a toploop, more or less the same happens.
> However, the toploop is a full compiler, and does not only have the
> symbol table, but also the current environment, i.e. the set of
> currently visible types and values with the still-needed parts of their
> definitions. As far as I know, #load does not modify the environment
> (because nothing changes - the loaded modules are already in scope when
> the .cmi file is in the search path).

Yes, but the bytecode itself is not in the environment, or at least
not initialised, hence why you need the #load right? Try using Str
module for instance. Symbols in memory, but that's it.

Anyways, my next question is: does the toplevel need dlopen & friends?
I know dynlink module would, as you stated, it performs relocation and
all that other stuff.

Jonathan

Re: [Caml-list] The Bytecode Interpreter...

[Jacques Garrigue]

> > When one #loads within a toploop, more or less the same happens.
> > However, the toploop is a full compiler, and does not only have the
> > symbol table, but also the current environment, i.e. the set of
> > currently visible types and values with the still-needed parts of their
> > definitions. As far as I know, #load does not modify the environment
> > (because nothing changes - the loaded modules are already in scope when
> > the .cmi file is in the search path).

This is true that #load itself does nothing to the typing environment,
but there is probably a slightly confusing point in that the toplevel
has a not completely static view of its environment. Namely, it
interacts lazily with the filesystem. As a result, the type of a unit
is only fixed the first time its .cmi is loaded. So the toplevel lets
you do strange things such as generating code and loading it on the
fly: you just need to make sure you generate new file names.
This does not negate your point: the toplevel sees its typing
environment as immutable (outside of direct input), and it has no way
to know that any module on the disk is "new".


> Yes, but the bytecode itself is not in the environment, or at least
> not initialised, hence why you need the #load right? Try using Str
> module for instance. Symbols in memory, but that's it.

Sure, but the point is that any code accessing a unit does it assuming
an immutable type for it, that can be verified when loading the
bytecode.
Note that one can do this with Dynlink too: if you load unit A with
dynlink, and unit B later, then unit B can refer to values in unit A.
The only thing the linker doesn't let you do, is to have code that
refers to values that are not yet loaded. And this is true both in the
toplevel and with Dynlink.

> Anyways, my next question is: does the toplevel need dlopen & friends?
> I know dynlink module would, as you stated, it performs relocation and
> all that other stuff.

Yes, sure, it does something similar to dlopen on bytecode. You can
just see the code in topdirs.ml.

Jacques Garrigue

Re: [Caml-list] The Bytecode Interpreter...

[Jonathan Roewen]

Ok, so let me see if I can understand this all correctly. Let's assume
a linux-like environment.

When I compile a bytecode application, it uses the #! thing to execute
ocamlrun, with the app itself (I presume this is bytecode) following.
And this action is the exact same as typing: ocamlrun <bytecodeapp> at
the commandline instead of just ./<bytecodeapp>, right?

Then, the startup code in the bytecode interpreter (ocamlrun) tries to
load itself .. and if it turns out to be the interpreter itself, it
searches for the app as the command line argument, and opens that,
else opens itself (when invoked directly, not via ocamlrun), so that
it can access the bytecode in the file.

At this stage, we 1) don't need dlopen anywhere, and 2) only need
ocamlrun application somewhere for it to be executed.

If I were to use the toplevellib.cma, I'd then need dlopen; however,
the rest of the application flow is exactly the same, correct?

So, to get bytecode running on the bare metal, I'd just need to
implement some libc functionality for ocamlrun, possibly try tell
ocamlc to generate a different #! path to ocamlrun, and be able to
open the bytecode app file using fopen.

This is actually starting to sound doable ;-) Thank you all for your
valuable input to help me learn the intricacies of the ocaml bytecode
interpreter =)

Kindest Regards,

Jonathan Roewen

Re: [Caml-list] The Bytecode Interpreter...

[Jonathan Roewen]

Okay, last question =)

The following is from startup.c in 'byterun' dir.

/* Main entry point when code is linked in as initialized data */

CAMLexport void caml_startup_code(
           code_t code, asize_t code_size,
           char *data, asize_t data_size,
           char *section_table, asize_t section_table_size,
           char **argv)

Is it possible to create my own app that calls this function, instead
of caml_main (since that needs to open files and what not)? If so, how
can I get all the required data to pass to it?

Like, would this work if I had a copy of a bytecode application in memory?

Jonathan

Re: [Caml-list] The Bytecode Interpreter...

[Jonathan Roewen]

Hi once again,

Hopefully this'll be my last problem to solve ;-)

I've got ocamlrun + a bytecode app running on the bare metal, finally =)

The following works fine:

print_endline "Hello, World";;

but, the following fails:

Printf.printf "Hello, World\n%!";;

with a print_endline statement before it, not even that gets run, so
it appears to be a problem with loading the bytecode itself.

The bytecode app is created using ocamlc -output-obj, and the .o file
is linked into my kernel. I then call caml_startup(argv), where argv =
{ "" }.

I've also experienced the same problem (appearing to not load/run the
bytecode) when using Scanf & Hashtbl modules (so it's not isolated to
Printf).

What is the bytecode interpreter trying to do? Any clues? ;-) I'm
trying to debug file open calls and things, but nothing appears to
show up, and I don't get any errors printed to stdout/stderr by the
interpreter.

Jonathan

Re: [Caml-list] The Bytecode Interpreter...

[Jonathan Roewen]

Hmm,

It might not be the interpreter afterall, or at least I'm ending up
with some very volatile machine code =/

Adding a printf() and a clear_screen() just before "res =
caml_interprete(caml_start_code, code_size);"
startup.c/caml_startup_code, and the problematic code runs fine...

So, not sure where the fault lies on this one... =/

On 10/26/05, Jonathan Roewen <jonathan.roewen@gmail.com> wrote:
> Hi once again,
>
> Hopefully this'll be my last problem to solve ;-)
>
> I've got ocamlrun + a bytecode app running on the bare metal, finally =)
>
> The following works fine:
>
> print_endline "Hello, World";;
>
> but, the following fails:
>
> Printf.printf "Hello, World\n%!";;
>
> with a print_endline statement before it, not even that gets run, so
> it appears to be a problem with loading the bytecode itself.
>
> The bytecode app is created using ocamlc -output-obj, and the .o file
> is linked into my kernel. I then call caml_startup(argv), where argv =
> { "" }.
>
> I've also experienced the same problem (appearing to not load/run the
> bytecode) when using Scanf & Hashtbl modules (so it's not isolated to
> Printf).
>
> What is the bytecode interpreter trying to do? Any clues? ;-) I'm
> trying to debug file open calls and things, but nothing appears to
> show up, and I don't get any errors printed to stdout/stderr by the
> interpreter.
>
> Jonathan
>

Re: [Caml-list] The Bytecode Interpreter...

[Damien Doligez]

On Oct 26, 2005, at 11:56, Jonathan Roewen wrote:

> The bytecode app is created using ocamlc -output-obj, and the .o file
> is linked into my kernel. I then call caml_startup(argv), where argv =
> { "" }.

I don't know whether this is the source of your problems, but argv
should end with a NULL:

   argv = { "", NULL }

-- Damien

Re: [Caml-list] The Bytecode Interpreter...

[Jonathan Roewen]

Hi,

I have a question about the vmthreads package. I've been looking at
the source of schedule.c, and am making a small understanding of how
it works.

Is it true that this supports true pre-emption of threads (e.g. even
during a GC cycle)? Also, would it be safe to build an ISR framework
that could wake up a thread waiting on an interrupt to be triggered?
Like if I somehow got it to act like a file descriptor...

Jonathan

Re: [Caml-list] The Bytecode Interpreter...

[Gerd Stolpmann]

Am Samstag, den 29.10.2005, 10:41 +1300 schrieb Jonathan Roewen:
> Hi,
> 
> I have a question about the vmthreads package. I've been looking at
> the source of schedule.c, and am making a small understanding of how
> it works.
> 
> Is it true that this supports true pre-emption of threads (e.g. even
> during a GC cycle)? 

No. Preemption can only happen in the main loop of the bytecode
interpreter.

> Also, would it be safe to build an ISR framework
> that could wake up a thread waiting on an interrupt to be triggered?

The problem is you need realtime behaviour. That means your ISR thread
must have a higher priority than other threads, i.e. you need a
realtime-aware scheduler.

Second, also memory management must be realtime-aware. This is the
difficult part. How to handle the case when the interrupt occurs within
a GC cycle?

The minor GC is not the problem, because it is very fast, and has an
upper limit on the time spent in it.

Major GC: In principle, you can stop it at any time. You should probably
do so when the interrupt occurs. And then? The ISR must not allocate
memory in this case, because the memory manager cannot give it to you in
this moment (major GCs are triggered from minor GCs, so the minor heap
is currently full). It is very difficult to write ISR code that does not
allocate any memory. Maybe a way out is to have further minor heaps only
for this purpose (one heap per realtime thread), but this raises further
questions (how to get it empty again when the ISR is over? What to do if
it becomes full? What to do if you still need a major heap block?)

Compactification: I think this GC mode is totally incompatible with real
time. You cannot stop it, and it takes a very long time.

Gerd

> Like if I somehow got it to act like a file descriptor...
> 
> Jonathan
> 
> _______________________________________________
> 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
> 
-- 
------------------------------------------------------------
Gerd Stolpmann * Viktoriastr. 45 * 64293 Darmstadt * Germany 
gerd@gerd-stolpmann.de          http://www.gerd-stolpmann.de
Telefon: 06151/153855                  Telefax: 06151/997714
------------------------------------------------------------

Re: [Caml-list] The Bytecode Interpreter...

[skaller]

On Sat, 2005-10-29 at 13:29 +0200, Gerd Stolpmann wrote:

> > Also, would it be safe to build an ISR framework
> > that could wake up a thread waiting on an interrupt to be triggered?
> 
> The problem is you need realtime behaviour. That means your ISR thread
> must have a higher priority than other threads, i.e. you need a
> realtime-aware scheduler.
> 
> Second, also memory management must be realtime-aware. This is the
> difficult part. How to handle the case when the interrupt occurs within
> a GC cycle?

The easy way of course: forget about it :)

ISR code only allocates memory on the stack, and it only
accesses its local stack and global variables. All the
real work is done by the kernel, not in the ISRs .. and the
kernel is a single synchronous thread.

Your main problem, IMHO, will be concurrency, not interrupts.
That is -- multiprocessor support. Because typical 
multiprocessor OS shares a lot more data between CPUs,
and runs at least part of the kernel on ALL the CPUs.

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

Re: [Caml-list] The Bytecode Interpreter...

[Jonathan Roewen]

> Your main problem, IMHO, will be concurrency, not interrupts.
> That is -- multiprocessor support. Because typical
> multiprocessor OS shares a lot more data between CPUs,
> and runs at least part of the kernel on ALL the CPUs.

Possibly. I think we'll tackle this by a separate kernel
instance/runtime per processor, and act like they're separate machines
.. akin to distributed programming.

But multiprocessor stuff is a long, long way off.

Re: [Caml-list] The Bytecode Interpreter...

[Damien Doligez]

On Oct 29, 2005, at 13:29, Gerd Stolpmann wrote:

> Major GC: In principle, you can stop it at any time. You should  
> probably
> do so when the interrupt occurs. And then? The ISR must not allocate
> memory in this case, because the memory manager cannot give it to  
> you in
> this moment (major GCs are triggered from minor GCs, so the minor heap
> is currently full).

Actually, in OCaml a major GC slice is triggered right _after_ each  
minor
GC, so the minor heap is always empty when the major GC is running.

-- Damien