[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Proposal: block-based vector allocator

From: Dmitry Antipov
Subject: Re: Proposal: block-based vector allocator
Date: Thu, 07 Jun 2012 14:03:00 +0400
User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:12.0) Gecko/20120428 Thunderbird/12.0.1

On 06/06/2012 11:18 PM, Stefan Monnier wrote:

The cost (CPU or memory, it doesn't matter much here, and we ignore
fragmentation) of allocating a vector is something like:
and CPU costs alike, ignores fragmentation):
- outside of a vector-block: malloc + mem_node
- inside a vector-block: vector-block + frac * (malloc + mem_node + a-bit-more)
   where "frac" is a fraction that's more or less vector-size /
So for small vectors, "frac" is small and since we expect the
vector-block overhead to be significantly smaller than malloc+mem_node
we win.  But past a certain value of "frac", we're better off allocating
outside of a vector-block.  As I said, I don't know exactly where that
threshold is, but using VECTOR_BLOCK_BYTES / 2 should be good enough.

OK. This is a bit more complicated since we need some tricks to
manage free space larger than (approx.) VECTOR_BLOCK_BYTES / 2.


Attachment: vector_alloc.patch
Description: Text document

reply via email to

[Prev in Thread] Current Thread [Next in Thread]