The Road to 2.2

The Road to 2.2

[Andy Wingo]

Friends!  Schemers!  Gentle Guilefolk!  The time has come to begin in
earnest on the road to Guile 2.2!

I know all of you are wondering, "did that paragraph really need four
exclamation marks?"  Well the answer is yes, yes it did, and the rest of
this mail lays out the reasons.

So, what does 2.2 mean, why is it appropriate now?  2.2 means many
things on many levels, but on its most basic level, it will result in a
new series of Guile deployments.  This series will be installed in
parallel with Guile 2.0 [0].  It shouldn't disrupt people that develop
or distribute C extensions to Guile or programs written in Guile.  True,
the binary named "guile" on your system might be 2.0 or 2.2, depending
on what you have installed, though one can get around that with passing
--program-suffix to ./configure.  In total, the disruptive impact of a
new series is low.

[0] http://www.gnu.org/software/guile/manual/html_node/Parallel-Installations.html

On the other hand, creating a new development series does have a cost in
splitting our development effort away from the stable branch, and so we
have to justify that.  This is the second part of the question, "why
now?"  The answer is that we have important improvements to make to the
Guile implementation that can't be made in a strictly binary-compatible
way.  We think these things are so exciting as to be worth the
inconvenience of a new stable series.  We might still make a few more
2.0 maintenance releases, but when I describe what we have on tap for
2.2 you will see why we're excited to move to the next phase.

RTL VM
======

Guile 2.0 added a compiler and a virtual machine to what was previously
a pure-interpreter implementation of Scheme.  I know we all are pretty
stoked about that, but some time has passed and it's time to look at
what we have and see how we can do better.

The Guile 2.0 VM is a stack machine.  That means that its instructions
usually take their values from the stack, and produce values (if
appropriate) by pushing values onto the stack.

The problem with stack machines is that they penalize named values.  If
I realize that a computation is happening twice and I factor it out to a
variable, that means in practice that I allocate a stack frame slot to
the value.  So far so good.  However, to use the value, I have to emit
an instruction to fetch the value for use by some other instruction; and
to store it, I likewise have to have another instruction to do that.

For example, in a stack machine, compiling "z = x + y" might mean:

  (local-ref 0) ; x
  (local-ref 1) ; y
  (add)
  (local-set! 2) ; z

The cost of interpreting a bytecode is largely dispatch cost, which is
linear in the number of instructions executed.  So factoring out a
computation to a local variable can sometimes actually cause code to run
slower, depending on the relative cost of the computation versus
accessing its operands.  Pushing and popping values can also be
expensive as we are updating a stack pointer all the time, possibly
checking for overflow as well.

The solution to this problem is to use a "register machine".  I use
scare quotes because in fact this is a virtual machine, so unlike a CPU,
the number of "registers" is unlimited, and in fact they are just stack
slots accessed by index.

So in a register machine, "z = x + y" might be:

  (add 2 0 1) ; register 2 = register 0 + register 1;

Of course the code for a register VM has to be bigger: instead of _byte_
code that doesn't need to encode its operands because they are expected
on the stack, register VM code has to encode the "register names", so it
ends up being better to implement it as _word_ code.  But this cost is
much less significant than the dispatch cost.

Anyway, that's the back-story.  For Guile 2.2, I have implemented a new
register-based virtual machine.  For no good reason I called it the
"RTL" VM, for "register transfer language".  RTL is a name for a
particular kind of intermediate representation in compilers, but perhaps
it isn't the most appropriate denomination for what we're doing.  In any
case the name seems to have stuck.  Perhaps we need a marketing guru
here to find some other compelling name :)

Given that we're changing the bytecode...
=========================================

So RTL is a new bytecode, a new VM, and will ultimately need a new
compiler.  I'll talk a bit more about the compiler in a minute, but I
want to mention another aspect of RTL.

