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

Я пытаюсь реализовать приложение boost::multi_index, и производительность очень плохая: вставка 10000 объектов занимает почти 0,1 секунды, что недопустимо. Поэтому, когда я заглядываю в документацию и обнаруживаю, что 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> >
  >,
  boost::object_pool<order>
> order_sell;

В общем, компилятору не нравится выражение boost:: object_pool в качестве распределителя в объявлении order_sell.

Источник

3 ответа

Решение

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

Live Coliru Demo

#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, мы получим:

Вставка 10000 случайных заказов плюс очистка контейнера
0,00494657 сег.

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

Вставка 10000 случайных заказов плюс очистка контейнера
0,00492825 сег.

Итак, это примерно в 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 для представления валюты?

Источник

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

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

Источник
Другие вопросы по тегам