[Ecls-list] Slow bignums

[Nils Bruin]

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

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. I did not check your code example in 
detail, but if it works with particularly large bignums, it could get in 
the range where ECL has to reallocate and shrink the register for every 
operation, essentially tripling the numer of memory management calls. You 
could retry your example with a default register size that is definitely 
sufficient for your example and see if consing is drastically reduced.

ECL has an option to let GMP use a different memory manager (this was 
necessary because in Sage, GMP is already initialized with a memory 
manager, so ECL couldn't overwrite that). Given that the memory manager 
that GMP within ECL uses will only be used to resize registers, it is 
conceivable that a special purpose memory manager would do a better job.

When I tested bignum performance, I found that Sage's GMP-based integers 
were particularly good. I think the main thing was that Sage keeps a pool 
of preallocated bignums that get reused. This leads to particularly 
cache-friendly performance without having to do any extra programming. I 
don't know if Boehm would reclaim unused integers quickly enough to get 
the same cache-friendly behaviour.

Nils