What's the boost pool allocator good for?

Discussion in 'C++' started by Juha Nieminen, Jul 9, 2008.

  1. I tested the speed of a simple program like this:

    //------------------------------------------------------------
    #include <list>
    #include <boost/pool/pool_alloc.hpp>

    int main()
    {
    typedef std::list<int> List_t; // default allocator
    //typedef std::list<int, boost::pool_allocator<int> > List_t;

    List_t l;

    for(int i = 0; i < 100000; ++i)
    l.push_back(i);

    int counter = 0;
    for(List_t::iterator iter = l.begin(); iter != l.end();)
    if(++counter % 3 == 0)
    iter = l.erase(iter);
    else
    ++iter;

    for(int i = 0; i < 100000; ++i)
    l.push_back(i);
    }
    //------------------------------------------------------------

    Compiling this with "-O3 -march=pentium4" and running it in my
    computer, the running time was approximately 33 milliseconds.

    When I change to the version of the list which uses the boost pool
    allocator and do the same thing, the running time is a whopping 59
    seconds. That's approximately 1800 times slower.

    What the heck is this pool allocator good for? At least not for speed.
     
    Juha Nieminen, Jul 9, 2008
    #1
    1. Advertising

  2. Juha Nieminen a écrit :
    [snip]
    > Compiling this with "-O3 -march=pentium4" and running it in my
    > computer, the running time was approximately 33 milliseconds.
    >
    > When I change to the version of the list which uses the boost pool
    > allocator and do the same thing, the running time is a whopping 59
    > seconds. That's approximately 1800 times slower.
    >
    > What the heck is this pool allocator good for? At least not for speed.


    From boost documentation

    pool_allocator is a more general-purpose solution, geared towards
    efficiently servicing requests for any number of contiguous chunks.
    fast_pool_allocator is also a general-purpose solution, but is geared
    towards efficiently servicing requests for one chunk at a time; it will
    work for contiguous chunks, but not as well as pool_allocator. If you
    are seriously concerned about performance, use fast_pool_allocator when
    dealing with containers such as std::list, and use pool_allocator when
    dealing with containers such as std::vector.

    --
    Michael
     
    Michael DOUBEZ, Jul 9, 2008
    #2
    1. Advertising

  3. Juha Nieminen

    James Kanze Guest

    On Jul 9, 3:11 pm, Juha Nieminen <> wrote:
    > I tested the speed of a simple program like this:


    > //------------------------------------------------------------
    > #include <list>
    > #include <boost/pool/pool_alloc.hpp>


    > int main()
    > {
    > typedef std::list<int> List_t; // default allocator
    > //typedef std::list<int, boost::pool_allocator<int> > List_t;


    > List_t l;


    > for(int i = 0; i < 100000; ++i)
    > l.push_back(i);


    > int counter = 0;
    > for(List_t::iterator iter = l.begin(); iter != l.end();)
    > if(++counter % 3 == 0)
    > iter = l.erase(iter);
    > else
    > ++iter;


    > for(int i = 0; i < 100000; ++i)
    > l.push_back(i);}
    > //------------------------------------------------------------


    > Compiling this with "-O3 -march=pentium4" and running it in my
    > computer, the running time was approximately 33 milliseconds.


    > When I change to the version of the list which uses the boost
    > pool allocator and do the same thing, the running time is a
    > whopping 59 seconds. That's approximately 1800 times slower.


    Did you expect anything different? The standard has been
    carefully worded so that an implementation can optimize use of
    the standard allocators, in a very container dependent fashion.
    The purpose of the allocator parameter is not for a possible
    optimization, but to support different semantics, and normally,
    I would expect any custom allocator to be slower than the
    standard allocator, at least if the library author has done a
    good job.

    > What the heck is this pool allocator good for? At least not
    > for speed.


    Isn't that question backwards? First, decide what you are
    trying to achieve, and why the standard allocator isn't
    acceptable. Then look for an allocator which achieves what you
    need.

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
     
    James Kanze, Jul 10, 2008
    #3
  4. James Kanze wrote:
    >> When I change to the version of the list which uses the boost
    >> pool allocator and do the same thing, the running time is a
    >> whopping 59 seconds. That's approximately 1800 times slower.

    >
    > Did you expect anything different?


    Certainly. What sense does it make to use an allocator which makes
    allocation almost 2000 times slower? It makes no sense whatsoever.

    Even if this allocator cut total memory usage in half, implemented a
    full garbage collector and performed full boundary checks, it would
    *still* be useless because of the humongous slowdown. It couldn't even
    be used for debugging purposes in programs which allocate even moderate
    amounts of memory.

    As the other poster replied, boost::fast_pool_allocator does a much
    better job at this (although while it's a bit faster than the default
    allocator, it's still no *so* fast).

    So my question remains: What's boost::pool_allocator good for?

    > The standard has been
    > carefully worded so that an implementation can optimize use of
    > the standard allocators, in a very container dependent fashion.


    I believe that. However, I still can't understand what's the use for
    an allocator which is almost 2000 times slower than the default allocator.

    > The purpose of the allocator parameter is not for a possible
    > optimization, but to support different semantics, and normally,
    > I would expect any custom allocator to be slower than the
    > standard allocator, at least if the library author has done a
    > good job.


    Why do you expect that? I can think of four reasons to use a custom
    allocator:

    1) The allocator is way faster than the default allocator.
    2) The allocator consumes considerably less memory than the default
    allocator.
    3) The allocator performs GC or other type of safety checks (which would
    be mostly irrelevant with the STL containers, but anyways).
    4) The allocator does something exotic, such as use a file or a network
    connection as memory, or something along those lines.

    None of these (except perhaps number 4, for rather obvious reasons)
    imply that the allocator ought to be thousands of times slower than the
    default allocator.

    1) and 2) are not even hard to do. I have created such an allocator
    myself (and, in fact, my purpose in trying the boost allocator was to
    compare its speed with mine).

    >> What the heck is this pool allocator good for? At least not
    >> for speed.

    >
    > Isn't that question backwards? First, decide what you are
    > trying to achieve, and why the standard allocator isn't
    > acceptable. Then look for an allocator which achieves what you
    > need.


    I'm trying to achieve maximum allocation/deallocation speed. The
    standard allocator (at least in linux) is very slow.
     
    Juha Nieminen, Jul 10, 2008
    #4
  5. Juha Nieminen a écrit :
    > James Kanze wrote:
    >>> When I change to the version of the list which uses the boost
    >>> pool allocator and do the same thing, the running time is a
    >>> whopping 59 seconds. That's approximately 1800 times slower.

    >> Did you expect anything different?

    >
    > Certainly. What sense does it make to use an allocator which makes
    > allocation almost 2000 times slower? It makes no sense whatsoever.

    [snip]

    It makes sense if you don't want to use the system allocator: for a pet
    thread allocator or if you want to limit memory usage while keeping some
    flexibility in a specific area (I do that in some part of my -embedded-
    software).

    > I'm trying to achieve maximum allocation/deallocation speed. The
    > standard allocator (at least in linux) is very slow.


    Did you try with *fast_pool_allocator* ? I tried quickly with your code
    and without measuring, the time looked equivalent (at least not 1 min
    like with pool_allocator).


    --
    Michael
     
    Michael DOUBEZ, Jul 11, 2008
    #5
  6. Michael DOUBEZ wrote:
    >> Certainly. What sense does it make to use an allocator which makes
    >> allocation almost 2000 times slower? It makes no sense whatsoever.

    > [snip]
    >
    > It makes sense if you don't want to use the system allocator: for a pet
    > thread allocator or if you want to limit memory usage while keeping some
    > flexibility in a specific area (I do that in some part of my -embedded-
    > software).


    I'm sorry, but I *still* don't understand how it makes sense.

    Let me repeat myself: boost::pool_allocator seems to be almost 2000
    times slower than the default allocator. Not 2 times, not even 20 times,
    2000 times.

    What advantage there could ever be from boost::pool_allocator compared
    to the default allocator? Even if you are making just one single
    allocation during the execution of the entire program (in which case the
    speed of the allocation doesn't really matter), I still fail to see what
    would be the benefit over just using the default allocator.

    What is boost::pool_allocator for? Why should I even consider paying
    the humongous price for using it?

    >> I'm trying to achieve maximum allocation/deallocation speed. The
    >> standard allocator (at least in linux) is very slow.

    >
    > Did you try with *fast_pool_allocator* ?


    Yes, it was suggested in an earlier post. That one is indeed a bit
    faster than the default allocator, at least in my linux system, and
    could thus be much more useful. (OTOH it's still much slower than my own
    allocator, which is what I was comparing it against.)

    However, my original question has still not been answered.

    > I tried quickly with your code
    > and without measuring, the time looked equivalent (at least not 1 min
    > like with pool_allocator).


    Actually here fast_pool_allocator is a bit faster than the default
    allocator. If you happened to be interested, I put some results here:
    http://warp.povusers.org/FSBAllocator/#benchmark
     
    Juha Nieminen, Jul 11, 2008
    #6
  7. Juha Nieminen

    Noah Roberts Guest

    Juha Nieminen wrote:
    > Michael DOUBEZ wrote:
    >>> Certainly. What sense does it make to use an allocator which makes
    >>> allocation almost 2000 times slower? It makes no sense whatsoever.

    >> [snip]
    >>
    >> It makes sense if you don't want to use the system allocator: for a pet
    >> thread allocator or if you want to limit memory usage while keeping some
    >> flexibility in a specific area (I do that in some part of my -embedded-
    >> software).

    >
    > I'm sorry, but I *still* don't understand how it makes sense.
    >
    > Let me repeat myself: boost::pool_allocator seems to be almost 2000
    > times slower than the default allocator. Not 2 times, not even 20 times,
    > 2000 times.


    You seem to have tested the architecture unfairly. If the documentation
    states that using pool_allocator in a std::list is inappropriate, as has
    been said in this thread once already, then you need to come up with a
    different test. Your question is completely pointless while it is based
    on poorly arrived at statistics.
     
    Noah Roberts, Jul 11, 2008
    #7
  8. Juha Nieminen

    James Kanze Guest

    On Jul 10, 10:40 pm, Juha Nieminen <> wrote:
    > James Kanze wrote:
    > >> When I change to the version of the list which uses the boost
    > >> pool allocator and do the same thing, the running time is a
    > >> whopping 59 seconds. That's approximately 1800 times slower.


    > > Did you expect anything different?


    > Certainly. What sense does it make to use an allocator which
    > makes allocation almost 2000 times slower? It makes no sense
    > whatsoever.


    You use a non-standard allocator because you need different
    semantics. If you need those semantics, it doesn't matter what
    the speed, since the program won't be correct without them.

    If the semantics are correct with the standard allocator, then
    that's what you should be using.

    [...]
    > > The purpose of the allocator parameter is not for a possible
    > > optimization, but to support different semantics, and normally,
    > > I would expect any custom allocator to be slower than the
    > > standard allocator, at least if the library author has done a
    > > good job.


    > Why do you expect that?


    Because if it were faster, then the implementors of the standard
    library would have used the same algorithms.

    > I can think of four reasons to use a custom allocator:


    > 1) The allocator is way faster than the default allocator.
    > 2) The allocator consumes considerably less memory than the default
    > allocator.
    > 3) The allocator performs GC or other type of safety checks (which would
    > be mostly irrelevant with the STL containers, but anyways).
    > 4) The allocator does something exotic, such as use a file or a network
    > connection as memory, or something along those lines.


    The only possible reason for using a non-standard allocator with
    the STL should be the last. Unless the implementor has not done
    his job correctly.

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
     
    James Kanze, Jul 11, 2008
    #8
  9. James Kanze wrote:
    >> Why do you expect that?

    >
    > Because if it were faster, then the implementors of the standard
    > library would have used the same algorithms.


    I disagree.

    The default allocator is designed for maximum flexibility (meaning
    that it should work with allocated memory blocks of any size) and, if
    possible, optimal memory usage (meaning that even though the memory
    blocks are completely arbitrary in size, the allocator should waste
    ancillary bookkeeping memory as little as possible).

    In other words, the default memory allocator is a completely *generic*
    allocator designed for all possible uses.

    The price to be paid for it being so generic is that it's slower and
    wastes unneeded memory in situations where a much simpler allocator
    would be enough. For example, if you are instantiating a std::list with
    lots of elements, each one of those elements has exactly the same size.
    It would thus be enough to have a memory allocator which just allocates
    memory blocks of that size and nothing else. The amount of required
    bookkeeping is reduced considerably, and the allocator also can be made
    a lot faster (mainly because there's less bookkeeping causing update
    overhead).

    It's perfectly possible to design a memory allocator which is
    specialized for allocations which have all the same size (which is the
    case with std::list, std::set and std::map). Because such allocator is
    much simpler than the default generic allocator, it can be enormously
    faster and waste considerably less memory.
    I know this is possible because I have implemented such a memory
    allocator myself. It *is* considerably faster than the default
    allocator, and it uses less memory.
    Of course this allocator has its limitations. For example, you can't
    allocate arrays with it. However, you don't need the support for array
    allocation when all you are doing is using the allocator with a
    std::list, std::set or std::map.

    >> I can think of four reasons to use a custom allocator:

    >
    >> 1) The allocator is way faster than the default allocator.
    >> 2) The allocator consumes considerably less memory than the default
    >> allocator.
    >> 3) The allocator performs GC or other type of safety checks (which would
    >> be mostly irrelevant with the STL containers, but anyways).
    >> 4) The allocator does something exotic, such as use a file or a network
    >> connection as memory, or something along those lines.

    >
    > The only possible reason for using a non-standard allocator with
    > the STL should be the last. Unless the implementor has not done
    > his job correctly.


    It's rather easy to prove you wrong:
    http://warp.povusers.org/FSBAllocator/#benchmark

    (Ok, you might argue that the implementors of the memory allocator in
    linux libc have not done their job correctly, but that's not a big
    consolation when you are in a situation where you require maximal
    allocation speed for things like std::list.)
     
    Juha Nieminen, Jul 11, 2008
    #9
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Protoman
    Replies:
    2
    Views:
    295
    John Harrison
    Nov 20, 2005
  2. joe
    Replies:
    0
    Views:
    338
  3. James
    Replies:
    0
    Views:
    815
    James
    Jan 1, 2009
  4. James
    Replies:
    0
    Views:
    508
    James
    Jan 1, 2009
  5. Rick Lawson
    Replies:
    8
    Views:
    825
    Graham Dumpleton
    Jul 17, 2009
Loading...

Share This Page