Re: [RFC/PATCH 2/3] small-alloc: add allocator for small objects

[David Barr <davidbarr@google.com>]

Junio wrote:
> Instead of having two independently depleted byte-buffer (space[] and
> len[]), I wonder if it would be more space efficient (without being less
> processing efficient) to use a single buffer space.  Your pool_ptr() would
> start at the beginning of pool->space[n], decode a varint and take it as a
> length, if that is not the object you are looking for, skip that many
> bytes (i.e. payload immediately follows the length) to the next object,
> and so on.

David Barr wrote:
> I have already investigated this arrangement, it has very poor
> locality of access.
> For objects <32 bytes long, its not too bad since typically 2 bytes of a 64 byte
> cache line would be read consecutively. For larger objects this is pathological
> cache behavior. On the other hand, the current design means that the entire
> sequence of lengths will fit on a single >=16 byte cache line.

Another approach is to keep the buffers separate but interleave
pointers and lengths.
I'll give this a go and see if it's an overall improvement.

--
David Barr