c++ - 如何使用 boost::object_pool 作为 boost::multi_index 分配器？

Question

我正在尝试实现一个 boost::multi_index 应用程序，但性能非常糟糕:插入 10,000 个对象几乎需要 0.1 秒，这是 Not Acceptable 。因此，当我查看文档并发现 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; 

一般来说，编译器不喜欢在 order_sell 声明中将 boost::object_pool 表达为分配器。

Answer 1

让我重申一下 Alexander 的建议，即您分析程序以了解问题的真正所在。我强烈怀疑 Boost.MultiIndex 本身会像你说的那样慢。以下程序测量了创建 order_sell 容器(没有 Boost.Pool)、用 10,000 个随机订单填充它并销毁它所花费的时间:

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

当 Coliru 使用任何后端以 -O3 模式运行时，我们得到:

Insertion of 10,000 random orders plus container cleanup0.00494657 seg.

我的机器(Intel Core i5-2520M @2.50GHz)中的 VS 2015 Release模式产生:

Insertion of 10,000 random orders plus container cleanup0.00492825 seg.

因此，这比您报告的快 20 倍左右，而且我在测量中包括容器销毁和随机数生成。

一些额外的观察:

• boost::object_pool 不提供标准库为与容器的互操作性指定的分配器接口(interface)。您可能想使用 boost::pool_allocator取而代之(我已经玩了一会儿，但似乎并没有 boost 速度，但你的里程可能会有所不同)。
• John 的回答似乎暗示 Boost.MultiIndex 是次优的，因为它将节点与值或类似的东西分开分配。事实上，该库在内存分配方面尽可能高效，并且您无法使用 Boost.Intrusive 做得更好(实际上您可以获得相同的效果)。看看this answer如果您对 Boost.MultiIndex 内部数据结构的外观感到好奇，请阅读我的文章。特别是，对于具有散列索引和有序索引的 order_sell 容器，每个值都进入其自己的一个节点，另外还有一个单独的所谓的桶数组(指针数组)长度与元素数量大致相同。对于基于节点的数据结构，没有比这更好的了(如果您想放弃迭代器的稳定性，您可以设计出内存效率更高的方案)。