Besides being faster than the Guile 2.0 VM, RTL opens up other
interesting possibilities.  One of the most exciting is the ability to
statically allocate all kinds of data.  In Guile 2.0, when a .go file
loads from disk, it allocates all of the constants that it needs on the
heap.  But that's sub-optimal in many ways.  For example, a pair of
immediates like '(1 . 2) doesn't actually need to be allocated at all --
it can just be part of the loaded image.  Likewise a pair with
non-immediates like ("foo" . "bar") can also be allocated in the image,
but it needs fixing up at runtime so that its fields point to the "foo"
and "bar" values.  In this particular case the "foo" and "bar" would be
values also in the image.

What I mean to say is that we can, at compile time, allocate and lay out
the memory for the constants that a program will need, compute the
minimal set of initializations that those constants will need, and make
the right links from the compiled code to the constants.  This is
exactly like what the C compiler, linker, and dynamic loader do -- so we
take pointers from them and do exactly the same thing.  The RTL branch
writes out compiled data to ELF files.  When a .go file is loaded, it
runs a thunk to do the run-time initializations, then returns the "main"
thunk for the .go (which the caller can run or not).

Note that we use ELF for all platforms.  Since we don't rely on the
platform's linker or dynamic loader, there's no sense in using the
format of each individual platform.  That said, the files that Guile
produces are readable with readelf, and it should be possible to operate
on them with standard ELF tools.

Guile's linker and loader are careful to separate read-only data like
bytecode and writable data like those pairs that need runtime
initialization.  In this way we can maximize sharing between processes.
Also, Guile puts a bunch of data that's not needed in normal execution
at the end of the file, in the read-only section -- like docstrings, for
example.  If a program never asks for procedure-documentation of a
procedure, those docstrings will never be paged in by the kernel; but if
a program does do a lot of documentation grovelling, they are readily
accessible.

Separating the different metadata into different sections also makes it
possible to strip metadata.  For example when deploying to systems with
not much disk space, you might strip docstrings or line number
information.  You can use standard ELF tools to do this, or do it using
Guile's ELF tools.

Finally, using a well-structured format like ELF brings in the
possibility of linking together a number of modules in one file, and
possibly even an entire application.  We don't have this working yet,
and it's not in the immediate plans, but it is a great possibility to
keep in mind.

What about the compiler?
========================

So we have a new VM, assembler, disassembler, and all the things!  It's
pretty close to finished: it's just missing the part that lets a
debugger know about line numbers and local variables.  But how do we
actually produce RTL assembly from Scheme?

Well, there we don't have a finished story.  Noah Lavine made a branch
to compile tree-il, our high-level intermediate language, to a
"continuation-passing-style" (CPS) form.  This is a useful
transformation for many reasons, but among them it is convenient for
giving a "name" to all values -- a property that a register VM prizes.

His CPS compiler isn't done yet, though when I last looked at it, it was
looking great.  So the path goes Scheme -> Tree-IL (something we already
have), then -> CPS (something Noah did), then -> RTL Assembly (again,
Noah), then -> bytecode (the piece I did).  It doesn't yet work with all
of Guile but it's getting there.

How to get there?
=================

However, I think we've done all we can in branches.  I think we should
bless this RTL experiment as the way to do Guile 2.2.  (Thoughts or
objections welcome.)  To that end, I think we need to start merging
wip-rtl into master.

What I propose is that, if we agree, I start merging in trivial stuff.
When I get to something interesting that's not just a refactoring of
existing things, I'll submit that patch to the list.  We have a few days
to look at it, we go through some review, and then we figure out how to
move forward -- usually merging some version of that patch.  Then we
repeat.

Once the RTL branch is all merged in, we can start doing the same with
Noah's wip-rtl-cps branch.

Then eventually some glorious day comes and we start using the CPS/RTL
toolchain, everything is working great and fast, and we start deleting
the old code.

What do you all think?

I love it when a plan comes together!

Cheers,

Andy
-- 
http://wingolog.org/

Re: The Road to 2.2

