[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
bug#65491: [PATCH] Improve performance allocating vectors
From: |
Eli Zaretskii |
Subject: |
bug#65491: [PATCH] Improve performance allocating vectors |
Date: |
Sat, 26 Aug 2023 10:14:28 +0300 |
> 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.
bug#65491: [PATCH] Improve performance allocating vectors, Mattias Engdegård, 2023/08/26