Re: [Chicken-hackers] [PATCH] More efficient numbers integration through "scratchspace"

[Peter Bex]

On Sun, Apr 19, 2015 at 10:28:53PM -0400, John Cowan wrote:
> Peter Bex scripsit:
> > The scratch area is seen as an extension of the nursery: the
> > C_demand() and C_stack_probe() checks will add the size of the scratch
> > space to the stack's size, and trigger a minor GC when the sum of the
> > two exceeds the maximum nursery size.
> 
> So when a bignum needs to be allocated for the first teim, a scratch
> space is alloca()ed?  How big is it?  It sounds like it needs to be
> big enough to hold a sufficient number of biggest-bignums to perform a
> single operation.

As usual, "it depends".  If you perform an operation on two fixnums which
results in a bignum, the result will be allocated completely on the stack.
That's because the size needed for (most of) those operations is exactly
as big as the size needed to store a fixnum in a bignum.  This will take
up a bignum of one bigit (bignum digit).  This fits even when the addition
overflows because the fixnum uses up two bits which are free in the bigit
when it's promoted to a bignum, so it can overflow within that bigit.
This is what's called a "fix bignum" (yeah, I know..), and
C_SIZEOF_FIX_BIGNUM is the size of a bignum of one bignum digit, which
is identical to C_SIZEOF_BIGNUM(1).  Multiplication is a bit of a special
case here, as it will need C_SIZEOF_BIGNUM(2), ie it needs two bignum
digits to contain the result of a fixnum*fixnum operation.  This is still
allocated on the stack (and the reason the types.db specialization needs
a bit more memory).

Then, when you perform an operation on two actual bignums, or a fixnum is
shifted by enough to need a bignum, it will *really* need a scratch space.
The size that's allocated is DEFAULT_SCRATCH_SPACE_SIZE, which is defined
to be 256 words somewhere at the start of runtime.c.  This will generally
hold plenty of bignums to be usable for a while without needing
reallocation.  When we reallocate, we calculate the needed space (which
is the current *used* space plus the requested size) and take the adjoining
higher power of two, or the current size of the scratch space times two,
whichever is bigger.  In order to avoid unbounded growth, a check is
inserted that allows the new size to be halved if the calculated new size
is more than eight times as big as the amount that's strictly needed to
hold the new bignum plus every "live" scratch object.

I've experimented with various growth factors and default sizes, and this
has turned out to be the best algorithm so far to avoid excessive
reallocations ("GCs") of the scratch space and resulting copying.  It's
still not as efficient as the original numbers implementation that
allocated straight in the nursery or heap, though!  But it's an acceptable
tradeoff, I think.  At least the performance of non-bignum code doesn't
suffer as much in this system.

> > a cplxnums containing two ratnums, which both contain two bignums will
> > be correctly updated, regardless of where any of the 7 objects lives.
> 
> Compnums, rectnums, and ratnums are already fixed-size, so there is
> no obvious reason to allocate them in the scratch space rather than
> on the regular C stack.

Except for the fact that this causes the needed stack space is bigger,
resulting in more minor GCs even for code that doesn't need these numeric
types.

> It seems to me that there needs to be some way in the new design to force
> part of the old behavior: for overflow and for / of integers to return
> a flonum.  Notoriously, Scheme programs on full towers can get horribly
> slow because they generate bigger and bigger ratnums, and any time where
> efficiency beats accuracy, you want to switch to flonums.  This is often
> done by inserting judicious decimal points into the constants in the
> program, but it would be better to make it a switch of some sort.

I don't understand how this would work and why it will be needed.  If you
need flonum behaviour, you can simply convert to inexact before making
your calculations.  The compiler cannot make the decision to use inexact
numbers for you: that depends on the application and the domain-specific
nature of the calculations you're performing, I would say.

Cheers,
Peter

signature.asc
Description: Digital signature