Faster method of clearing a boost::interprocess::map?

Question

I have an application which uses a boost::interprocess::map in shared memory. The map contains a large number of elements (100k to 10M), and everything works pretty well, with one exception: the map has to be cleared periodically and this seems to take around 4 µs per element (so 40 seconds worst case), which is unacceptable for the application. It looks like clear() actually deletes each map element individually and rebalances the tree after each deletion, so it's horrendously inefficient when you have a large number of elements. Ideally clear() would just delete all the elements without any rebalancing - is there any way I can implement this kind of optimised clear() method myself ?

(Incidentally I've also tried boost:interprocess:flat_map - this has a much faster clear time, as might be expected (10x faster), but it's too slow for insert/delete operations.)

Note: an earlier question on StackOverflow touched on a similar problem with smaller STL maps in normal (i.e. not shared) memory, but didn't really resolve the problem.

Answer 1

From looking at the Boost code, I am guessing you have either:

• Found a bug in the implementation of rbtree

or

• Coded using safe-mode or auto-unlink

From \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);
      }
   }

The comment here clearly states that you can get constant time out of the implemented clear. Paging through the boost code, my reading is that interprocess::map eventually uses this rbtree as the underlying data structure. I did not notice anywhere safemode or auto-unlink were set, but I could have missed it. If you have set one of these, I'd first see if I could live without it, and if so, your performance problems hopefully will go away.

If this is a bug in boost, you'll have to work around it. I'd immediately report it using the contact information in the header:

/////////////////////////////////////////////////////////////////////////////
//
// (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.
//
/////////////////////////////////////////////////////////////////////////////

A quick Google search appears to have contact details for Ion at:

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

Or by going to http://www.boost.org/development/bugs.html

And then implement either Paul R or rileyberton's solution, depending on your level of performance needs.