Bytecodes: vm & compiler for guile3

[Jim Blandy <jimb@red-bean.com>]

This is really cool.  I'm quite interested in the space savings.

>The Result
>
>Both compiler and bytecode interpreter work correctly, as far as I
>have tested them: The compiler compiles itself etc. It is pretty complete.
>
>Speed: This subject is really sad. Even though compiled code uses
>about 20% less cells, it needs about 10% more CPU time.
>
>I think that loop conversion and many other costly optimizations 
>would have been necessary so that compiled code runs faster than
>the Guile interpreter. However, does the cost of a big compiler pay if
>it speeds execution up just by few percents?
>
>
>I have to pay respect to the implementors of SCM/Guile:
>It is not a trivial task to overtake their interpreter.

Yes, Aubrey put a lot of work into SCM's speed.  I'm not at all
surprised that a first shot at a bytecode interpreter was slower than
code tuned carefully by its author over several years.

Aubrey argues that bytecode engines have no speed advantage over
SCM-like systems.  I disagree, but that is only my intuition; as far
as I know, the facts at present are on Aubrey's side.  But I believe
that this is because nobody has put as much time into a bytecode
engine as Aubrey has into SCM.  This is an opportunity to change
that.

So, some questions and suggestions:

1) Are you comparing the speed of your engine to the speed of Guile
with debugging enabled, or Guile with debugging disabled, or SCM?  The
latter, I think, is the most worthy opponent.  Aubrey can tell you how
to configure SCM to get fair benchmarks: you want all the typechecking
and argument checking enabled.

2) Are you expanding (let ((var exp) ...) body) to
((lambda (var ...) body) exp ...), in the usual way?  
SCM handles let, let*, letrec, etc. directly; I'll bet your code
spends a lot of time applying lambdas generated from let's.
Addressing this problem is not as hard as doing full lambda removal,
and it would help a lot.  For a full list of the forms Guile/SCM
handles directly in the interpreter, look in libguile/tags.h for the
list starting with SCM_IM_AND.

I agree that the compiler should be kept fast.  It shouldn't be much
trouble to handle a few special forms, if you design the compiler to
be open in the right way.

I think there's a lot of potential in this approach.

1) Analyzing code beforehand allows us to move optimizations out of
the interpreter itself, making it easier to reason about and
maintain.

2) Analyzing code beforehand allows us to lay out local variables in
an array, rather than a linked list, which should speed up variable
references (which are *very* frequent).

3) A bytecode engine can store more control state in an inspectable
form (rather than hiding it in the return addresses of recursive calls
to the interpreter), making it possible to support full debugging with
no slowdown.

Again, I think the lesson from the timing results is just that first-
try solutions aren't sufficient.  You have to refine your approach a
bit.  Zillions of people have written bytecode interpreters, but
you've got a chance to make an interesting statement when you take on
SCM.

I encourage you to continue what you've started.  I would love to do
this myself, but I don't have time at the moment.