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-08 17:27: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 anonymous):

 Hello again

 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.

 I have measured this performance problem many times.
 erase()ing/replace()ing/modify()ing a single node can take a millisecond
 on a bucket table of 2 million.  I would consider that a significant
 performance penalty especially when one insert()s/erase()s only a few
 elements repeatedly in between insert()ing/erase()ing 1 million elements.

 Thanks,
 Sasha

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