Re: Two stacks at once

[Bill Allombert <allomber@math.u-bordeaux.fr>]

On Wed, Dec 15, 2004 at 10:40:18PM -0800, Ilya Zakharevich wrote:
> Suppose we have two stacks:
> 
>   top1, bottom1, avma1;
>   top2, bottom2, avma2;
>   current_stack;		/* 1 or 2 */
> 
>  At the start: current_stack = 1; top = top1; bottom = bottom1; avma = avma1.
> 
>  There is a macro: SWAP_STACKS(), which resets current_stack, top,
>  bottom and avma.
> 
> Given this, I think one can significantly speed up PARI: instead of
> incessant moving of temporaries on the stack, they are just created on
> the stack corresponding to the depth-of-calls:
> 
>  in a PARI function, before you create temporaries and call other PARI
>  functions, you do SWAP_STACKS(); as a result, the temporaries you
>  need and the result of the call of the PARI functions are created on
>  the other stack; before creating the GEN which is going to be the
>  final result, you SWAP_STACKS() again.  Also, one needs to save/reset
>  OTHER_AVMA at the start/end of the subroutine too.
> 
> If you do so, no movement of GENs on the stack is needed.  Your
> grandkids create the results on "yours" stack, but when these results
> are perused by your children, your stack is clean again.
> 
> What do you think?

We considered various multi-stack scheme but they have 2 problems:

1) Stack overflow might happen in either stacks, so we have to allocate
a suitable amount for each stacks. 

2) We cannot allow recursive objects in a stack to include pointers to the 
other stack, else we will not be able to garbage collect.

Also in practice

1) Given 2) above, making sure objects are created in the correct stack
without requiring extra copy can be painful.

2) Most of the time lazy garbage collecting is nearly as good as a
multi-stack approach.  Karim have developed fast gerepile alternative
that have nearly the same cost as a copy.

3) Switching stacks has a cost.

However, we could decide to follow this course if we rewrite PARI from
scratch one day. Your scheme might be more clever than the one we though
of.

Cheers,
Bill.