Как использовать boost::object_pool в качестве распределителя boost::multi_index?

Позвольте мне повторить предложение Александра о том, чтобы вы профилировали свою программу, чтобы понять, в чем на самом деле заключается проблема. Я сильно сомневаюсь, что Boost.MultiIndex как таковой может быть таким медленным, как вы говорите. Следующая программа измеряет время, необходимое для создания контейнера order_sell (без Boost.Pool), заполнения его 10 000 случайных заказов и его уничтожения:

Текущая демонстрация Coliru

#include <algorithm>
#include <array>
#include <chrono>
#include <numeric> 

std::chrono::high_resolution_clock::time_point measure_start,measure_pause;

template<typename F>
double measure(F f)
{
  using namespace std::chrono;

  static const int              num_trials=10;
  static const milliseconds     min_time_per_trial(200);
  std::array<double,num_trials> trials;
  volatile decltype(f())        res; /* to avoid optimizing f() away */

  for(int i=0;i<num_trials;++i){
    int                               runs=0;
    high_resolution_clock::time_point t2;

    measure_start=high_resolution_clock::now();
    do{
      res=f();
      ++runs;
      t2=high_resolution_clock::now();
    }while(t2-measure_start<min_time_per_trial);
    trials[i]=duration_cast<duration<double>>(t2-measure_start).count()/runs;
  }
  (void)res; /* var not used warn */

  std::sort(trials.begin(),trials.end());
  return std::accumulate(
    trials.begin()+2,trials.end()-2,0.0)/(trials.size()-4);
}

void pause_timing()
{
  measure_pause=std::chrono::high_resolution_clock::now();
}

void resume_timing()
{
  measure_start+=std::chrono::high_resolution_clock::now()-measure_pause;
}

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/member.hpp>

using namespace boost::multi_index;

struct order
{
    unsigned int    id;
    unsigned int    quantity;
    double          price;
};

struct id{};
struct price{};

typedef multi_index_container<
  order,
  indexed_by<
    hashed_unique<
      tag<id>,BOOST_MULTI_INDEX_MEMBER(order, unsigned int, id)>,
    ordered_non_unique<
      tag<price>,BOOST_MULTI_INDEX_MEMBER(order ,double, price),
        std::less<double> >
  >
> order_sell; 

#include <iostream>
#include <random>

int main()
{
  std::cout<<"Insertion of 10,000 random orders plus container cleanup\n";
  std::cout<<measure([](){
    order_sell os;
    std::mt19937                                gen{34862};
    std::uniform_int_distribution<unsigned int> uidist;
    std::uniform_real_distribution<double>      dbdist;

    for(unsigned int n=0;n<10000;++n){
      os.insert(order{uidist(gen),0,dbdist(gen)});
    }
    return os.size();
  })<<" seg.\n";
}

При запуске в режиме -O3 с любым бэкэндом, который использует Coliru, мы получаем:

Insertion of 10,000 random orders plus container cleanup
0.00494657 seg.

Режим выпуска VS 2015 на моей машине (Intel Core i5-2520M @ 2,50 ГГц) дает:

Insertion of 10,000 random orders plus container cleanup
0.00492825 seg.

Итак, это примерно в 20 раз быстрее, чем вы сообщаете, и я включаю в свои измерения разрушение контейнера и генерацию случайных чисел.

Пара дополнительных наблюдений:

• boost::object_pool не предоставляет интерфейс распределителя, указанный стандартной библиотекой для взаимодействия с контейнерами. Вы можете использовать boost::pool_allocator вместо этого (я немного поиграл с ним и, похоже, скорость не улучшилась, но ваш пробег может отличаться).
• Ответ Джона, кажется, подразумевает, что Boost.MultiIndex неоптимален в том смысле, что он выделяет узлы отдельно от значений или что-то в этом роде. На самом деле, библиотека настолько эффективна, насколько это возможно с точки зрения распределения памяти, и вы не можете добиться большего успеха с Boost.Intrusive (на самом деле вы можете получить то же самое). Взгляните на этот мой ответ, если вам интересно, как выглядят внутренние структуры данных Boost.MultiIndex. В частности, для вашего контейнера order_sell с хешированным индексом и упорядоченным индексом каждое значение помещается в один собственный узел, плюс у вас есть отдельный так называемый массив ведра (массив указателей) с длина примерно равна количеству элементов. Вы не можете улучшить структуру данных на основе узлов (если вы хотите обойтись без стабильности итератора, вы можете разработать схемы, более эффективные с точки зрения памяти).

Вы не можете или не должны этого делать по нескольким причинам.

Во-первых, у boost::object_pool есть проблема с производительностью: освобождение объектов от него — это O(N). Если вы хотите сделать это эффективно, вам нужно реализовать свой собственный распределитель непосредственно поверх boost::pool. Причина в том, что object_pool использует семантику "заказано бесплатно", что вам не нужно для вашего варианта использования. Дополнительные сведения об этой ошибке производительности см. здесь: https://svn.boost.org/trac/boost/ticket/3789

Во-вторых, multi_index_container на самом деле нужно выделить несколько разных вещей, в зависимости от выбранных вами индексов. Недостаточно иметь возможность выделить value_type, необходимо выделить узлы дерева и т. д. Это делает его совершенно непригодным для использования с распределителем пула, поскольку распределитель пула обычно предполагает наличие множества экземпляров одного типа (или, по крайней мере, одного размера) .

Если вам нужна наилучшая производительность, вам, возможно, придется «свернуть свою собственную». Boost MIC и Boost Pool определенно не будут хорошо работать вместе. Но другая идея заключается в использовании более производительного распределителя общего назначения, такого как tcmalloc: http://goog-perftools.sourceforge.net/doc/tcmalloc.html

Вы можете рассмотреть Boost Intrusive, который контейнеры, которые хорошо подходят для распределения в пуле. Вы можете добавить хуки к вашему типу order, чтобы позволить хранить их в упорядоченных и неупорядоченных картах, а затем вы можете разместить заказы в boost::pool.

Наконец, поскольку кажется, что вы храните финансовые данные, вы должны знать, что использование double для хранения цен опасно. Подробнее об этом см. здесь: Почему бы не использовать Double или Float представлять валюту?

Первое, что нужно сделать (как всегда при узких местах в производительности) — это профилировать!

Может оказаться (и, вероятно, так и будет), что распределение — не самое худшее для вас.