Re: chunked MemPool

Andres Kroonmaa wrote:

> I'm still not sure if it is worth it. It could be worth only for pools
> that have very many chunks to search. I have no idea where could the
> threshold be between adding overhead and becoming more efficient.
> But for sure with a pool with less than some 4-8 chunks searching via
> trees or hashes would only add overhead. And that is most of the time.

Sure. If a tree is used then it should have a branch factor of about 5 I
think, to start out as a linear search until more than 5 nodes are
needed. For 6 to 25 nodes it will be two linear searches of up to 5
iterations each.

But I think using a free list is the correct thing, and almost nullifies
the impact of chunk searches. And some low cost magics can be played to
keep the freelist somewhat sorted..

> So, to be most efficient, we'd need to decide based on number of
> chunks whether to use trees or plain linklist search.

Done automatically in a good tree design.

> > I would suggest using a tree with about 5 branches per internal node.
>
> In squid we have only splay? Did you mean that? I'm not like writing
> any tree code myself.

splay uses a binary tree with 2 branches (i.e. binary), and automatic
reordering to speed up common searches.

for chunked mempools I would use a much simpler tree code than splay,
and specifically written for the mempools to avoid having to call
compare function pointers..

writing a basic tree implementation is not much harder than a doubly
linked list. What is tricky is to write a rebalance function if needed
(which shouldn't really be needed for chunked mempools).

> basically cache of frees. I was thinking on that path. Only we'll
> loose stats per chunk.

Do we need full per chunk stats in production? Don't think so.

We can still provide detailed allocated/free stats, just need to iterate
thru the free list to refresh the per chunk free counts. Perhaps the
only thing we cannot provide is counters or timestamps showing how many
times a chunk has been used/reused.

--
Henrik