[PATCH] Re: Bignum performance (was: Shrinking the C core)

[Ihor Radchenko]

Emanuel Berg <incal@dataswamp.org> writes:

>> Maybe we could somehow re-use the already allocated bignum
>> objects, similar to what is done for cons cells (see
>> src/alloc.c:Fcons).
>
> Sounds reasonable :)

And... is has been already done, actually.
allocate_vectorlike calls allocate_vector_from_block, which re-uses
pre-allocated objects.

And looking into the call graph, this exact branch calling
allocate_vector_from_block is indeed called for the bignums:

   33.05%     0.00%  emacs    [unknown]                       [.] 
0000000000000000
            |
            ---0
               |          
               |--28.04%--allocate_vectorlike
               |          |          
               |           --27.78%--allocate_vector_from_block (inlined)
               |                     |          
               |                     |--2.13%--next_vector (inlined)
               |                     |          
               |                      --0.74%--setup_on_free_list (inlined)

If it manually cut off `allocate_vector_from_block', the benchmark time
increases twice. So, there is already some improvement coming from
re-using allocated memory.

I looked deeper into the code tried to cut down on unnecessary looping
over the pre-allocated `vector_free_lists'. See the attached patch.

Without the patch:

 perf record ~/Git/emacs/src/emacs -Q -batch -l /tmp/fib.eln
 2.321 s
 
     28.60%  emacs    emacs                        [.] allocate_vectorlike
    24.36%  emacs    emacs                        [.] process_mark_stack
     3.76%  emacs    libgmp.so.10.5.0             [.] __gmpz_sizeinbase
     3.59%  emacs    emacs                        [.] pdumper_marked_p_impl
     3.53%  emacs    emacs                        [.] mark_char_table

With the patch:

perf record ~/Git/emacs/src/emacs -Q -batch -l /tmp/fib.eln
1.968 s

    33.17%  emacs    emacs                          [.] process_mark_stack
     5.51%  emacs    libgmp.so.10.5.0               [.] __gmpz_sizeinbase
     5.05%  emacs    emacs                          [.] mark_char_table
     4.88%  emacs    emacs                          [.] pdumper_marked_p_impl
     3.30%  emacs    emacs                          [.] pdumper_set_marked_impl
...
     2.52%  emacs    emacs                          [.] allocate_vectorlike

allocate_vectorlike clearly takes a lot less time by not trying to loop
over all the ~500 empty elements of vector_free_lists.

We can further get rid of the GC by temporarily disabling it (just for
demonstration):

(let ((beg (float-time)))
  (setq gc-cons-threshold most-positive-fixnum)
  (fib 10000 1000)
  (message "%.3f s" (- (float-time) beg)) )

perf record  ~/Git/emacs/src/emacs -Q -batch -l /tmp/fib.eln
0.739 s

    17.11%  emacs    libgmp.so.10.5.0      [.] __gmpz_sizeinbase
     7.35%  emacs    libgmp.so.10.5.0      [.] __gmpz_add
     6.51%  emacs    emacs                 [.] arith_driver
     6.03%  emacs    libc.so.6             [.] malloc
     5.57%  emacs    emacs                 [.] allocate_vectorlike
     5.20%  emacs    [unknown]             [k] 0xffffffffaae01857
     4.16%  emacs    libgmp.so.10.5.0      [.] __gmpn_add_n_coreisbr
     3.72%  emacs    emacs                 [.] check_number_coerce_marker
     3.35%  emacs    fib.eln               [.] F666962_fib_0
     3.29%  emacs    emacs                 [.] allocate_pseudovector
     2.30%  emacs    emacs                 [.] Flss

Now, the actual bignum arithmetics (lisp/gmp.c) takes most of the CPU time.

I am not sure what differs between Elisp gmp bindings and analogous SBCL
binding so that SBCL is so much faster.

diff --git a/src/alloc.c b/src/alloc.c
index 17ca5c725d0..62e96b4c9de 100644
--- a/src/alloc.c
+++ b/src/alloc.c
@@ -3140,6 +3140,7 @@ large_vector_vec (struct large_vector *p)
    vectors of the same NBYTES size, so NTH == VINDEX (NBYTES).  */
 
 static struct Lisp_Vector *vector_free_lists[VECTOR_MAX_FREE_LIST_INDEX];
+static int vector_free_lists_min_idx = VECTOR_MAX_FREE_LIST_INDEX;
 
 /* Singly-linked list of large vectors.  */
 
@@ -3176,6 +3177,8 @@ setup_on_free_list (struct Lisp_Vector *v, ptrdiff_t 
nbytes)
   set_next_vector (v, vector_free_lists[vindex]);
   ASAN_POISON_VECTOR_CONTENTS (v, nbytes - header_size);
   vector_free_lists[vindex] = v;
+  if ( vindex < vector_free_lists_min_idx )
+    vector_free_lists_min_idx = vindex;
 }
 
 /* Get a new vector block.  */
@@ -3230,8 +3233,8 @@ allocate_vector_from_block (ptrdiff_t nbytes)
   /* Next, check free lists containing larger vectors.  Since
      we will split the result, we should have remaining space
      large enough to use for one-slot vector at least.  */
-  for (index = VINDEX (nbytes + VBLOCK_BYTES_MIN);
-       index < VECTOR_MAX_FREE_LIST_INDEX; index++)
+  for (index = max ( VINDEX (nbytes + VBLOCK_BYTES_MIN), 
vector_free_lists_min_idx );
+       index < VECTOR_MAX_FREE_LIST_INDEX; index++, 
vector_free_lists_min_idx++)
     if (vector_free_lists[index])
       {
        /* This vector is larger than requested.  */
@@ -3413,6 +3416,7 @@ sweep_vectors (void)
   gcstat.total_vectors = 0;
   gcstat.total_vector_slots = gcstat.total_free_vector_slots = 0;
   memset (vector_free_lists, 0, sizeof (vector_free_lists));
+  vector_free_lists_min_idx = VECTOR_MAX_FREE_LIST_INDEX;
 
   /* Looking through vector blocks.  */
 

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