[boost] [graph, python, regex, serialization, thread, multi_index, wave] Efficiency bugs

From: David Abrahams (dave_at_[hidden])
Date: 2005-11-30 07:28:27

I suggest we all review:

  http://home.twcny.rr.com/hinnant/cpp_extensions/On_list_size.html#boost%20survey

It reveals efficiency bugs in

  boost/graph/detail/adjacency_list.hpp
  boost/libs/python/src/object/inheritance.cpp
  boost/regex/pending/object_cache.hpp
  libs/serialization/src/basic_iarchive.cpp
  libs/thread/src/thread.cpp
  boost/multi_index/detail/seq_index_ops.hpp
  boost/wave/util/cpp_macromap.hpp

Sort story: std::list::size is not O(1) (surprise!)


attached mail follows:

To: C++ libraries mailing list
Message c++std-lib-16084

On Oct 26, 2005, at 3:03 PM, Howard Hinnant wrote:

> I recommend just commenting out list::size in your std header, run  
> the tests, and see what fails to compile.  And then check if you  
> approve of the use of std::list::size in each of those cases.  If  
> you do this experiment, I'd love to know the results.
>
> And having to experiment this way is exactly my point.
>
> In fact, run the experiment again and comment out the "splice some"  
> signature this time.  My bet is that list::size will be used much  
> more often than list::splice-some.

I decided to do this survey myself:

http://home.twcny.rr.com/hinnant/cpp_extensions/ 
On_list_size.html#boost%20survey

If boost authors can be bitten by list::size (after peer reviews from  
other boost members), just imagine what it is doing out in the  
trenches...

-Howard


-- 
Dave Abrahams
Boost Consulting
www.boost-consulting.com