ABI of “return objects on the bottom of the stack, continuously” (Re: Two stacks at once)

[Ilya Zakharevich <nospam-abuse@ilyaz.org>]

The quoted message was written ∼19 years ago. — And then I found a
solution “quite soon” — but could not find toits to write this down.

The old discussion is on
  https://pari.math.u-bordeaux.fr/archives/pari-dev-0412/msg00016.html

> On Thu, Dec 16, 2004 at 11:49:19PM +0100, Bill Allombert wrote:
> > That said, the idea of several stacks has a lot of merit, but I don't
> > think we can retrofit it at this stage without major though.

⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜ grepile() is considered harmful

I remind that the idea was to (almost?) completely eliminate
grepile() — which is the most confusing — and thoroughly
unneeded and wasteful — part of the implementation of PARI.

The **need** for grepile() comes from the PARI’s ABI, whose idea is
that

 [[[  objects returned from a subroutine call are allocated on stack  ]]]

Moreover, these returned objects should better (for the purpose of
efficiency of the stack usage) be allocated continuously.  Likewise,
they should better be at the bottom of the stack.

However, the components of recursively built objects are often
constructed using OTHER ancillary subroutine calls.  After such a
call to construct (say) the 3rd component, the stack looks like

   BEFORE … COMPONENT1 COMPONENT2  RESULT-OF-CALL

Now we may need to post-process the RESULT-OF-CALL, and when
COMPONENT3 is finally returned by yet another ancillary call, the
stack becomes

   BEFORE … COMPONENT1 COMPONENT2  RESULT-OF-CALL COMPONENT3

 — and this means that our 3 components are now not adjacent.

⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜ The proposed solution of 2004

Use two stacks alternately: when our caller expects our result to be
on STACKα, we call our ancillary routines when being switched to
STACKβ, and only the FINAL ancillary call during the calculation of
COMPONENT3 is made switching back to STACKα.

Of course, there is a disadvantage: this may IN SOME CASES result in a
waste of memory: it may happen that we need a lot of memory on
STACKβ — while STACKα has a lot of unused memory.

⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜ WORKAROUND — of about 2005 ;—(

Have both stacks use the same chunk of memory!  To avoid collisions,
one of them should grow-down-from-top, the other one
grow-up-from-bottom.

⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜ IMPLEMENTATION

 • Have a new variable stack_dir.
 • Make the stack allocation routines pay attention to stack_dir.
 • (As a stopgap measure) make gerepile() (and friends) pay attention
   to stack_dir.
 • Make the starting value for stack_dir to be settable at the start
   of runtime.

After this, check that the current code works with the “non-standard”
value of stack_dir.  If this ACTUALLY turns out to be feasible:

 • Add a new function flip_stack_dir().
 • Use this function in new code (as described above).
 • (Leisurely,) insert flip_stack_dir() in suitable places in old code
   and remove gerepile() code. 

The bookkeeping data for the stack is currently
     stack_bot    avma   stack_top
(if I did not mix up the names bot/top!).  avma grows when one
allocates objects on stack.  The free area is between avma and
stack_top.

The proposed data for the stack is
    stack_min   avma_min  avma_max   stack_max
The free area is between avma_min and avma_max.  Depending on
stack_dir, avma is aliased to one of avma_min and avma_max, and
stack_top is aliased to the other one of these two.

  (The code taking into account stack_bot needs to be rewritten.)

 (One way to do this is that flip_stack_dir() flips stack_dir, and
  exchanges avma and stack_top.)

Hope this helps,
Ilya