[Ecls-list] Slow bignums

[Waldek Hebisch]

Nils Bruin wrote:
> On Fri, 29 Jan 2010, Waldek Hebisch wrote:
> 
> > GENERIC-* and GENERIC-+ dispatch to specialized bignum routines
> > and bignum routines use stack alocation for temporaries.  ECL
> > reports almost 4000 times larger allocation than sbcl.  A simple
> > estimate suggests that when all results are stack allocated
> > consing should be similar to what sbcl reported.  Given that
> > other implementation give similar amounts I thend to believe
> > that sbcl consing number is correct.  So the question is if
> > ECL reports _way_ to large consing number, or maybe ECL
> > is doing something stupid and allocates too much.
> 
> I have some experience with ECL's bignums from setting up embedded use of 
> ECL in Sage (which is working great, by the way). ECL calls GMP routines 
> *always* with a "register" as target -- a preallocated GMP integer. Once 
> the bignum computation is done, ECL can read off exactly how big the 
> result is, allocate an appropriate block and copy the integer into it. In 
> practice, this copy is so cheap that it isn't really worth avoiding (we 
> did some tests).

Yes, typically copy is cheap enough.  But in this case main operations
are adding 1 and multiplication by fixnum.  Adding 1 costs basically
the same as copy.  Multiplication by fixnum is slightly more expensive,
but should be no more expensive than two copies.

Also, copies may increase working set and push you outside cache, in
such case effect may be more significant.  OTOH I am not sure how
much is saved by resizing: in case of multiplication and addition
there is possibility to save one word, which is not much.  Only
in case of subtraction (and remainder) there is possibility for big
saving.

> Of course, if you are going to optimize evaluation of bignum expressions 
> by keeping track of which results are only intermediate and hence can be 
> overwritten, the balance for this may shift.
> 
> Normally, there is no consing outside the one for the result in every 
> bignum operation. However, if the preallocated register (which has a 
> comfortable default size) needs extending, then that is an extra 
> allocation. Furthermore, if the register has grown to more than 3 times 
> its default size, then ECL shrinks it again, which could cause extra 
> memory management overhead as well.

You mean that ECL _always_ shrinks register if it gets large?  That
looks like huge waste.  It looks like nice opportunity to use
weak references: keep weak reference to register and let garbage
collector to recycle it.  But before garbage collection register
would still be available for reuse.

-- 
                              Waldek Hebisch
hebisch at math.uni.wroc.pl