[Ecls-list] computing results into preallocated bignums

[Juan Jose Garcia-Ripoll]

On Wed, Sep 9, 2009 at 5:57 PM, Nils Bruin <nbruin at cecm.sfu.ca> wrote:
> OK, I redid the timings for the fibo example, without the time related
> commands in "test" and using the time macro and results are much more
> consistent.
>
> Register code, uncompiled: 15.9 sec
> Register code, compiled: 9.1 sec
>
> Prealloc code, uncompiled: 14.8 sec
> Prealloc code, compiled: 8.8 sec

That is definitely not much. I wonder whether your code does the
equivalent of big_register_normalize(), that is detecting whether a
bignum fits into a computer word or not and then output the value. I
am also wondering whether instead of actual bignum optimization we are
just seeing the effect of inlining code that before resided elsewhere.
If this is the case then I would take it with a grain of salt and
balance the benefits of code maintainability versus open-coding all
bignum operations.

> Some remarks:
>  - this example computed the 4000(+-1)th fibonacci number, which has about
> 836 digits, or about 2777 bits. On 64 bit machine, I think this does not
> quite trigger register reallocation upon freeing yet (that would happen
> when the register hits 32*3*64=6144 bits). Indeed "cons"-ing seems to be
> on par. Is that what's measured by "cons"ed?

Yes, "consing" is a lispy word for memory allocation. The numbers you
see is how much has been allocated during the execution of the timed
form.

>  - Juanjo made a good point: You don't want to do this if the result is
> likely to fit in a fixnum. Hence, the right thing to do is probably to
> keep the register code in (fixnum,fixnum) operations (although the spare
> bits mean that for addition, that one can be done in a long anyway!). I'd
> think that "cancellation" is relatively rare, so when a bignum comes into
> play, I'd think you're making a good guess by assuming that the answer
> will be a bignum again. Any heuristics on the percentage of multiprecision
> operations that end up producing a small integer in "real life"?

Cancellations are more likely than you would expect in the sense that
it will be quite frequent that we operate on bignums just because they
have 1 or 2 more bits than fit in a lisp word. These numbers, or
"fixnums" have 32-3=29 or 64-3=61 bits because they have to be
distinguished from pointers, and thus most of the bignum operations
that you see are due to those extra bits.

This connects with the other remark you made: for most calculations
1024 bits is really enough and the bignum register is not being
reallocated. If only extremely big computations are going to profit
and small number computations might suffer from whatever optimization
we make, then I would think it twice before changing the current
code...

Juanjo

-- 
Instituto de Física Fundamental, CSIC
c/ Serrano, 113b, Madrid 28006 (Spain)
http://juanjose.garciaripoll.googlepages.com