[Boost-bugs] [Boost C++ Libraries] #6324: Flyweight performance improvement

Subject: [Boost-bugs] [Boost C++ Libraries] #6324: Flyweight performance improvement
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2011-12-25 14:58:20

#6324: Flyweight performance improvement
----------------------------------------------------------------+-----------
 Reporter:  Koh Ohnishi <k_onishi@…>                            |       Owner:  joaquin    
     Type:  Bugs                                                |      Status:  new        
Milestone:  To Be Determined                                    |   Component:  multi_index
  Version:  Boost 1.48.0                                        |    Severity:  Problem    
 Keywords:  flyweight, multi_index, hashed_unique, performance  |  
----------------------------------------------------------------+-----------
 Hi,
 I am using flyweight for storing char_string, and when I do an erase one
 of the flyweight entry when there are a lot of entries, I am facing the
 performance issue, like ticket #4264 mentioned, in multi_index
 hashed_unique erase in boost/flyweight/hashed_factory.hpp
 hashed_factory_class::erase(handle_type) .

 There are two reasons.

 1. hashed_factory_class::erase should call erase with key, like
 cont.erase(cont.key_extractor()(*(cont.iterator_to(*h))));
 instead of calling
 cont.erase(cont.iterator_to(*h));
 as Change History of #4264 mentions.

 2. boost::multi_index hashed_unique erase takes linear time against the
 bucketsize, even if you use erase method with key, as ticket #4264's
 Change History mentioned. It calculates begin() and do linear search the
 top of the node when erasing some node.

 These two behavior cause significant performance penalty when a lot of
 entries are stored in flyweight.

 I think most of users of multi_index hashed_unique are expecting not O(1)
 begin(), but O(1) erase(key). I would like the erase method of
 hashed_unique should perform O(1).

 Thanks,

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