[Ecls-list] Slow bignums
nbruin at cecm.sfu.ca
Fri Jan 29 04:57:42 UTC 2010
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.
More information about the ecl-devel