Использование boost::object_pool не может выйти явно. Я неправильно использую?

Question

Я использую Boost:: Object_pool в моей программе, но я нашел некоторые проблемы, он не может выйти. Ниже приведен код. Не предлагайте мне использовать boost:: pool. Boost:: pool не проблема, просто обсудите boost:: object_pool. Кто-нибудь может мне помочь?

#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;
}

Эта программа не может выйти нормально. Зачем?

Answer 1

На моей машине эта программа работает правильно, если очень медленно.

Цикл, вызывающий "уничтожить", очень медленный; похоже, в нем есть бит O(N^2); по крайней мере, для каждого 10-кратного увеличения размера петель время выполнения увеличивается в 90 раз.

Вот некоторые моменты:

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

Answer 2

Кто-то тоже меня побил - просто увидел этот вопрос через список рассылки буста.

В соответствии с документами уничтожение является O(N), поэтому, безусловно, вызов этого N раз не идеален для больших N - однако я представляю, что использование самого деструктора Object Pool (который вызывает деструктор для каждого выделенного объекта), который сам является O(N) очень поможет с массовым удалением).

У меня действительно был график, показывающий время на моей машине - но так как я не использовал переполнение стека, я не могу опубликовать его - ну, ну, это не так уж много показывает...

Answer 3

Я опубликовал исправление, полученное из сортировки слиянием в буст-песочнице:

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

или автономно:

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