apr-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Greg Stein <gst...@lyra.org>
Subject Re: freelists: a slightly different approach
Date Wed, 26 Sep 2001 08:00:26 GMT
On Wed, Sep 26, 2001 at 12:03:55AM -0700, Justin Erenkrantz wrote:
> Something strikes me as incorrect with this.  First, it'd require
> initialization of this code per thread and then they'd have to store
> it globally so that all of the code that calls _bucket_foo_create()
> can pass it - but since threads typically share memory space with
> their sibling threads, they'll need to create the data structure
> themselves.  And, this code will have to be duplicated by any 
> user of buckets.

Yah :-(

> What's wrong with an internal hashtable here keyed off of the 
> thread id (or whatever is returned by apr_os_thread_current)?
> Internally, you can represent the apr_bucket_freelist* as you 
> describe (that sounds good) - so we can abstract all of that 
> away, but forcing this out to the caller seems like the wrong 
> direction to go.  The hashtable makes it so that it is of 
> indeterminate size and the retrieval speed should be fast 
> enough for our purposes.
> Or, what am I missing?  -- justin

An internal thread id seems more than fine. We can always expose more
details later on, as we find we need to fine tune things.

That thread id would then give you an array of chains of free buckets. That
array can be indexed by the bucket size, say rounded up to the nearest 8 or
16 bytes. Buckets over size N fall off to a separate structure to associate
sizes with the chains. That gives us speed for "normal" buckets, yet allows
us to handle arbitrary size buckets.

I believe the optimal structure for the chain is a pair of items:

* a free list of buckets, in a simple linked list
* a block of free buckets, specified as ptr to current and N left

The free list optimizes the "free bucket" operation to be a simple linking

Allocating a bucket goes to the free list first, then to the block. Both are
very fast operations. If none are available, then a new block is allocated
and the ptr/N pair are initialized.

By using the pair, we optimize the alloc-new-block operation: linking N
buckets into the free list is expensive. Dropping the new allocation into a
block is the fastest operation. But putting free buckets back into that
block is expensive, so we add in the free list.

A bucket can simply record a ptr to its chain.

So... the hard part is figuring out which chain to use when allocating a
bucket. Like I said above, I would suggest a simple mechanism (for starters)
which maps the thread id to an array of chains. Note that this does not
require any API changes. Heck, it doesn't even need an API change for
setting up the structures -- not to the bucket allocs and not even the
apr_bucket_alloc stuff.


Greg Stein, http://www.lyra.org/

View raw message