Subject: Re: [boost] [object_pool]too slow?
From: Ben Muzal (bmuzal_at_[hidden])
Date: 2009-03-16 13:45:25
Object pool is very slow. destroy() is O(n) where n is the number of
free objects. Therefore if you allocate N objects and then destroy N
objects, you end up with a O(N^2) runtime.
LET ME SAY THAT AGAIN: ObjectPool is O(n^2) FOR THE TYPICAL USAGE OF A POOL!!!
The ( bad IMHO ) reason for doing this is in order to keep the free
list sorted so that ~ObjectPool() runs in O(n) instead of O(n^2).
However, if it wanted to ~ObjectPool() could just sort the free list
in O(n logn) so there is no need at all for destroy() to keep it
However, my personal feelings about a pool is that the pool should not
be calling the destructors on any objects that are still allocated
when the pool is destroyed. I know that standard containers will call
distructors, but a pools are NOT a container.
The usage of a pool is closer to the new and delete operator. If you
'new' an object, and then do an exit(), your object does not get
deleted before the process is destroyed. Why should a pool work any
differently? If you want to create a bunch of objects and then destroy
them all at once, then use a container. If you have any allocated
objects still around when a pool is destroyed, It is a bug unless the
process is about to exit.
I thought about submitting a patch, but I don't think there is anyone
who is maintaining boost::pool.
The workaround to make object pool fast is just to modify object pool
header to use free() instead of orderedFree() and then modify the
destructor to not call the destructors of the objects that are still
On Wed, Mar 11, 2009 at 11:42 PM, Qiu Yuzhou <qbowater_at_[hidden]> wrote:
> Lock is slow. The pool lib is for performance.
> 2009/3/12 <jon_zhou_at_[hidden]>:
>> seems only singleton_pool is thread-safe? but it just only alloc memory and does not call ctor...
>> why object_pool is not designed as thread-safe?
> Just like the stl container vector,list... are not thread-safe. The
> user should lock his mutex by himself if it's in need.
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk