bug#65491: [PATCH] Improve performance allocating vectors

[Stefan Monnier via "Bug reports for GNU Emacs, the Swiss army knife of text editors" <bug-gnu-emacs@gnu.org>]

> 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