bug#65491: [PATCH] Improve performance allocating vectors

[Eli Zaretskii <eliz@gnu.org>]

> From: Ihor Radchenko <yantar92@posteo.net>
> Date: Thu, 24 Aug 2023 09:59:33 +0000
> 
> 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 |
> 

Stefan, any comments?

my comment is that the savings are quite small, so it seems, so I'm
not sure we should install this.