bug#65491: [PATCH] Improve performance allocating vectors

[Ihor Radchenko <yantar92@posteo.net>]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> +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.

Sure. I can add a comment. However, from previous answers, we may better
rewrite the vector allocation code more significantly.

>> -  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.

>>    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).

Interestingly, when I just tried to skip searching vector_free_lists
when there are no vectors available there, it yielded to no significant
improvement.

Only that max(VINDEX (...), last_known_vector_free_idx) yielded a good
performance improvement.

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

It could be a good exercise to look into statistics of how
vector_free_lists is filled. Is there some standard way to print debug
information from the allocation code?

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>