Re: Byte-code compilation - good for loading.

[Telford Tendys <telford at eng dot uts dot edu dot au>]

> > * I believe a bytecode interpreter could provide much higher code
> > density than the current representation.  If Guile is stretching the
> > processor's data cache, this might improve speed, too.
> 
> Hmm. A `bytecode' in the notion of a different storage format
> than scheme source would certainly be a Big Win. But how do you
> want to strech the processor's data cache, if we always have to
> interpret the next byte code?
> 
> Bytecode has it's advantages, but speed surely isn't one of them :)

In a word, pointers.

For example, the current guile tree uses pointers from the CDR of
one cell to the CAR of the next. Thus half the data being pumped into
the CPU is pointer data for the linked lists. Now the CPU can very
easily make use of these pointers -- just throw the pointer into the
MMU and we are away -- so the CPU can get a lot done with a minimum
number of clocks. However, the memory bandwidth for actual instructions
and data is halved and memory bandwidth is what tends to hold you back.

With current guile implementation, the minimum size for any operation
is 64 bits (one cell). In a bytecode, many operations get by on 8 bits
-- this is (at best) a factor of 8 to 1 saving. In reality it might
translate to a 2 to 1 saving. Also, bytecodes can make use of small
8 bit and 16 bit relative indirection (just like CPU opcodes do) and
all those bits add up.

Thus, when speed is determined by CPU cache, the highest density
of code will be faster, regardless of the extra clock cycles required
for the CPU to decode the instruction. Consider the typical inteL system
with a 550MHz CPU running over 100MHz RAM. Since the CPU can often do
two things at once, you get probably 10 opcodes executed for every
memory access. This is why CPU cache and code density is so important.

The Oberon/Juice people seem to believe that their format is higher
density than (Java) bytecodes. I'm using linux so I can't run their
development kit, nor can I be bothered finding a W95 machine and setting
it all up. I would presume that it is not a pointer based tree since
pointers would not make sense being sent over the internet, presumably
they have some other tree encoding that avoids the space-waste and
unportability of pointers. If anyone knows where their format is documented
then feel free to speak up, from reading their web page I got the feeling
they had gone out of their way to avoid providing any detailed technical
information.

 > * I believe a bytecode could be a better target for multiple language
> > support than Scheme.  I think common target languages should be very
> > low-level and concrete, since this leaves more implementation choices
> > in the hands of language-specific code, where they can be decided
> > appropriately.
> 
> Or a tree-representation like gcc.

Try running gcc on a 64 bit machine, notice how slow it is.
The reason is, once again, pointers and memory bottleneck.
Not that I'm against a tree representation, I like tree representations,
it's just an issue of how to encode them in a space efficient manner.

The other encoding issue that has burnt the LISP community for years
is how to write a cyclic list to a file so that it loads back in as a
cyclic list. Since you can't write pointers to a file, you have a lot
of difficulty with this one. Bytecode CAN handle this because it
just uses a relative indicrection which can be saved exactly as it is
-- completely relocatable and supports cyclic structures as tangled
as you like.

> You think of the GVM, Guile Virtual Machine, just like the JVM,
> so that languages can be compiled into it? I don't know wether
> that's a really good idea :]

I think it has some good and bad points. If GVM is going to be
like JVM then why not be lazy and just use JVM anyhow? Then you
end up with something like kawa. Possibly we could find a cut-down
subset of JVM that was good enough to use but not too difficult
to build an evaluator for.

If GVM is going to be different from JVM then where would the
important differences be and why introduce them?

> A few things that might be helpful to those who have more
> knowledge than me in this matter..
> 
> Bytecode (or binary format, or whatever) enhances loading
> speed, e.g. (read)-speed, not necessarily (eval)-speed.

It will always enhance reading speed over plain text scheme
and will sometimes be faster to eval than the current pointer-linked
tree that we use (depending on cache as mentioned above).

> Guile should have an internal format that can be written out,
> just like .elc oder .pyc, because loading speed is important
> sometimes :)

I agree here, once again, the pointers and possible cyclic
links are what makes the internal format difficult to write out.

> If this format can then be easily translated into gcc's tree
> representation, we would all of a sudden have a very good
> compiler. But that could wait for some other time. (it surely
> needs improvements on the gcc side of things)
> 
> A normal bytecode throws away too many information that can be
> useful (see juice). We should think about this twice.

Is there a ``normal'' bytecode? I presume you mean stack-based
bytecode as used by Java...

> So in conclusion, what i think we (we? those who understand guile
> better, and me maybe if i find the time to read into guile more
> than i have now, instead of telling everyone what "we" should do
> *cough*) should do is:
> - Define an internal tree format (maybe based on the current one)
>   which can be written out and read in easily.

and make it dense.

>   This format should be chosen in a way that it makes a parsing
>   in (read) almost unnecessary.
> - (eval) should be more abstracted from (read).
>   Ideally it shouldn't modify anything in the tree structure.
>   That could be done by a special optimize function?

There are actually a few more points missing. First one is
SMOBs which may be user-defined in some special application
(remember that people might use Guile as an embedded scripting
langauge). So some application defines an SMOB, gets all that
stuff working and then tries to write some internal structure to
a file -- how does guile know what to do with SMOBs in its structures?

There are already some SMOBs that will never write correctly,
for example, you cannot try to save a port and then expect the
port to load back up in its previous state. OK, in some cases
agreeing that no solution is possible is better than trying to
think up some patchy thing that won't work properly. However,
what about saving a lambda expression, or an environment to a file?
I see no reason (in principle) why that cannot work. To a some
extent Java has the ability to do this because all functions are
stored as compiled bytecode.

Second thing is modular Guile extensions. Suppose I write a module
to handle rational numbers, then I save my internal structures to a
file and later want to load that file back in... it will only work
if I have the same rational-number module loaded up first so that I can
make sense of the structures that I am reading. Java embeds the names
of all the prerequisite modules in its modules so that loading
the leaf implicitly loads up the tree (presumably in the correct order
of root upwards). Then there's all the ``beans'' stuff that is supposed
to load up the correct code along with whatever data you load
(I've never seen this work, maybe someone else is more familiar here).

The point is that whatever save-file format you use must have some
way of telling the interpreter what code will be necessary to read
this save-file -- otherwise the interpreter is not extensible.
The save-file could contain the code or it could contain some way of
naming the code.

In short, there is some major work to be done if Guile wants to
follow this route.

	- Tel