Re: [Boost-bugs] [Boost C++ Libraries] #4264: boost multi_index hashed_unique erase takes linear time

Subject: Re: [Boost-bugs] [Boost C++ Libraries] #4264: boost multi_index hashed_unique erase takes linear time
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2010-06-09 06:36:52

#4264: boost multi_index hashed_unique erase takes linear time
--------------------------+-------------------------------------------------
 Reporter:  anonymous     |       Owner:  joaquin    
     Type:  Bugs          |      Status:  new        
Milestone:                |   Component:  multi_index
  Version:  Boost 1.41.0  |    Severity:  Showstopper
 Keywords:                |  
--------------------------+-------------------------------------------------

Comment(by joaquin):

 ''A possible solution to this bug is to keep an intrusive list of the
 nodes in the table, so begin() and the returned iterator are O(1) when
 using erase(iterator).''

 This would increase the size of nodes, which currently are kept to a
 minimum (one pointer per node).

 ''BTW, it is not amortized. If the bucket table is resized to be 2
 million, and you constantly insert()/erase() a couple of elements. You
 consistently get the worse case scenario.''

 Yes, there are cases where you don'te get the benefit amortization.
 Unordered containers give average case complexity and worst case
 complexity, I'd include the case you describe as a form of the latter.
 Remember these containers are tricky and don't guarantee performance.

 ''Also, since, the bucket vector never shrinks, the problem can also be
 reproduced by insert()ing 2 million objects, then erase()ing them. The
 erase()ing will take forever.''

 This effect is not related to the keeping-track-of-first-non-empty
 feature, but to [http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-

 active.html#579 LWG issue #579], which is something different and I'm
 willing to correct as soon as a resolution is agreed within the C++
 committee.

 ''I was reading gcc4.1.2's unordered_map's/set's hashtable, and it does
 not have this performance bug. gcc4.1.2's unordered_map's/set's
 hashtable's begin() is linear.''

 Yes, you're right, I've taken a look myself and `begin` with the latest
 versions of libstdc++ unordered containers is linear. This is a bug with
 libstdc++, since the op is required to be constant. I'll file a bug report
 to gather feedback from libstdc++ developers.

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/4264#comment:6>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.