boost::object_pool::free() is very slow.

[Dai Yun <dy95020@…>]

boost::object_pool::free() Design is very bad。The main problem is in ： [void * simple_segregated_storage<SizeType>::find_prev(void * const ptr)] Whenever a user to delete a node, we must traverse to the previous nodes from list head. Means, if we have created 10,000 objects and 9,000 removed from the ground, then when the user to delete the first 9001 objects, he would traverse the list from scratch 9,000 times.

[Dai Yun <dy95020@…>]

object_pool.hpp + Main.hpp

[anonymous]

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

[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?

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]

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.

[edupuis]

Patch is a complete rewrite of object_pool.

[edupuis]

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]

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]

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.

[edupuis]

(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.

[edupuis]

​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]

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);

}

to

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

store().free(chunk);

}

[anonymous]

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]

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]

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).

[feicheng@…]

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

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