Boost C++ Libraries: Ticket #3789: boost::object_pool::free() is very slow.

attachment set

Tue, 22 Dec 2009 07:05:12 GMT

attachment → object_pool.rar

object_pool.hpp + Main.hpp

cc set

John Maddock — Fri, 07 Jan 2011 11:23:57 GMT

cc boostpool@… added

anonymous — Mon, 17 Oct 2011 07:22:36 GMT

Replying to johnmaddock: Why is this patch not getting applied in all the boost releases till now? Any specific reason..

anonymous — Mon, 17 Oct 2011 11:56:49 GMT

There are so many differences between your version and current trunk, that I can't figure out what you're proposing: can you please post a diff and/or explain what changes you're proposing?

BTW, there is no maintainer for Boost.Pool at present which is why this issue has languished for so long :-( I will try and figure out how to fix this issue though...

John Maddock.

anonymous — Mon, 31 Oct 2011 08:35:08 GMT

Replying to anonymous:

There are so many differences between your version and current trunk, that I can't figure out what you're proposing: can you please post a diff and/or explain what changes you're proposing?

The version submitted here is not mine, but i wrote the comment2. I was just interested to know, when there will be a fix.

Thanks, Gokul.

owner, status changed

edupuis — Thu, 03 May 2012 16:46:18 GMT

owner changed from Peng Yu to edupuis
status new → assigned

edupuis — Thu, 03 May 2012 19:54:40 GMT

Patch is a complete rewrite of object_pool.

edupuis — Fri, 04 May 2012 05:27:01 GMT

In fact the current implementation is as follows :

O(1) for requesting an object, thus O(n) to request n objects;
O(n) for releasing an object, thus O(n²) to release n objects;
O(n) for deleting the pool.

In my opinion, it would be better if it was

O(1) for requesting an object, thus O(n) to request n objects;
O(1) for releasing an object, thus O(n) to release n objects;
O(n²) for deleting the pool or O(1) if the user kindly released all requested objects. Using a sort algorithm, it is perhaps possible to make this O(n log n).

John Maddock — Sat, 05 May 2012 08:55:12 GMT

I'm not sure that what you're looking for is actually possible?

The problem here is that object_pool always calls the ordered_(allocate|free) functions which are slow to free when there are a lot of free objects in the underlying pool.

IMO it would have been better to have had object_pool have two allocate/free functions (ordered and unordered) like pool does, I thought about making that change, but it's a breaking change so I resisted it. Better still I can't help but thinking that the whole design is wrong (having ordered and unordered free methods in the same class that is). Then if you get into O(N) ordered free you're basically reimplementing the system allocator which is the whole thing that pool was trying to avoid. Maybe this limitation should just have better documentation - that pool is designed for fast allocate/free of small numbers of objects - and is not a complete heap replacement?

edupuis — Tue, 08 May 2012 10:42:37 GMT

Hi John,

The change I am proposing is possible (see ticket #6610); I would simply modify object_pool call the non ordered version of malloc and free. I would need also a member function 'order' who whould order the pool, function that could be called in the destructor prior to applying the method that destroys all non released object.

The pool.order() method would be O(n log n) complexity, using an in-place merge sort.

This modification I am suggesting would not break the API, only speed-up the free function and slow down the destructor, for those lazy programmers that do not release all objects they have allocated...

Now that I have started digging into the code (I have already fixed tickets #5902, #6561, #6701, #6865 and #6867 in the boost sandbox), I agree with you that the design is weird and could be improved a lot.

For example, the fact that the user supplied allocator is made of static non member functions makes it almost impossible to make something useful of it.

cc changed

edupuis — Tue, 08 May 2012 10:43:02 GMT

cc edupuis added

status changed; resolution set

edupuis — Thu, 10 May 2012 21:10:58 GMT

status assigned → closed
resolution → fixed

(In [78412]) Added a pool.order() function, which transforms an unordered pool into an ordered one. Call this function in object_pool::~object_pool() if suitable, which allows to use pool.malloc() and pool.free() instead of pool.ordered_malloc() and pool.ordered_free().

This changes the complexity of object_pool.destroy(), going from O(n) to O(1), while the complexity of the destructor goes from O(n) to O(n log n) if the pool user has not released all pool objects, otherwise the destructor is O(1).

This fixes #3789 and makes it possible to have pools holding millions of objects.

status changed; resolution deleted

edupuis — Mon, 21 May 2012 05:59:09 GMT

status closed → reopened
resolution fixed

milestone changed

anonymous — Tue, 22 May 2012 06:42:43 GMT

milestone Boost 1.42.0 → To Be Determined

cc, owner, status changed

edupuis — Mon, 16 Jul 2012 19:59:27 GMT

cc edupuis removed
owner changed from edupuis to John Maddock
status reopened → new

https://svn.boost.org/svn/boost/sandbox/pool at revision 79460 contains a solution for tickets #3789, #5902, #6561, #6610, #6701, #6718, #6865 and #6867. Related test cases are also present.

https://svn.boost.org/svn/boost/sandbox/pool at revision 79460 does not contain any other new features or modifications other than those related to the above tickets.

Boost.Pool currently has no maintainer and is thus orphaned.

anonymous — Fri, 07 Jun 2013 23:03:13 GMT

I was recently hit by this problem. In my application, if I use boost::object_pool, it runs 12 seconds. Through profiling, I know it was due to find_prev(). So I replaced it with boost:pool. Now it finishes in 1 second.

I was wondering if we can simply do the following change to fix the problem?

void free BOOST_PREVENT_MACRO_SUBSTITUTION(element_type * const chunk) { ...

store().ordered_free(chunk);

}

void free BOOST_PREVENT_MACRO_SUBSTITUTION(element_type * const chunk) { ...

store().free(chunk);

}

anonymous — Sat, 07 May 2016 00:14:46 GMT

I think there is a much better solution than those previously proposed.

The object pool currently contains a single linked list of free objects, which makes it o(1) to allocate a single object. Why not simply to have two linked lists -- one for freed objects and one for allocated objects? Then freeing all allocated objects becomes O(N) and freeing N objects manually is also O(N).

anonymous — Sat, 07 May 2016 00:14:48 GMT

I think there is a much better solution than those previously proposed.

anonymous — Sat, 07 May 2016 00:14:49 GMT

I think there is a much better solution than those previously proposed.

feicheng@… — Fri, 29 Jul 2016 05:17:08 GMT

Boost.Pool currently has no maintainer and is thus orphaned.

so bad.................