Re: [PATCH] Re: Bignum performance

[Po Lu]

Ihor Radchenko <yantar92@posteo.net> writes:

> Po Lu <luangruo@yahoo.com> writes:
>
>>>> And we have huge overheads converting things back-and-forth
>>>> between GMP and Elisp formats. It is by choice. And my patch
>>>> did not do anything about this difference.
>>
>> AFAIU, no conversion takes place between ``Elisp formats'' and GMP
>> formats.  Our bignums rely on GMP for all data storage and memory
>> allocation.
>
> Thanks for the clarification!
> So, GMP is not as fast as SBCL's implementation after all.
> SBCL uses https://github.com/sbcl/sbcl/blob/master/src/code/bignum.lisp
> - a custom bignum implementation, which is clearly faster compared to
> GMP (in the provided benchmark):

GMP is significantly faster than all other known bignum libraries.
Bignums are not considered essential for Emacs's performance, so the GMP
library is utilized in an inefficient fashion.

> perf record  ~/Git/emacs/src/emacs -Q -batch -l /tmp/fib.eln
> 0.739 s
> (0.007 s for SBCL)
>
>     17.11%  emacs    libgmp.so.10.5.0      [.] __gmpz_sizeinbase
>
>      7.35%  emacs    libgmp.so.10.5.0      [.] __gmpz_add
>
> ^^ already >0.1 sec.

The subroutine actually performing arithmetic is in fact
mpn_add_n_coreisbr.

mpz_add and mpz_sizeinbase are ``mpz'' functions that perform memory
allocation, and our bignum functions frequently utilize mpz_sizeinbase
to ascertain whether a result can be represented as a fixnum.  As such,
they don't constitute a fair comparison between the speed of the GMP
library itself and SBCL.

GMP provides low-level functions that place responsibility for memory
management and input verification in the hands of the programmer.  These
are usually implemented in CPU-specific assembler, and are very fast.
That being said, they're not available within mini-gmp, and the primary
bottleneck is in fact mpz_sizeinbase.