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-07 07:53:06

#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):

 ''The problem with keeping track of the first non-empty bucket is just as
 big a problem, we use it for an ultra low latency application and we can't
 use any function that has linear time, even if it is only one in a few
 calls. we can't afford the risk that our erase() happens to be erasing the
 first non-empty bucket and causes a linear search no matter how infrequent
 it may happen.''

 The possible linear search is amortized across different calls to `erase`,
 so in average the time taken is constant. Have you actually measured
 whether this is making an impact on your app?

 ''Would it be possible to have a function call on the hashmap that I can
 explicitly call to disable this keeping-track-of-first-non-empty feature,
 with the understanding that begin() will no longer have constant time
 complexity?''

 There's no technical impediment to doing this, but I won't unless there's
 a compelling argument that the keeping-track-of-first-non-empty feature is
 having a significant performance penalty. Take into account other
 implementations of C++0x unordered associative containers also have this
 feature to ensure a constant complexity `begin`.

 ''what would be the ramifications of begin() having linear time
 complexity?''

 It's a violation of the standard. `begin` is required to be constant (not
 amortized contant), hence we can't say cache the first non-empty bucket to
 make it amortized contant, and the keeping-track-of-first-non-empty
 feature has to be implemented on insertion and deletion time.

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