[Nala Ginrut]

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

Nice guys~ very impressive work!
I saw that our current ELF just wraps the .go code, not the native code.
Maybe it's possible to try a naive AOT compiler now. IMO, translate RTL
bytecode to native asm code, say, i386 assemble code. Then call gas to
assemble it.

I do know Andy's expectation is to write that "translator"  and native
assembler all in Guile. But I think it's cool to try a simpler one first.

Comments?

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

Re: The Road to 2.2

[Andy Wingo]

Hi,

On Sat 18 May 2013 07:00, Nala Ginrut <nalaginrut@gmail.com> writes:

> I saw that our current ELF just wraps the .go code, not the native code.

This is imprecise.  Think of ".go" and "ELF" as containers for code and
data.  It doesn't make sense to wrap a container in a container :)

Currently in stable-2.0, the code is Guile 2.0 stack machine code, and
the container is .go.  In master, the code is stack machine code, and
the container is ELF.  In wip-rtl, the code is RTL code, and the
container is ELF, and constants and such have their own sections in the
ELF.  There are some 12 or 14 sections per file.

> Maybe it's possible to try a naive AOT compiler now.

I think now is probably not the time.  I do think we will do native
compilation soon but probably not for 2.2.  I don't think we will be
able to change the VM, assembler, linker, loader, disassembler, and
compiler, *and* add support for native compilation (for some
architectures) in the 2.2 series.

Regards,

Andy
-- 
http://wingolog.org/

Re: The Road to 2.2

[Noah Lavine]

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

This is very exciting! I have a very small question, based on something I
think you said earlier - since the container will be ELF, will we call our
files .so now?

Noah


On Fri, May 17, 2013 at 5:49 PM, Andy Wingo <wingo@pobox.com> wrote:

