master 091b8de586e 2/2: Use heuristic to speed up allocation of small vectors (bug#65491)

[Mattias Engdegård]

branch: master
commit 091b8de586efc41c3dbd8606445c99c541e90076
Author: Mattias Engdegård <mattiase@acm.org>
Commit: Mattias Engdegård <mattiase@acm.org>

    Use heuristic to speed up allocation of small vectors (bug#65491)
    
    Instead of scanning vector_free_lists from the appropriate size until
    we find a nonempty bucket, start at the last bucket where we last put
    something in.  This may favour splitting larger vectors than necessary
    but in general saves a lot of time in the allocation of small vectors.
    
    Original patch by Ihor Radchenko.
    
    * src/alloc.c (last_inserted_vector_free_idx): New variable.
    (setup_on_free_list): Set it.
    (allocate_vector_from_block): Use it.
    (sweep_vectors): Reset it.
---
 src/alloc.c | 10 +++++++++-
 1 file changed, 9 insertions(+), 1 deletion(-)

diff --git a/src/alloc.c b/src/alloc.c
index b2d3f734d4f..45a950c4f81 100644
--- a/src/alloc.c
+++ b/src/alloc.c
@@ -3155,6 +3155,11 @@ static struct vector_block *vector_blocks;
    - For I = VECTOR_FREE_LIST_ARRAY_SIZE-1, VINDEX(BS(V)) ≥ I */
 static struct Lisp_Vector *vector_free_lists[VECTOR_FREE_LIST_ARRAY_SIZE];
 
+/* Index to the bucket in vector_free_lists into which we last inserted
+   or split a free vector.  We use this as a heuristic telling us where
+   to start looking for free vectors when the exact-size bucket is empty.  */
+static ptrdiff_t last_inserted_vector_free_idx = VECTOR_FREE_LIST_ARRAY_SIZE;
+
 /* Singly-linked list of large vectors.  */
 
 static struct large_vector *large_vectors;
@@ -3191,6 +3196,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_inserted_vector_free_idx = vindex;
 }
 
 /* Get a new vector block.  */
@@ -3256,7 +3262,8 @@ 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_inserted_vector_free_idx);
        index < VECTOR_FREE_LIST_ARRAY_SIZE; index++)
     if (vector_free_lists[index])
       {
@@ -3489,6 +3496,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_inserted_vector_free_idx = VECTOR_FREE_LIST_ARRAY_SIZE;
 
   /* Looking through vector blocks.  */