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'