> Friends!  Schemers!  Gentle Guilefolk!  The time has come to begin in
> earnest on the road to Guile 2.2!
>
> I know all of you are wondering, "did that paragraph really need four
> exclamation marks?"  Well the answer is yes, yes it did, and the rest of
> this mail lays out the reasons.
>
> So, what does 2.2 mean, why is it appropriate now?  2.2 means many
> things on many levels, but on its most basic level, it will result in a
> new series of Guile deployments.  This series will be installed in
> parallel with Guile 2.0 [0].  It shouldn't disrupt people that develop
> or distribute C extensions to Guile or programs written in Guile.  True,
> the binary named "guile" on your system might be 2.0 or 2.2, depending
> on what you have installed, though one can get around that with passing
> --program-suffix to ./configure.  In total, the disruptive impact of a
> new series is low.
>
> [0]
> http://www.gnu.org/software/guile/manual/html_node/Parallel-Installations.html
>
> On the other hand, creating a new development series does have a cost in
> splitting our development effort away from the stable branch, and so we
> have to justify that.  This is the second part of the question, "why
> now?"  The answer is that we have important improvements to make to the
> Guile implementation that can't be made in a strictly binary-compatible
> way.  We think these things are so exciting as to be worth the
> inconvenience of a new stable series.  We might still make a few more
> 2.0 maintenance releases, but when I describe what we have on tap for
> 2.2 you will see why we're excited to move to the next phase.
>
> RTL VM
> ======
>
> Guile 2.0 added a compiler and a virtual machine to what was previously
> a pure-interpreter implementation of Scheme.  I know we all are pretty
> stoked about that, but some time has passed and it's time to look at
> what we have and see how we can do better.
>
> The Guile 2.0 VM is a stack machine.  That means that its instructions
> usually take their values from the stack, and produce values (if
> appropriate) by pushing values onto the stack.
>
> The problem with stack machines is that they penalize named values.  If
> I realize that a computation is happening twice and I factor it out to a
> variable, that means in practice that I allocate a stack frame slot to
> the value.  So far so good.  However, to use the value, I have to emit
> an instruction to fetch the value for use by some other instruction; and
> to store it, I likewise have to have another instruction to do that.
>
> For example, in a stack machine, compiling "z = x + y" might mean:
>
>   (local-ref 0) ; x
>   (local-ref 1) ; y
>   (add)
>   (local-set! 2) ; z
>
> The cost of interpreting a bytecode is largely dispatch cost, which is
> linear in the number of instructions executed.  So factoring out a
> computation to a local variable can sometimes actually cause code to run
> slower, depending on the relative cost of the computation versus
> accessing its operands.  Pushing and popping values can also be
> expensive as we are updating a stack pointer all the time, possibly
> checking for overflow as well.
>
> The solution to this problem is to use a "register machine".  I use
> scare quotes because in fact this is a virtual machine, so unlike a CPU,
> the number of "registers" is unlimited, and in fact they are just stack
> slots accessed by index.
>
> So in a register machine, "z = x + y" might be:
>
>   (add 2 0 1) ; register 2 = register 0 + register 1;
>
> Of course the code for a register VM has to be bigger: instead of _byte_
> code that doesn't need to encode its operands because they are expected
> on the stack, register VM code has to encode the "register names", so it
> ends up being better to implement it as _word_ code.  But this cost is
> much less significant than the dispatch cost.
>
> Anyway, that's the back-story.  For Guile 2.2, I have implemented a new
> register-based virtual machine.  For no good reason I called it the
> "RTL" VM, for "register transfer language".  RTL is a name for a
> particular kind of intermediate representation in compilers, but perhaps
> it isn't the most appropriate denomination for what we're doing.  In any
> case the name seems to have stuck.  Perhaps we need a marketing guru
> here to find some other compelling name :)
>
> Given that we're changing the bytecode...
> =========================================
>
> So RTL is a new bytecode, a new VM, and will ultimately need a new
> compiler.  I'll talk a bit more about the compiler in a minute, but I
> want to mention another aspect of RTL.
>
> Besides being faster than the Guile 2.0 VM, RTL opens up other
> interesting possibilities.  One of the most exciting is the ability to
> statically allocate all kinds of data.  In Guile 2.0, when a .go file
> loads from disk, it allocates all of the constants that it needs on the
> heap.  But that's sub-optimal in many ways.  For example, a pair of
> immediates like '(1 . 2) doesn't actually need to be allocated at all --
> it can just be part of the loaded image.  Likewise a pair with
> non-immediates like ("foo" . "bar") can also be allocated in the image,
> but it needs fixing up at runtime so that its fields point to the "foo"
> and "bar" values.  In this particular case the "foo" and "bar" would be
> values also in the image.
>
> What I mean to say is that we can, at compile time, allocate and lay out
> the memory for the constants that a program will need, compute the
> minimal set of initializations that those constants will need, and make
> the right links from the compiled code to the constants.  This is
> exactly like what the C compiler, linker, and dynamic loader do -- so we
> take pointers from them and do exactly the same thing.  The RTL branch
> writes out compiled data to ELF files.  When a .go file is loaded, it
> runs a thunk to do the run-time initializations, then returns the "main"
> thunk for the .go (which the caller can run or not).
>
> Note that we use ELF for all platforms.  Since we don't rely on the
> platform's linker or dynamic loader, there's no sense in using the
> format of each individual platform.  That said, the files that Guile
> produces are readable with readelf, and it should be possible to operate
> on them with standard ELF tools.
>
> Guile's linker and loader are careful to separate read-only data like
> bytecode and writable data like those pairs that need runtime
> initialization.  In this way we can maximize sharing between processes.
> Also, Guile puts a bunch of data that's not needed in normal execution
> at the end of the file, in the read-only section -- like docstrings, for
> example.  If a program never asks for procedure-documentation of a
> procedure, those docstrings will never be paged in by the kernel; but if
> a program does do a lot of documentation grovelling, they are readily
> accessible.
>
> Separating the different metadata into different sections also makes it
> possible to strip metadata.  For example when deploying to systems with
> not much disk space, you might strip docstrings or line number
> information.  You can use standard ELF tools to do this, or do it using
> Guile's ELF tools.
>
> Finally, using a well-structured format like ELF brings in the
> possibility of linking together a number of modules in one file, and
> possibly even an entire application.  We don't have this working yet,
> and it's not in the immediate plans, but it is a great possibility to
> keep in mind.
>
> What about the compiler?
> ========================
>
> So we have a new VM, assembler, disassembler, and all the things!  It's
> pretty close to finished: it's just missing the part that lets a
> debugger know about line numbers and local variables.  But how do we
> actually produce RTL assembly from Scheme?
>
> Well, there we don't have a finished story.  Noah Lavine made a branch
> to compile tree-il, our high-level intermediate language, to a
> "continuation-passing-style" (CPS) form.  This is a useful
> transformation for many reasons, but among them it is convenient for
> giving a "name" to all values -- a property that a register VM prizes.
>
> His CPS compiler isn't done yet, though when I last looked at it, it was
> looking great.  So the path goes Scheme -> Tree-IL (something we already
> have), then -> CPS (something Noah did), then -> RTL Assembly (again,
> Noah), then -> bytecode (the piece I did).  It doesn't yet work with all
> of Guile but it's getting there.
>
> How to get there?
> =================
>
> However, I think we've done all we can in branches.  I think we should
> bless this RTL experiment as the way to do Guile 2.2.  (Thoughts or
> objections welcome.)  To that end, I think we need to start merging
> wip-rtl into master.
>
> What I propose is that, if we agree, I start merging in trivial stuff.
> When I get to something interesting that's not just a refactoring of
> existing things, I'll submit that patch to the list.  We have a few days
> to look at it, we go through some review, and then we figure out how to
> move forward -- usually merging some version of that patch.  Then we
> repeat.
>
> Once the RTL branch is all merged in, we can start doing the same with
> Noah's wip-rtl-cps branch.
>
> Then eventually some glorious day comes and we start using the CPS/RTL
> toolchain, everything is working great and fast, and we start deleting
> the old code.
>
> What do you all think?
>
> I love it when a plan comes together!
>
> Cheers,
>
> Andy
> --
> http://wingolog.org/
>
>

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

