Re: Who invented the cactus stack?

mdp2 <M.D.Poole@ukc.ac.uk> asked:


      > Can anyone help me to locate a literature reference for the concept of
      > a Cactus Stack?


In article 95-11-083 hbaker@netcom.com (Henry Baker)
replied:


      I don't know if they 'invented' it, but a popular reference is Bobrow &
      Wegbreit, Communications of the ACM, Oct. 1973.


      Some people call this 'spaghetti', rather than 'cactus'....


Tree-like activation record structures (= stack frame) are required by
control structures like co-routines and threads (let's call them
"threads" generically). A more limited form of structure is needed
for handling "upwards funarg" in Lisp.


There are several ways of implementing such tree-like structures.


(A) One is to allocate each activation record on the heap, and link it
back to the logically surrounding activation record. This is the
method used by most Simula 67 implementations, I believe. The
original implementations of Lisp 1.5 used the heap for the name
records (the a-list), but not for control activations. The advantage
of this technique is that it is simple and uniform, and never runs out
of memory for any particular thread unless there is no more memory
left globally. It also is parsimonious of address space. On the
other hand, activation record allocation and deallocation are more
expensive than in stack-based approaches. It may also have poorer
locality (cache) properties than the other approaches.


(B) Another is to allocate a fixed-size stack whenever you spawn a new
parallel thread. This has all the efficiency advantages of an
ordinary stack, but means that each thread has its own allocation
limit, which may run out long before global memory is exhausted. This
is the method that is implicitly assumed in Ada, for instance, by the
length clause for tasks. It is also the model imposed by library
extensions to stack implementations (like C's pthreads), since each
thread operates exactly as on a single linear stack. It will work
well if the stack requirements of a thread can be predicted
accurately, or if address space is cheap (as on many virtual memory
architectures). It does impose, however, a minimal cost of one
virtual memory page per stack. At the time the Bobrow and Wegbreit
paper was written, both address space and memory were expensive. (I
believe both were working on PDP-10's at the time, with an 18-bit word
address; Bobrow, at BBN, presumably on Tenex, which had paging, but
Wegbreit, at Harvard, on TOPS-10, which did not.)


(C) Yet another technique combines the advantages of these two
techniques by basically allocating activation records in a stack-like
way, but also providing for links among records. It uses a stack-like
piece of memory in a heap-like way. This is the technique described
in the Bobrow and Wegbreit paper. This has the advantage of being
relatively parsimonious of address space, and of being just about as
efficient as a pure stack when multiple stacks are not in use. On the
other hand, it can be wasteful of address space and of memory with
certain patterns of use, e.g. when two co-routined threads recurse
deeply, calling each other, and then one returns, leaving the other
one far into the stack.


I haven't been able to find an early use of the terms "cactus stack"
and "spaghetti stack" in a quick search of the literature. My
intuition is that (B) is a "cactus stack", because it has linear
pieces of stack connected at their bases, while (C) is a "spaghetti
stack" because the pieces of various stacks are intermixed. (A) is
not a stack approach at all, but a heap approach.


Bobrow and Wegbreit mention approach (A) as "fairly straightforward";
and in fact it had been used in Simula for several years before their
paper. They do not mention approach (B), probably because, although
obvious, it was prohibitively inefficient in their computational
environment. And they use neither the term "spaghetii" nor "cactus"
in their CACM paper. However, later papers (e.g. Kearns82) do refer
to their approach as "spaghetti stacks".


Which approach is appropriate depends (as usual) on the context. In a
context of large numbers of small, short-lived threads, the heap or
the spaghetti approach are probably best. For large, long-lived
threads, the dedicated stack ("cactus") approach (B) is probably best
when virtual memory allows preallocation of large chunks of address
space cheaply. I suspect that most implementations in production
environments these days are cactus and not spaghetti or heap.
Experimental or academic languages, on the other hand, generally use
heaps. I am not aware of current use of spaghetti stacks, but I would
be interested to hear of any.


In summary, Bobrow and Wegbreit _should_ be credited with the concept
but perhaps not the name "spaghetti stacks", but _not_ with the
concept of "cactus stacks".


Any additional information on this would be welcome.


-s




Kearns82: John P. Kearns, Carol J. Meier, Mary Lou Soffa, _The
Performance Evaluation of Control Implementations_, IEEE Trans. on
Soft. Eng. SE-8:2:89 (March 1982).
[IBM mainframe PL/I used method C at least as early as 1970. Sure was a lot
of crud in the procedure prologs and epilogs. -John]
--

Return to the comp.compilers page.
Search the comp.compilers archives again.