Use boost::object_pool can not quit clearly. Am I misusing?

Question

I use boost::object_pool in my program, but I found some problems, it can not quit. Below is the code. Don't suggest me use boost::pool. The boost::pool is no problem, just discuss the boost::object_pool. Could anybody help me?

#include <iostream>
#include <boost/pool/object_pool.hpp>

int main(void) {
    boost::object_pool<int> p;
    int count = 1000*1000;
    int** pv = new int*[count];

    for (int i = 0; i < count; i++)
            pv[i] = p.construct();
    for (int i = 0; i < count; i++)
            p.destroy(pv[i]);

    delete [] pv; 

    return 0;
}

This program can not quit normally. Why?

Answer 1

On my machine, this program works correctly, if very slowly.

The loop calling "destroy" is very slow; it appears to have a O(N^2) bit in it; at least, for each 10x increase in the size of the loops, the run time increases by a factor of 90.

Here are some timings:

1000 elements        0.021 sec
10000 elements       1.219 sec
100000 elements      103.29 secs  (1m43.29s)
1000000 elements     13437 secs   (223m57s)

Answer 2

Someone beat me too it - just saw this question via the boost mailing list.

According to the docs destroy is O(N) so certainly calling this N times isn't ideal for large N - however I imagine that using the Object Pool destructor itself (which calls the destructor for each allocated object) which is itself O(N) would help a lot with bulk deletions).

I did have a graph showing timings on my machine - but since I haven't used Stack Overflow much I can't post it - ah well it doesn't show that much ...

Answer 3

I've published a fix derived from a merge-sort in boost sandbox:

https://github.com/graehl/boost/tree/object_pool-constant-time-free

or, standalone:

https://github.com/graehl/Pool-object_pool