Re: The Road to 2.2

[Andy Wingo]

Hi :)

On Sat 18 May 2013 15:44, Noah Lavine <noah.b.lavine@gmail.com> writes:

> I have a very small question, based on something I think you said
> earlier - since the container will be ELF, will we call our files .so
> now?

We certainly can.  Is it a good idea though?  It might conflict with .so
Makefile rules in some systems.  Maybe we can get around that, though.
Also there are some platforms on which a .so can be e.g. a Mach-O file;
not sure if that is relevant.

What do you think?

Andy
-- 
http://wingolog.org/

Re: The Road to 2.2

[Ludovic Courtès]

Andy Wingo <wingo@pobox.com> skribis:

> On Sat 18 May 2013 15:44, Noah Lavine <noah.b.lavine@gmail.com> writes:
>
>> I have a very small question, based on something I think you said
>> earlier - since the container will be ELF, will we call our files .so
>> now?
>
> We certainly can.  Is it a good idea though?

I’d vote for keeping .go, or at least something different from
commonly-used extensions like .so.

Ludo’.

Re: The Road to 2.2

[Ludovic Courtès]

Hello!

This is all very exciting!

Andy Wingo <wingo@pobox.com> skribis:

> However, I think we've done all we can in branches.  I think we should
> bless this RTL experiment as the way to do Guile 2.2.  (Thoughts or
> objections welcome.)  To that end, I think we need to start merging
> wip-rtl into master.
>
> What I propose is that, if we agree, I start merging in trivial stuff.
> When I get to something interesting that's not just a refactoring of
> existing things, I'll submit that patch to the list.  We have a few days
> to look at it, we go through some review, and then we figure out how to
> move forward -- usually merging some version of that patch.  Then we
> repeat.

