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

Question

我正在尝试实现一个 boost::multi_index 应用程序，但性能非常糟糕：插入 10,000 个对象几乎需要 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 声明中的分配器。

Answer 1

出于几个原因，您不能或不应该这样做。

首先，boost::object_pool有一个性能问题：从中释放对象是O(N)。如果你想有效地做到这一点，你需要直接在 boost::pool 之上实现你自己的分配器。原因是 object_pool 使用了 "ordered free" 语义，您不希望它用于您的用例。有关此性能错误的更多详细信息，请参见此处：https://svn.boost.org/trac/boost/ticket/3789

其次，multi_index_container 实际上需要分配一些不同的东西，具体取决于您 select 的索引。能够分配 value_type 是不够的，它需要分配树节点等。这使得它完全不适合与池分配器一起使用，因为池分配器通常假定多个实例的单一类型（或至少单一尺寸）。

如果你想要最好的性能，你可能需要 "roll your own." Boost MIC 和 Boost Pool 不能一起玩。但另一个想法是使用更高性能的通用分配器，例如 tcmalloc：http://goog-perftools.sourceforge.net/doc/tcmalloc.html

您可以考虑 Boost Intrusive，其中包含非常适合集中分配的容器。您可以向 order 类型添加挂钩，以便将它们存储在有序和无序映射中，然后您可以在 boost::pool.

中分配订单

最后，由于您似乎正在存储财务数据，因此您应该知道使用 double 存储价格是危险的。有关更多信息，请参见此处：Why not use Double or Float to represent currency?

Answer 2

您需要做的第一件事（在遇到性能瓶颈时总是如此）- 进行分析！

结果可能（而且很可能会）分配并不是你最糟糕的事情。

Answer 3

让我重申一下 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";
}

当运行在 -O3 模式下，无论 Coliru 使用何种后端，我们得到：

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

我的机器（Intel Core i5-2520M @2.50GHz）中的 VS 2015 发布模式产生：

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

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

一些额外的观察：

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

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

How to use boost::object_pool as a boost::multi_index allocator?

c++

boost

pool

boost-multi-index