bug#65491: [PATCH] Improve performance allocating vectors

[Stefan Monnier]

> The reason might be that vector sizes are distributed non-uniformly and
> some segments of vector_free_lists are filled more than others.

Indeed, I'd expect that at any given time, many buckets of
`vector_free_lists` are empty.

Also, when ELisp code allocates many structs of the same size, the first
few allocations may be satisfied by free elements in the appropriate
bucket, but very quickly that bucket will become empty, so we'll look
for the next non-empty bucket, and the remaining slightly-smaller free
vector will then be put back into a lower bucket but the next allocation
will go through the same loop to find that same "slightly-smaller free
vector", to make it yet a bit smaller, ... until it's all consumed after
which we'll look for the next bigger free vector etc...

So your code makes a lot of sense from that point of view.

Many mallocs approach the problem by creating whole pages dedicated to
a given object size, so when the bucket is empty, N new free vectors of
that exact size are created (in a new vector-block) and put into the
appropriate bucket so the next N allocations of that same size will
quickly find a free vector.  Since all those vector-blocks are made of
vectors of the same size, the size info can be shared between them
instead of each one of them carrying its own size.
[ In our case, vectors need to carry their size for other purposes than
  memory management, so it's not clear we'd gain much there.
  But it could help make `live_small_vector_holding` faster.  ]


        Stefan