Could we use multiple stacks?

[Francois-Rene Rideau]

> Sorry for not posting sooner, I had lots of thinking to do.
   Do not be sorry. I've not gone further than chapter 9
in the rewriting of my paper yet
(http://www.eleves.ens.fr:8080/home/rideau/Tunes/WhyNewOS/Part_1.html),
though I have drafted a lot more.
   Also, I have done little Scheme coding for the project.
   However, I've discovered Joseph Raz' book "The Morality of Freedom",
which is an excellent book; but that's another story.


> As part of that I have implemented a rough approximation of my ideas.
> I've written enough code now that it mostly works.  More then has gone
> before but I still think not quite enough to use as the lll.
   Well, please do publish whatever you're doing:
it may be a good starting point for us all.


>    On Mon, 29 Apr 1996, Eric W. Biederman wrote:
>    > That is could we have (at least logically) 4 stacks.
>    > One for pointers
>    > One for ints
>    > One for floats
>    > One for return values
> 
>    You forgot the return address stack. ;-)
> 
> Not really, My intention was to list the major stacks of ANS forth,
> with an extra one for pointers.

While this method might have advantages,
it poses lots of problems:
* why restrict it to those types ?
 What if the particular application I write need more of them ?
* what if I have a restricted address space,
 but can't statically determine the max size of any of the above,
 though I know the total sum size fits the memory ?
* if I multiply stacks, won't that make thread switching horrible,
 whereas most threads will use only few of them stacks ?
* are you specifying what the user can expect,
 or the way it will be implemented on that particular version of the code,
 without the user being able to trust that behavior in any portable way ?
 [Like the fact that portable ANS Forth programmers
 shouldn't trust extra floating/local/control/whatever stacks
 to be different from the standard data/return stack]


Note that the problem involves:
* dynamism vs statism:
 statically priviledged types may be a burden to high-level applications,
 while low-level code may prefer low-level mixing of types.

* cooperative multithreading:
 threads can be required to explicitly
 save/restore exactly those stack/stack-pointers that they need,
 but this precludes memory sharing with preempted threads
 (not a problem: we already agreed to that).

* portability to systems without MMU:
 only some kind of MMU can allow us to space/time efficiently manage
 a sparse address space that will make multiplication of
 dynamically sized stacks acceptable.

* grain and efficiency of memory allocation+GC:
 reserving stack space for every thread will be very costly,
 which may prevent the fine-grained threading required by Tunes.
 Using a common stack space for all threads with heap-copying of the stack,
 or using space up/down the heap as a scratch pad that is framed to become
 part of the heap during switches,
 are the solutions currently adopted.
    the frame is not homogeneous to the framed data,
 so unless individual data are framed,
 the


To conclude, I don't think it's really useful to multiply stacks.
I think that one or two stacks
plus a fast and efficient general-purpose heap,
is more than enough.
The space at the end of the heap could be used as a scratch stack, too,
which may or not account as one of the above-mentionned stacks.
Surely, the heap could be multiplexed according to the size/type
of the reserved data, but the user shouldn't rely on it.

   Also, the return stack, if separated from the heap scratchpad,
and unless specifically allocated for the current thread,
could be limited to a fixed number of pages:
any kind of deep recursion should be done accross real-time checkpoints,
and hence must regularly allow GC.
Copying stack (the usual method for having light-weight continuations)
is too expensive for such deep recursion,
and heap-based recursion will be much cheaper
(remember: using the GC'ed heap is cheap),
while specifically reserving non-shared space for the stack
would be a good idea if the stack is going to be very deep.

   To me stacks are useful for two things:
visible user interaction,
and caching of temporary low-level data.
In between, high-level programming is better done with
an expressive statically strongly typed language,
where the low-level stacks are invisible,
and high-level stacks are not particularly efficient.


   Of course, let's not be stopped by our possible disagreements:
let's try out everyone's ideas until some of them
(not all forcibly from the same person) prove better than the others...



>    Besides, it really doesn't help with typing things in memory. If we can 
>    get this to be done the same way as on the stack, we gain an enormous 
>    simplification.
> 
> Right the object system ( What provides the types ), and how it is
> implemented is what is important.  What we really need to provide is a
> reflexive (how objects are implemented should be totally up to the
> user) interface to the garbage collector.

   Surely, the HLL needs to keep track of object types;
but that the LLL should remember more than is strictly necessary for GC
is doubtful to me: compiled code should be efficient,
and whenever dynamic reflection is used,
interpretation and/or decompilation (for heavily used routines
-- imposes restrictions on compilation of decompilable routines)
is generally quite an acceptable overhead.


> My current leanings are toward a forth type system that has root
> pointer stack.  Basically anything you aren't sure is referenced to
> from somewhere else would have to be passed on it.  But otherwise you
> can do as you please.  Since ANS forth is all explicit memory
> management we could handle it with no trouble.
   Surely, we be able to reserve and use both GC-scanned and GC-skipped
data space. The later is needed anyway for interrupt-driven threads
and all kinds of raw data.


> I strongly suspece that Garbage collection is not the right solution
> for every memory management task.
   Indeed, GC is NOT the right solution for EVERY mm task,
and there should be ways for the LLL to work without it.
*Static* memory management (again, done by the compiler
with more or less human help) is often a good/necessary solution
to many problems, *when possible*.
(particularly when there's hard real-time/real-space requirement).
   However, a GC is just needed anyway for intrinsically *dynamic* problems,
so we must implement it, and offer support for it inside the (extensible) LLL.


--    ,                                         ,           _ v    ~  ^  --
-- Fare -- rideau@clipper.ens.fr -- 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: "http://www.eleves.ens.fr:8080/home/rideau/Tunes/"