Could we use multiple stacks?

Francois-Rene Rideau
Fri, 17 May 1996 16:15:57 +0200 (MET DST)

> With regards to my suggeseted root pointer stack.  Here is how I think
> it will be useful.  First a garabage collector has to have a set of
> root pointer to start it's collection with.  Having a stack reserved
> for this purpose seems to be an almost ideal way to manipulate and
> implement that aspect of the garbage collector.
But how will you garbage collect that stack ?
Why not just GC the data stack ?
Perhaps you just mean separate a "Data" stack from a "pointer" stack ?
How much would that help ?
Then what about doing the same for the return stack ?

Well, anything could be tried.
What is important is that threads can clean up their state before a switch,
and that reserving space on the heap may cause a switch.
Now, please remember that checkpoints and allocation points
need clean up only if there is an actual switch,
and that preallocating time/space should be possible,
just by inserting a checkpoint just before a routine,
or inserting a large multi-heap allocation that accounts for all
needed objects before to actually initialize them.
I don't know how hard are the requirements for real-time GC,
but I think it is that all allocation points should be clean anyway,
so that we should keep our requirements for "clean" simple
(problem: what about registers -- which are GC'ed values, if any ?).
(other problem: can a real-time GC do weak pointers ?)
-- I really should read again Henry Baker's articles...

> In addition there are
> some applications that heavily manipulate anonymous objects and have
> pointer sprawl all over the place.  Additionally it could be that any
> single pointer is the only pointer to an object, in these pointer
> intense applications, so passing those pointers on the root pointer
> stack would be ideal.
   Still, if you allow pointers on the data stack, I see no
advantage in a specific pointer stack.
   Also, I wonder how well we can mix linear logic and transactions for
the persistent store. It will also require uniqueness annotation of types
at the HLL level if we don't want to call twice a continuation that
uses a root pointer stack that follows linear logic.

[Stack continuations being framed on heap]
> All pushes are at the top of the stack, but if you happen to be in a
> frame that isn't at the top of the stack your pops work find but when
> you next push you generate a new frame.  Carried to an extreme all
> stacks could be simply various continuations at different states of
> the same original stack.  A particular advantage to this kind of
> arrangment is that garabage collecting stack frames is realivily
> cheap.

That's what I proposed in early messages here
(using some heap scratch pad as the stack, and framing when needed).
However, copying stack is needed for continuations anyway,
so if we're to allow full-fledged, continuations that can be called
several times, let's not pop inside heap-allocated continuations,
but just copy the framed continuation to the stack so we use it.
I'd be sorry that every instruction should look at the stack for every
argument, to see if it's in the current frame or the previous one,
so framing should be explicit at the LLL, while the HLL can handle it
implicitly. Really, stack copying is good. If you're afraid to copy
long stacks often, just explicitly frame the seldom-used old part,
so that each thread-switch will only copy the very-used recent part.

> The other thing I am considering and will help to some exten is a
> calling convention that specifically buffers stacks, and global
> variables in registers.  When compiling the compiler simply looks at
> the description of the function to see which variables need to be in
> which registers before the function is called.  This has the potential
> to make very good use of the registers.  Especially if someone ever
> writes a global optimizer.  Currently I support it, but I my compiler
> can't generate that expects things in registers.
Actually, that was one of my early requirements for my project compiler,
even before the Tunes project began :)

> I was thinking that there should be some kind of interface like.
> GC says to an object:  Give me your pointers
> GC says to an object:  These are you new pointer values
> GC says move to place x:  Object moves
> GC asks what kind of things do thes pointer point to:
That's also what I proposed for a more complex implementation
where GC-type would be determine from the page an object is in.
Weak pointers and finalizers could be implemented this way, too.
All this needn't be done in our very first implementation,
that would be the unoptimized general case.

--    ,                                         ,           _ v    ~  ^  --
-- Fare -- -- Francois-Rene Rideau -- +)ang-Vu Ban --
--                                      '                   / .          --
Join the TUNES project for a computing system based on computing freedom !
                 TUNES is a Useful, Not Expedient System
WWW page at URL: ""