Bignum performance (was: Shrinking the C core)

[Ihor Radchenko <yantar92@posteo.net>]

Emanuel Berg <incal@dataswamp.org> writes:

> In theory Lisp can be as fast as any other language but in
> practice it is not the case with Elisp and Emacs at least.
>
> Here is a n experiment with stats how Emacs/Elisp compares
> to SBCL/CL, for this particular one it shows that Elisp, even
> natively compiled, is still +78875% slower than Common Lisp.
>
> ...
> (defun fib (reps num)
>   (let ((z 0))
>     (dotimes (_ reps)
>       (let ((p1 1)
>             (p2 1))
>         (dotimes (_ (- num 2))
>           (setf z (+ p1 p2)
>                 p2 p1
>                 p1 z))))
>     z))
>
> (let ((beg (float-time)))
>   (fib 10000 1000)
>   (message "%.3f s" (- (float-time) beg)) )

Most of the time is spent in (1) GC; (2) Creating bigint:

perf record emacs -Q -batch -l /tmp/fib.eln

perf report:

Creating bignums:
    40.95%  emacs    emacs                    [.] allocate_vectorlike
GC:
    20.21%  emacs    emacs                    [.] process_mark_stack
     3.41%  emacs    libgmp.so.10.5.0         [.] __gmpz_sizeinbase
GC:
     3.21%  emacs    emacs                    [.] mark_char_table
     2.82%  emacs    emacs                    [.] pdumper_marked_p_impl
     2.23%  emacs    libc.so.6                [.] 0x0000000000090076
     1.78%  emacs    libgmp.so.10.5.0         [.] __gmpz_add
     1.71%  emacs    emacs                    [.] pdumper_set_marked_impl
     1.59%  emacs    emacs                    [.] arith_driver
     1.31%  emacs    libc.so.6                [.] malloc
GC:
     1.15%  emacs    emacs                    [.] sweep_vectors
     1.03%  emacs    libgmp.so.10.5.0         [.] __gmpn_add_n_coreisbr
     0.88%  emacs    libc.so.6                [.] cfree
     0.87%  emacs    fib.eln                  [.] F666962_fib_0
     0.85%  emacs    emacs                    [.] check_number_coerce_marker
     0.80%  emacs    libc.so.6                [.] 0x0000000000091043
     0.74%  emacs    emacs                    [.] allocate_pseudovector
     0.65%  emacs    emacs                    [.] Flss
     0.57%  emacs    libgmp.so.10.5.0         [.] __gmpz_realloc
     0.56%  emacs    emacs                    [.] make_bignum_bits

My conclusion from this is that big number implementation is not
optimal. Mostly because it does not reuse the existing bignum objects
and always create new ones - every single time we perform an arithmetic
operation.

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>