bug#65491: [PATCH] Improve performance allocating vectors

[Ihor Radchenko <yantar92@posteo.net>]

[-- Attachment #1: Type: text/plain, Size: 7044 bytes --]

Tags: patch

Hi,

Following up the bignum performance discussion in
https://yhetil.org/emacs-devel/87bkfdsmde.fsf@localhost

This patch adds a heuristic that reduces the time spent searching
`vector_free_lists' when trying to allocate a new vector.

`vector_free_lists' is a rather long array with few hundreds of
elements. And it does not make sense to check the whole array in
`allocate_vector_from_block' if we can get information about free vector
that was recently made available of if we know for sure that no free
vectors are available (after GC).

In the patch, we start searching `vector_free_lists' no earlier than the
last known index of the available free vector, or skip the search
entirely when there is known index (after sweep).

The described approach may sometimes miss free vectors in
`vector_free_lists', especially if the allocation happens from larger
vector to smaller. The cost will be slightly higher memory consumption -
no larger than VECTOR_MAX_FREE_LIST_INDEX extra free vectors.

With the patch, CPU time spent allocating new vectors in the fib.eln
test from https://yhetil.org/emacs-devel/87bkfdsmde.fsf@localhost drops 10x.

Also, the patch gives a noticeable improvement when running
elisp-benchmarks (ELPA package). The overall speedup is around 10%
(including unaffected tests).

No single test gets worse within error margins and the following tests
get a significant speedup:

- eieio        1.32±0.04 -> 1.04±0.03
- pack-unpack  0.40±0.00 -> 0.35±0.01
- pidigits     6.00±0.06 -> 4.08±0.12

pidigits is no surprise as it likely uses bignums.

* Results without the patch

  | test               | non-gc avg (s) | gc avg (s) | gcs avg | tot avg (s) | tot avg err (s) |
  |--------------------+----------------+------------+---------+-------------+-----------------|
  | bubble             |           0.68 |       0.06 |       1 |        0.73 |            0.05 |
  | bubble-no-cons     |           1.17 |       0.00 |       0 |        1.17 |            0.07 |
  | bytecomp           |           1.64 |       0.32 |      13 |        1.95 |            0.03 |
  | dhrystone          |           2.13 |       0.00 |       0 |        2.13 |            0.02 |
  | eieio              |           1.19 |       0.13 |       7 |        1.32 |            0.04 |
  | fibn               |           0.00 |       0.00 |       0 |        0.00 |            0.00 |
  | fibn-named-let     |           1.47 |       0.00 |       0 |        1.47 |            0.04 |
  | fibn-rec           |           0.00 |       0.00 |       0 |        0.00 |            0.00 |
  | fibn-tc            |           0.00 |       0.00 |       0 |        0.00 |            0.00 |
  | flet               |           1.41 |       0.00 |       0 |        1.41 |            0.03 |
  | inclist            |           0.84 |       0.00 |       0 |        0.84 |            0.03 |
  | inclist-type-hints |           0.76 |       0.00 |       0 |        0.76 |            0.00 |
  | listlen-tc         |           0.12 |       0.00 |       0 |        0.12 |            0.01 |
  | map-closure        |           5.25 |       0.00 |       0 |        5.25 |            0.02 |
  | nbody              |           1.47 |       0.15 |       1 |        1.62 |            0.07 |
  | pack-unpack        |           0.38 |       0.02 |       1 |        0.40 |            0.00 |
  | pack-unpack-old    |           1.13 |       0.05 |       3 |        1.19 |            0.03 |
  | pcase              |           1.77 |       0.00 |       0 |        1.77 |            0.01 |
  | pidigits           |           5.04 |       0.97 |      17 |        6.00 |            0.06 |
  | scroll             |           0.58 |       0.00 |       0 |        0.58 |            0.02 |
  | smie               |           1.47 |       0.05 |       2 |        1.52 |            0.02 |
  |--------------------+----------------+------------+---------+-------------+-----------------|
  | total              |          28.49 |       1.74 |      45 |       30.23 |            0.16 |

* Results with the patch

  | test               | non-gc avg (s) | gc avg (s) | gcs avg | tot avg (s) | tot avg err (s) |
  |--------------------+----------------+------------+---------+-------------+-----------------|
  | bubble             |           0.69 |       0.05 |       1 |        0.74 |            0.07 |
  | bubble-no-cons     |           1.03 |       0.00 |       0 |        1.03 |            0.02 |
  | bytecomp           |           1.45 |       0.25 |      13 |        1.70 |            0.10 |
  | dhrystone          |           1.98 |       0.00 |       0 |        1.98 |            0.05 |
  | eieio              |           0.92 |       0.12 |       7 |        1.04 |            0.03 |
  | fibn               |           0.00 |       0.00 |       0 |        0.00 |            0.00 |
  | fibn-named-let     |           1.45 |       0.00 |       0 |        1.45 |            0.12 |
  | fibn-rec           |           0.00 |       0.00 |       0 |        0.00 |            0.00 |
  | fibn-tc            |           0.00 |       0.00 |       0 |        0.00 |            0.00 |
  | flet               |           1.39 |       0.00 |       0 |        1.39 |            0.07 |
  | inclist            |           0.83 |       0.00 |       0 |        0.83 |            0.03 |
  | inclist-type-hints |           0.77 |       0.00 |       0 |        0.77 |            0.03 |
  | listlen-tc         |           0.10 |       0.00 |       0 |        0.10 |            0.00 |
  | map-closure        |           5.25 |       0.00 |       0 |        5.25 |            0.37 |
  | nbody              |           1.45 |       0.16 |       1 |        1.60 |            0.05 |
  | pack-unpack        |           0.33 |       0.02 |       1 |        0.35 |            0.01 |
  | pack-unpack-old    |           1.07 |       0.06 |       3 |        1.13 |            0.08 |
  | pcase              |           1.78 |       0.00 |       0 |        1.78 |            0.05 |
  | pidigits           |           3.15 |       0.92 |      17 |        4.08 |            0.12 |
  | scroll             |           0.55 |       0.00 |       0 |        0.55 |            0.01 |
  | smie               |           1.45 |       0.04 |       2 |        1.49 |            0.06 |
  |--------------------+----------------+------------+---------+-------------+-----------------|
  | total              |          25.63 |       1.62 |      45 |       27.25 |            0.45 |


In GNU Emacs 30.0.50 (build 54, x86_64-pc-linux-gnu, GTK+ Version
 3.24.38, cairo version 1.17.8) of 2023-08-22 built on localhost
Repository revision: c09d78f3c0818d7391760e84f94a442e8beb22dd
Repository branch: master
Windowing system distributor 'The X.Org Foundation', version 11.0.12101008
System Description: Gentoo Linux

Configured using:
 'configure --with-native-compilation
 JAVAC=/etc/java-config-2/current-system-vm/bin/javac'


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-Improve-performance-allocating-vectors.patch --]
[-- Type: text/patch, Size: 2613 bytes --]

From 476db65dc780d8c501d73dfaaf92c53eb9c73b2f Mon Sep 17 00:00:00 2001
Message-ID: <476db65dc780d8c501d73dfaaf92c53eb9c73b2f.1692869114.git.yantar92@posteo.net>
From: Ihor Radchenko <yantar92@posteo.net>
Date: Thu, 24 Aug 2023 11:05:18 +0300
Subject: [PATCH] Improve performance allocating vectors

* src/alloc.c (last_known_vector_free_idx): New global variable
holding the last known free allocated vector index in
`vector_free_lists'.
(setup_on_free_list): Record the vector index when adding a new
allocated vector to `vector_free_lists'.
(allocate_vector_from_block): Add heuristics searching for an existing
allocated vector no earlier than `last_known_vector_free_idx'.  This
heuristics may sometimes skip available allocated vectors, but reduces
the number of the `for' loop iterations significantly.
(sweep_vectors): Set `last_known_vector_free_idx' to large value - no
free allocated vectors remain available after sweep operation.

Link: https://yhetil.org/emacs-devel/87bkfdsmde.fsf@localhost
---
 src/alloc.c | 5 ++++-
 1 file changed, 4 insertions(+), 1 deletion(-)

diff --git a/src/alloc.c b/src/alloc.c
index c77bdc6372d..4293de2bdf3 100644
--- a/src/alloc.c
+++ b/src/alloc.c
@@ -3145,6 +3145,7 @@ large_vector_vec (struct large_vector *p)
 
 static struct Lisp_Vector *vector_free_lists[VECTOR_MAX_FREE_LIST_INDEX];
 
+static ptrdiff_t last_known_vector_free_idx = VECTOR_MAX_FREE_LIST_INDEX;
 /* Singly-linked list of large vectors.  */
 
 static struct large_vector *large_vectors;
@@ -3180,6 +3181,7 @@ 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;
+  last_known_vector_free_idx = vindex;
 }
 
 /* Get a new vector block.  */
@@ -3234,7 +3236,7 @@ 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);
+  for (index = max (VINDEX (nbytes + VBLOCK_BYTES_MIN), last_known_vector_free_idx);
        index < VECTOR_MAX_FREE_LIST_INDEX; index++)
     if (vector_free_lists[index])
       {
@@ -3426,6 +3428,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));
+  last_known_vector_free_idx = VECTOR_MAX_FREE_LIST_INDEX;
 
   /* Looking through vector blocks.  */
 
-- 
2.41.0


[-- Attachment #3: Type: text/plain, Size: 224 bytes --]


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