[Boost-bugs] [Boost C++ Libraries] #4308: multi_index's hashed_index 2 performance bugs

Subject: [Boost-bugs] [Boost C++ Libraries] #4308: multi_index's hashed_index 2 performance bugs
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2010-06-07 22:32:18

#4308: multi_index's hashed_index 2 performance bugs
--------------------------+-------------------------------------------------
 Reporter:  anonymous     |       Owner:  joaquin    
     Type:  Bugs          |      Status:  new        
Milestone:  Boost 1.43.0  |   Component:  multi_index
  Version:  Boost 1.44.0  |    Severity:  Showstopper
 Keywords:                |  
--------------------------+-------------------------------------------------
 Hello

 The hashed_index within the multi_index project has such a major
 performance problem on anything that erases (i.e. erase, replace, modify)
 that the hash_index is unusable unless one never erases.

 The bug is reproduced by:
 - rehash()ing the table to 2 million buckets
 - inserting an element (which is correctly O(1))
 - erasing that element

 Yes, the hashed_index is documented to be O(size of bucket vector), but it
 should not be.  erase on a hash table should be O(1) just like in the TR1.

 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).  Another
 possible solution is to make begin() O(size of bucket vector) which is
 acceptable given that begin() is a linear interface.

 Obviously, the initial rehashing of the buckets to 1 million is standard
 practice for optimizing hash table performance, so this should not be
 eliminated.  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.

 Thanks,
 Sasha

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