apr-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Justin Erenkrantz <jerenkra...@ebuilt.com>
Subject Re: Observations on fragmentation in SMS pools
Date Sun, 08 Jul 2001 08:13:12 GMT
On Sun, Jul 08, 2001 at 12:47:32AM -0700, Brian Pane wrote:
> I added some instrumentation to apr_sms_trivial_malloc
> to study in more detail where its bottlenecks were.
> 
> As a result, I found a few interesting phenomena:
> 
> 1. The good news is that allocations of small amounts
>    of memory are very efficient.  They almost always
>    take the fastest path through the code, in which
>    some available space is reserved from the
>    "sms->used_sentinel.prev" block with a handful of
>    pointer arithmetic operations.
> 
> 2. The bad news is that allocations for larger blocks
>    (in the >=8KB range) typically require a call to the
>    parent SMS to get data.  On my test machine, I'm seeing
>    elapsed times in the 30 microsecond range when this
>    happens, compared to less than 1 microsecond for small
>    allocations that don't require more memory from the
>    parent SMS.  And when an allocation falls through to
>    the parent, it often seems to fall all the way through
>    to the root SMS (I suspect that 30us includes a malloc).
>    The problem seems to be particularly bad for things that
>    create subrequests, like mod_include.
> 
> 3. The worse news is that there seems to be lot of
>    fragmentation.  For example, I saw this pattern
>    during a server-parsed request:
>      - the application code requests 12296 bytes
>        from a pool
>      - not enough memory is available in the SMS, so it
>        requests 16400 bytes from its parent SMS.
>      - the parent SMS doesn't have enough free space
>        either, so it requests 20504 bytes from the
>        grandparent SMS.
>      - the grandparent SMS doesn't have enough space
>        either, but it has to iterate through 15 blocks
>        its free list to figure that out.  Each of these
>        blocks has between 8176 and 12272 bytes available.
>      - the grandparent calls through to the great-grandparent
>        to get 24608 bytes.  The great-grandparent doesn't
>        have a block with that much free space, but it
>        iterates through 9 blocks in its free list in
>        search of one; all of these blocks had 16376 bytes
>        free.
>      - the great-grandparent thus requests 28712 bytes from
>        the great-great grandparent.  The great-great-grandparent
>        doesn't have any blocks in its free list, so it calls
>        through to its parent, which at last is an SMS that
>        does a real malloc.
>    This type of pattern may explain the reported higher memory
>    use of the SMS-based httpd compared with the original pools;
>    there's a lot of memory in those free lists that can't be
>    used in this example.
> 
> For an SMS that's going to be a parent of other SMSs, we'll
> need something with more sophisticated policies for reassigning
> freed space than the current trivial-SMS.

Yup.  I've brought this up to Sander and David before, but this is how 
pools work EXCEPT for the fact that we get a little more pathological in 
SMS's addition of memory because each parent tacks on memory (as you
described).  The optimization here is for the <4KB allocation.  I'm not
sure that is what we need to be optimizing for.  More analysis is
probably needed to see what our typical usage pattern is.  This is where
Ian's pool replay code is *very* helpful (although I don't like adding
more #ifdef to the pool code - yuck - I'd like to see a SMS that just
prints that info and passes it up to the parent to do what it needs 
to).

Before turning SMS on in the mainline code by default, I think we need 
to come up with a more robust allocation algorithm.  And, the whole 
point of SMS is that we can play with memory allocation algorithms 
until we are blue in the face and nothing else changes.  You can't do 
that with the current pools code.  We need more people playing with it
and suggesting new allocation algorithms.  =)  The trivial SMS tries to
keep the memory allocation strategy as close as possible to what we 
currently have.

Personally, I'd set MIN_FREE to 0 and bite the small allocations (now 
they'd be slow, but really, how many allocations are under 4KB - data 
structures, perhaps?).  I'd also like to see it smarter about reclaiming
free space, but that gets really tricky.

It's a tradeoff (and is purposeful for lots of small allocations), but 
until someone can write a better memory allocation algorithm, this is 
what we got.  Trivial SMS has its Achilles heel here - this is just an
aggrevation of how the original pool code works (the pool code would add 
4KB, while each level of the SMS adds 4KB).

Aaron pointed out that CLR (Cormen/Leiserson/Rivest for those that never 
took algorithms classes) has many memory allocation algorithms.  I'd 
bet we could find one that would work better.  -- justin


Mime
View raw message