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

Subject: [Boost-bugs] [Boost C++ Libraries] #4264: boost multi_index hashed_unique erase takes linear time
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2010-05-27 01:16:41

#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:                |  
--------------------------+-------------------------------------------------
 Hi,

 We are using a multi_index with several hashed_unique indices. We make the
 number of bucket pretty large to avoid hash key clashes.

 When we do an erase, the time it takes is linear to the number of buckets.
 What happens is that erase returns an iterator to the next item, which
 means that it has to search linearly through all the buckets until it find
 a bucket with an item in it. In our tests it takes several milliseconds
 for this to happen (we have 1000000 buckets). As the number of items in
 the multi_index decreases, the performance gets worse because it has to do
 a linear search further to find a non-empty bucket.

 When the item from the first non-empty bucket is deleted, it also takes
 longer because the hashed index keeps a variable to know what the first
 non empty bucket is. when the first non-empty bucket becomes empty, it has
 to do another linear search to find the next non-empty bucket.

 I would suggest to have erase return void, and not to keep track of the
 first non-empty bucket, so that erase will take the expected constant
 time. Iterating is expected to take linear time so if that is slow it is
 expected, but erase should be constant time.

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