[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
bug#65491: [PATCH] Improve performance allocating vectors
From: |
Stefan Monnier |
Subject: |
bug#65491: [PATCH] Improve performance allocating vectors |
Date: |
Sun, 27 Aug 2023 12:21:30 -0400 |
User-agent: |
Gnus/5.13 (Gnus v5.13) |
> This patch adds a heuristic that reduces the time spent searching
> `vector_free_lists' when trying to allocate a new vector.
The microbenchmarks give surprisingly good performance improvements.
> `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).
Hmm... after GC we should usually have a non-zero number of free vectors
available (the unused parts of vector blocks which could not be `free`d
because they still contain a live vector), no?
[ See comment below. ]
> The described approach may sometimes miss free vectors in
> `vector_free_lists', especially if the allocation happens from larger
> vector to smaller.
Right, it could lead to an increase in fragmentation, tho it might tend
to allocate temporally related objects together, which might be beneficial.
> - pack-unpack 0.40±0.00 -> 0.35±0.01
Interesting. I didn't expect such a large effect there.
> @@ -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;
There's clearly some spacing issue with the following comment but more
importantly the new var would need a good comment explaining what the
variable should hold and why it's useful, so we know when it's safe and
desirable to set or use the var.
> @@ -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])
> {
IIUC that's the core of your patch. Nice.
> @@ -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. */
Hmm... so I was wrong and after GC there are aren't any free vectors?
I need to go re-read that code, then, because it doesn't match my mental
model of how it work(s|ed).
Stefan
bug#65491: [PATCH] Improve performance allocating vectors, Mattias Engdegård, 2023/08/26
bug#65491: [PATCH] Improve performance allocating vectors,
Stefan Monnier <=