Ilya Zakharevich on Fri, 17 Dec 2004 05:44:09 +0100


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: Two stacks at once


On Thu, Dec 16, 2004 at 11:49:19PM +0100, Bill Allombert wrote:
> > My hope was that no change to existing code is *needed*.  One *can*
> > use stack switching to optimize performance.  If it is used often
> > enough, one gets the "stack randomization effect" described above,
> > when you may use each-stack-of-lower size for the same calculation.
> 
> We would still need to identify what routine could benefit from
> the scheme and to update them. Do you have some candidates ?

As you said, as the first step one needs to avoid things which recurse
to GENs already-existing on stack.  Otherwise, things where gerepile()
may take significant portion of computation time are the natural
candidates.

> The idea is to make the garbage collection unfrequently so that the
> overall cost is negligible.

This is what I do in Math::Pari.  I think the scheme used there is
about 3 times quickier than gerepile();

> GP handles a lot of very small objects that span 3 or 4 words, so a copy
> can be less than 6 assignments.

Actually, it is 8 assignments, and two conditionals.  A copy would use
address arithmetic for all these words, so it cannot be as quick as
this.

> 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.

Thoughts are things I welcome,
Ilya