Re: alloca and GC

[Keisuke Nishida]

At 30 Jan 2001 18:44:58 +0200,
Michael Livshin wrote:
> 
> > Actually, I rather think that even if alloca was available, that it is
> > questionable whether it should be used, following the argumentation that
> > was posted to this list before by others:  The stack has to be
> > conservatively scanned, i. e. alloca-ting large regions on the stack for
> > bytecode increases the amount of memory that has always to be scanned,
> > independent of how clever a potential generational garbage collection
> > might be implemented.
> 
> that's right, assuming we don't change the GC to deal with bytecode
> stacks intelligently.  which is possible to do, I believe.  you just
> need to somehow "mark" the beginning and the end of the stack regions
> where the bytecode is executing.

Right, and that's what librep seems to be doing.  This can be one
solution once the vm is fully integrated with Guile, which won't
happen immediately.

> > Maybe I missed some point in the beginning of the discussion, but what
> > is the major benefit of using alloca in contrast to an ordinary
> > malloc in this particular case?  Doesn't bytecode have to be stored on the
> > heap anyway, belonging to some function object?
> 
> so you can `alloca' enough space on the current stack frame for all
> the locals.  you get the number of locals from the (compiled)
> applicable object (closure, smob, ...) that you are about to execute.
> but I didn't look at Keisuke's code yet.

In my current implementation, a vm has a single large stack, where
temporary data, local variables, and frames are stored.  I need to
protect them somehow.

The following is a brief description of how my vm works.  This is
the program to be executed:

  (let ((x 1) (y 2)) (foo x y)) ==

    (push 1)
    (popl x)
    (push 2)
    (popl y)
    (pushl x)
    (pushl y)
    (pushv foo)
    (call 2)
    (return)

Whenever a program is called, a new frame is created as follows:

          Stack
    |                |
    +----------------+
    | Local var 1: x |
    | Local var 2: y | <- fp
    | Program        |         Frame
    | Dynamic link   |
    | Return address | <- sp
    +----------------+
    |                |

Instruction `push' appends an object at the end of the stack.
`pushl' and `popl' operate on local variables.  `pushv' pushes
the value of a module variable.

After execution of (pushv foo), the stack will look like this:

    +-------+
    | x = 1 |
    | y = 2 | <- fp
    | other |
    +-------+
    |   1   |
    |   2   |
    |#<foo> | <- sp

When `call' is called, the vm creates a new frame and continues:

    +-------+
    | x = 1 |
    | y = 2 |
    | other |
    +-------+
    |   1   |
    |   2   | <- fp
    | other | <- sp
    +-------+
    |       |

So, these objects on the stack must be marked by the vm.
If I use alloca to allocate a stack, I don't need to do that.
If I use malloc, I need to write a mark function explicitly.
The problem is that the value of `sp' above is not visible
in the mark function of the stack.  This means that I have
to store the value of `sp' in an external variable before
all possible GC, which is a little bit tedious.

But thinking for a while, I noticed that the same thing
happens with the "alloca + save stack range" approach,
so I'll continue using malloc anyway..

Kei