Re: chunked MemPool

On 18 Apr 2001, at 0:25, Henrik Nordstrom <hno@hem.passagen.se> wrote:

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

 will try that.

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

 After some searching and reading I think that splay could actually be
 good here, as it kinda sorts most frequently used stuff to the top.
 I implemented splay for a try, but it wasn't any tremendous win.
 splay search takes about 200 cpu ticks average, but memPoolFree times
 didn't drop noticably, perhaps some 20-30%. Most cpu goes elsewhere.
 Will look into it also.

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

 I'm afraid this is the most crucial part of it. but I dunno.

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

 lets see. maybe we can get away with all the stats we want.

------------------------------------
 Andres Kroonmaa <andre@online.ee>
 CTO, Delfi Online
 Tel: 6501 731, Fax: 6501 708
 Pärnu mnt. 158, Tallinn,
 11317 Estonia
Received on Tue Apr 17 2001 - 17:10:05 MDT