Sounds like a good plan.

> Once the RTL branch is all merged in, we can start doing the same with
> Noah's wip-rtl-cps branch.

I’m unclear on what the safest or easiest approach is.  My natural
tendency would have led me to start by “just” rewriting the
GLIL->assembly pass, and only then go with the fancy CPS compiler.
But I gather that the CPS compiler may facilitate the conversion to
assembly.

What’s your take on this?

> Then eventually some glorious day comes and we start using the CPS/RTL
> toolchain, everything is working great and fast, and we start deleting
> the old code.

Looking forward to that day.  :-)

Ludo’.

Re: The Road to 2.2

[Andy Wingo]

Hi,

On Mon 20 May 2013 00:06, ludo@gnu.org (Ludovic Courtès) writes:

>> Once the RTL branch is all merged in, we can start doing the same with
>> Noah's wip-rtl-cps branch.
>
> I’m unclear on what the safest or easiest approach is.  My natural
> tendency would have led me to start by “just” rewriting the
> GLIL->assembly pass, and only then go with the fancy CPS compiler.
> But I gather that the CPS compiler may facilitate the conversion to
> assembly.
>
> What’s your take on this?

Dunno.  So GLIL is a pretty useless layer that won't have much purpose
in any RTL compiler I think.  The RTL assembler and linker provide some
of the facilities of GLIL like handling constants and meta-data, so I
think it's reasonable to go directly from tree-il or CPS to RTL.

One thing that would be possible would be a conversion to ANF -- still
tree-il, but with names for all temporary values -- then you run the
existing "analyze" pass that allocates local slots, and you hack the
tree-il->glil compiler to become a tree-il->rtl compiler.  That's
probably the lowest-risk thing to do.  But it is also a shame in some
ways, and still has some unknowns.  I'll start working with Noah's
code soon and give a better impression then.

Cheers,

Andy
-- 
http://wingolog.org/

Re: The Road to 2.2

[Noah Lavine]

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

On Sun, May 19, 2013 at 6:02 PM, Ludovic Courtès <ludo@gnu.org> wrote:

> Andy Wingo <wingo@pobox.com> skribis:
>
> > On Sat 18 May 2013 15:44, Noah Lavine <noah.b.lavine@gmail.com> writes:
> >
> >> I have a very small question, based on something I think you said
> >> earlier - since the container will be ELF, will we call our files .so
> >> now?
> >
> > We certainly can.  Is it a good idea though?
>
> I’d vote for keeping .go, or at least something different from
> commonly-used extensions like .so.
>

I don't think it's a big deal, but the reason I asked was that I'm afraid
.go will become increasingly popular because of the Go language. .so also
sort of hints at native compilation in the future, although that's not a
very strong reason to choose it.

Noah

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

Re: The Road to 2.2

[Nala Ginrut]

On Wed, 2013-05-22 at 00:23 -0400, Noah Lavine wrote:
> On Sun, May 19, 2013 at 6:02 PM, Ludovic Courtès <ludo@gnu.org> wrote:
> 
> > Andy Wingo <wingo@pobox.com> skribis:
> >
> > > On Sat 18 May 2013 15:44, Noah Lavine <noah.b.lavine@gmail.com> writes:
> > >
> > >> I have a very small question, based on something I think you said
> > >> earlier - since the container will be ELF, will we call our files .so
> > >> now?
> > >
> > > We certainly can.  Is it a good idea though?
> >
> > I’d vote for keeping .go, or at least something different from
> > commonly-used extensions like .so.
> >
> 
> I don't think it's a big deal, but the reason I asked was that I'm afraid
> .go will become increasingly popular because of the Go language. .so also
> sort of hints at native compilation in the future, although that's not a
> very strong reason to choose it.
> 

How about .glc or .glo?
But anyway, I don't think we should yield against a competitor.

> Noah