Re: Proposal: block-based vector allocator

[Dmitry Antipov]

On 12/06/2011 05:35 PM, Stefan Monnier wrote:

> Could you give a quick overview of what you've considered and thrown away?

The most basic idea was to maintain separate vector blocks for vectors
of each possible size (with the room enough to 0, 1, 2, etc. Lisp_Objects -
let's call it order0, order1 and so on), up to 4x1K vectors in 4K blocks,
and dedicated list for >1K vectors. This scheme is simple, but it tends to
hold too much space in free lists, and this space is of 'wrong order'. It was
typical to have 1000 free slots in order[234] blocks, but no free space in
order50 blocks. As a result, the total memory consumption was _more_ than
current.

> For large vectors we can probably just keep using what we have now.

It is so.

> I don't like much splitting&coalescing.  Is it really needed?

I believe splitting is important because the most of vectors are small,
so even a small pieces of unused memory are very likely to be utilized.

For (64-bit) example, consider 600-byte request, and there is no 600-byte free
block in corresponding free list. In this case, proposed allocator will not
consider 608 and 616-byte free lists, because splitting gives 8 and 16-bytes
tails, which can't be used to hold any vector (except 0-sized, which is very
rare). But it will consider free list with 624-bytes blocks, because 24-bytes
tail can be used for the vector holds 1 Lisp_Object. If it fails, next candidate
is 632-byte block free list, and so on. And it's very likely that 24-bytes (or
32, or 40, etc.) tail will be used soon, because most vectors are small.

Coalescing is harder, because... yes, most vectors are small :-). For example,
we can have vector block with 10 free and adjacent 40-byte vectors. While
coalescing as much as possible, an obvious result is to create 400-byte free
vector and set it on a free list. Next, it's very likely to have, for example,
8 requests for 32,40,32,40,48,32,24,48-byte vectors instead of one request for
360-byte vector. So, if corresponding small-size free lists are empty, an
allocator will split 400-byte block back into small pieces. This is an obvious
disadvantage of this allocator. But it's possible to introduce a kind of
'coalescing threshold' and stop coalescing if small-size free lists becomes
too short in favor of mid- and large-size ones.

Dmitry