From aa28527500210e542349cca3cd805a61a01c9dac Mon Sep 17 00:00:00 2001 From: =?utf8?q?Mattias=20Engdeg=C3=A5rd?= Date: Mon, 25 Sep 2023 16:49:29 +0200 Subject: [PATCH] Remove useless half of vector_free_lists array (bug#65491) The latter half of vector_free_lists was never used in any meaningful way but it did require traversal during allocation and GC. Reduce it to sizes we actually allocate, with a bucket for bigger ones. * src/alloc.c (VECTOR_MAX_FREE_LIST_INDEX): Rename to... (VECTOR_FREE_LIST_ARRAY_SIZE): ... this and adjust its value. (vector_free_lists): Use new, smaller size. (setup_on_free_list, allocate_vector_from_block): Adapt to new vector_free_lists size. (pseudovector_nbytes): New function extracted from... (vectorlike_nbytes): ...here. --- src/alloc.c | 42 ++++++++++++++++++++++++++++++------------ 1 file changed, 30 insertions(+), 12 deletions(-) diff --git a/src/alloc.c b/src/alloc.c index 2d5faf761c4..b2d3f734d4f 100644 --- a/src/alloc.c +++ b/src/alloc.c @@ -3080,10 +3080,10 @@ enum { VBLOCK_BYTES_MIN = vroundup_ct (header_size + sizeof (Lisp_Object)) }; enum { VBLOCK_BYTES_MAX = vroundup_ct ((VECTOR_BLOCK_BYTES / 2) - word_size) }; /* We maintain one free list for each possible block-allocated - vector size, and this is the number of free lists we have. */ - -enum { VECTOR_MAX_FREE_LIST_INDEX = - (VECTOR_BLOCK_BYTES - VBLOCK_BYTES_MIN) / roundup_size + 1 }; + vector size, one for blocks one word bigger, + and one for all free vectors larger than that. */ +enum { VECTOR_FREE_LIST_ARRAY_SIZE = + (VBLOCK_BYTES_MAX - VBLOCK_BYTES_MIN) / roundup_size + 1 + 2 }; /* Common shortcut to advance vector pointer over a block data. */ @@ -3145,9 +3145,15 @@ struct vector_block static struct vector_block *vector_blocks; /* Vector free lists, where NTH item points to a chain of free - vectors of the same NBYTES size, so NTH == VINDEX (NBYTES). */ + vectors of the same NBYTES size, so NTH == VINDEX (NBYTES), + except for the last element which may contain larger vectors. -static struct Lisp_Vector *vector_free_lists[VECTOR_MAX_FREE_LIST_INDEX]; + I.e., for each vector V in vector_free_lists[I] the following holds: + - V has type PVEC_FREE + - V's total size in bytes, BS(V) = PVSIZE(V) * word_size + header_size + - For I < VECTOR_FREE_LIST_ARRAY_SIZE-1, VINDEX(BS(V)) = I + - For I = VECTOR_FREE_LIST_ARRAY_SIZE-1, VINDEX(BS(V)) ≥ I */ +static struct Lisp_Vector *vector_free_lists[VECTOR_FREE_LIST_ARRAY_SIZE]; /* Singly-linked list of large vectors. */ @@ -3180,7 +3186,8 @@ setup_on_free_list (struct Lisp_Vector *v, ptrdiff_t nbytes) XSETPVECTYPESIZE (v, PVEC_FREE, 0, nwords); eassert (nbytes % roundup_size == 0); ptrdiff_t vindex = VINDEX (nbytes); - eassert (vindex < VECTOR_MAX_FREE_LIST_INDEX); + /* Anything too large goes into the last slot (overflow bin). */ + vindex = min(vindex, VECTOR_FREE_LIST_ARRAY_SIZE - 1); set_next_vector (v, vector_free_lists[vindex]); ASAN_POISON_VECTOR_CONTENTS (v, nbytes - header_size); vector_free_lists[vindex] = v; @@ -3212,6 +3219,17 @@ init_vectors (void) staticpro (&zero_vector); } +/* Memory footprint in bytes of a pseudovector other than a bool-vector. */ +static ptrdiff_t +pseudovector_nbytes (const union vectorlike_header *hdr) +{ + eassert (!PSEUDOVECTOR_TYPEP (hdr, PVEC_BOOL_VECTOR)); + ptrdiff_t nwords = ((hdr->size & PSEUDOVECTOR_SIZE_MASK) + + ((hdr->size & PSEUDOVECTOR_REST_MASK) + >> PSEUDOVECTOR_SIZE_BITS)); + return vroundup (header_size + word_size * nwords); +} + /* Allocate vector from a vector block. */ static struct Lisp_Vector * @@ -3239,17 +3257,19 @@ allocate_vector_from_block (ptrdiff_t nbytes) 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); - index < VECTOR_MAX_FREE_LIST_INDEX; index++) + index < VECTOR_FREE_LIST_ARRAY_SIZE; index++) if (vector_free_lists[index]) { /* This vector is larger than requested. */ vector = vector_free_lists[index]; + size_t vector_nbytes = pseudovector_nbytes (&vector->header); + eassert (vector_nbytes > nbytes); ASAN_UNPOISON_VECTOR_CONTENTS (vector, nbytes - header_size); vector_free_lists[index] = next_vector (vector); /* Excess bytes are used for the smaller vector, which should be set on an appropriate free list. */ - restbytes = index * roundup_size + VBLOCK_BYTES_MIN - nbytes; + restbytes = vector_nbytes - nbytes; eassert (restbytes % roundup_size == 0); #if GC_ASAN_POISON_OBJECTS /* Ensure that accessing excess bytes does not trigger ASan. */ @@ -3303,9 +3323,7 @@ vectorlike_nbytes (const union vectorlike_header *hdr) nwords = (boolvec_bytes - header_size + word_size - 1) / word_size; } else - nwords = ((size & PSEUDOVECTOR_SIZE_MASK) - + ((size & PSEUDOVECTOR_REST_MASK) - >> PSEUDOVECTOR_SIZE_BITS)); + return pseudovector_nbytes (hdr); } else nwords = size; -- 2.39.2