17

我有一个使用boost::interprocess::map共享内存的应用程序。地图包含大量元素（100k 到 10M），一切运行良好，但有一个例外：地图必须定期清除，每个元素似乎需要大约 4 µs（因此最坏情况下需要 40 秒），这是不可接受的应用程序。看起来clear()实际上是单独删除每个地图元素并在每次删除后重新平衡树，所以当你有大量元素时，它的效率非常低。理想情况下clear()只删除所有元素而不进行任何重新平衡 - 有什么办法可以自己实现这种优化clear()方法吗？

（顺便说一句，我也尝试过boost:interprocess:flat_map- 这有更快的清除时间，正如预期的那样（快 10 倍），但对于插入/删除操作来说太慢了。）

注意：StackOverflow 上的一个较早的问题涉及在普通（即非共享）内存中使用较小的 STL 映射的类似问题，但并没有真正解决问题。

4

1 回答 1

2

通过查看 Boost 代码，我猜你有：

  • 在rbtree的实现中发现了一个bug

或者

  • 使用安全模式或自动取消链接进行编码

从 \boost_1_54_0\boost\intrusive\rbtree.hpp

   //! <b>Effects</b>: Erases all of the elements.
   //!
   //! <b>Complexity</b>: Linear to the number of elements on the container.
   //!   if it's a safe-mode or auto-unlink value_type. Constant time otherwise.
   //!
   //! <b>Throws</b>: Nothing.
   //!
   //! <b>Note</b>: Invalidates the iterators (but not the references)
   //!    to the erased elements. No destructors are called.
   void clear()
   {
      if(safemode_or_autounlink){
         this->clear_and_dispose(detail::null_disposer());
      }
      else{
         node_algorithms::init_header(this->priv_header_ptr());
         this->priv_size_traits().set_size(0);
      }
   }

此处的评论清楚地表明，您可以从实施的明确中获得恒定的时间。翻阅 boost 代码，我的阅读是 interprocess::map 最终使用这个 rbtree 作为底层数据结构。我没有注意到设置了安全模式或自动取消链接的任何地方，但我可能会错过它。如果你设置了其中一个，我会先看看我是否可以没有它，如果是这样，你的性能问题有望消失。

如果这是 boost 中的一个错误，您将不得不解决它。我会立即使用标题中的联系信息进行报告：

/////////////////////////////////////////////////////////////////////////////
//
// (C) Copyright Ion Gaztanaga  2006-2012
//
// Distributed under the Boost Software License, Version 1.0.
//    (See accompanying file LICENSE_1_0.txt or copy at
//          http://www.boost.org/LICENSE_1_0.txt)
//
// See http://www.boost.org/libs/intrusive for documentation.
//
/////////////////////////////////////////////////////////////////////////////

快速的谷歌搜索似乎有 Ion 的联系方式：

http://boost.2283326.n4.nabble.com/template/NamlServlet.jtp?macro=user_nodes&user=161440

或访问 http://www.boost.org/development/bugs.html

然后根据您的性能需求水平实施 Paul R 或 rileyberton 的解决方案。

于 2013-10-24T19:18:57.953 回答