[boost] [intrusive] Review

From: Steven Watanabe (steven_at_[hidden])
Date: 2007-03-16 00:14:52

AMDG

I think that Intrusive should be accepted into Boost.

The documentation is good.

I had no problems compiling with msvc 8.0

The design and implementation are pretty straightforward.

I have needed embedded linked lists at least once in the last year.
So, I definitely have a use for this library.

intrusive.qbk line 136
  [*Boost.Intrusive]container
missing space

intrusive.qbk lines 169-170
  because the object can be destroyed before erasing it from the container.
Dangling participle

intrusive.qbk line 172
  However swapping can be used to implement move-capabilities
missing comma after however.

intrusive.qbk line 263-264
  A class that the user must add as a base class or as a member to its 
own class
its should be his.  A user is a person not a thing.

intrusive.qbk line 306-307
  it can store the number of stored elements to achieve constant-time
  size information, it can offer debugging facilities...
Using store twice sounds a little odd.  These are both complete sentences
and should therefore be separated by a semicolon instead of a comma.

islist is a terrible name. I automatically read this as a predicate (is 
X a list)

the second template parameter of ilist_base_hook &c. could be an mpl::bool_
or better it could be unique type that expresses the meaning better.
  struct safe_mode {};
  struct fast_mode {};

intrusive.qbk line 531
   typedef boost::intrusive::ilist_base_hook<Foo>::value_traits<Foo> 
FooValueTraits;
should be
   typedef boost::intrusive::ilist_base_hook<Tag>::value_traits<Foo> 
FooValueTraits;

intrusive.qbk line 564
  Sometimes a 'is-a' relationship
a should be an

intrusive.qbk line 689-690
  That's why you better avoid them in public interfaces of libraries.
"That's why you should avoid them in public interfaces of libraries."?

ilist_hook.hpp line 121
  ilist_base_hook& ilist_base_hook::operator=(const ilist_base_hook& );
I'm not sure that forbidding assignment of nodes that
are linked is a good idea.

ilist_hook.hpp line 163
   bool ilist_base_hook::linked() const;
Since this is only allowed in safe mode it should fail
to compile instead of asserting at runtime.

On further reflection the safe mode and non-safe mode variants
are sufficiently different to warrant two specializations.

config_begin line 12, config_end.hpp line 15
  #ifdef _MSC_VER
should be
  #ifdef BOOST_MSVC

I suggest this implementation for the default size_type parameter.
As it stands, ADL pulls in namespace std for the containers. (ADL
pulls in namespace detail, too but there are no fully generic
functions in namespace boost::intrusive::detail)

  struct default_size_type {};

  template<class T>
  struct get_size_type { typedef T type };

  template<>
  struct get_size_type<default_size_type> { typedef std::size_t type };

  template< class ValueTraits
          , bool  ConstantTimeSize = true
          , class SizeTypeParam         = default_size_type>
  class ilist
     :  private detail::size_holder<ConstantTimeSize, typename 
get_size_type<SizeTypeParam>::type>
  {
      typedef typename get_size_type<SizeTypeParam>::type SizeType;
      //...
  };

swap_nodes doesn't handle adjacent nodes correctly.  This isn't a
problem now but you might make a note of it just in case it does
become a problem.

For slist you might consider adding a pointer to the last element so that
swap can execute in constant time.  clone_from can use insert_after to
be optimally efficient.

I'm unclear about the usefulness of clone_from.  First of
all it doesn't look more efficient than what I would write
by hand.  Second, it only provides the basic guarantee although the
strong guarantee can be achieved as follows for ilist (assuming
that destroyer completely reverses the effects of cloner).

   template <class Cloner, class Destroyer>
   void clone_from(const ilist &src, Cloner cloner, Destroyer destroyer)
   {
      class cleanup {
      public:
          cleanup(Destroyer& d) : destroyer(d) {}
          ~cleanup() { value.clear_and_destroy(destroyer); }
          ilist value;
          Destroyer& destroyer;
      } temp(destroyer);
      for(const_iterator b(src.begin()), e(src.end()) ; b != e; ++b){
         temp.value.push_back(*cloner(*b));
      }
      this->swap(temp.value);
   }

The principal use I can think of for clone_from is a container
that can hold objects of different types.  You might change
doc_clone_from.cpp to use a polymorphic clone function instead of
new so that it doesn't seem quite so contrived.

member_hooks do not work with virtual inheritance. This blows up.

  #include <boost/intrusive/ilist.hpp>

  struct Y {};

  struct X : virtual public Y {
      boost::intrusive::ilist_member_hook<X> hook;
      int i;
  };

  typedef boost::intrusive::ilist_member_hook<X>::value_traits<&X::hook> 
value_traits;

  int main() {
      X x;
      boost::intrusive::ilist<value_traits> list;
      list.push_back(x);
      list.front().i = 1;
  }

I don't think that current is a good name for the function
that gets an iterator from the value_type.  How about something
a little more descriptive like get_iterator, iterator_from, or
to_iterator?

I would prefer to use CRTP for hooks
  template<class Derived, class Tag, bool SafeMode, class Pointer>
  struct ilist_base_hook;

Or at least use a metafunction instead of a member template
for the value_traits.
  template<class Hook, class T>
  struct base_hook_value_traits;

The base class hooks should be in a nested namespace and be
brought into namespace intrusive with using to prevent unwanted ADL.

The BOOST_STATIC_ASSERT in ilist needs to be INTERNAL ONLYed.

I compared the performance of sort for ilist on a std::random_shuffled
set of one million ints with msvc 8.0. (code is attached)

    INTRUSIVE .51 sec
    LIST .89 sec
    LIST POINTER 1.14 sec
    VECTOR .20 sec
    VECTOR STABLE .23 sec
    VECTOR POINTER .46 sec
    VECTOR POINTER STABLE .42 sec

In Christ,
Steven Watanabe


// sort_benchmark.cpp
//
// Copyright (c) 2007
// Steven Watanabe
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)

#include <ctime>
#include <vector>
#include <list>
#include <algorithm>
#include <iostream>
#include <boost/lambda/lambda.hpp>
#include <boost/lambda/bind.hpp>
#include <boost/intrusive/ilist.hpp>

//#define INTRUSIVE
//#define LIST
#define VECTOR
//#define POINTER
#define STABLE

struct Y {};

struct X {
#ifdef INTRUSIVE
    boost::intrusive::ilist_member_hook<X> hook;
#endif
    int i;
    bool operator<(const X& other) const {
        return(i < other.i);
    }
    X(int val) : i(val) {}
};

#ifdef POINTER
    typedef X* x_type;
    #define PREDICATE *boost::lambda::_1 < *boost::lambda::_2
    #define TRANSFORM &boost::lambda::_1
#else
    typedef X x_type;
    #define PREDICATE boost::lambda::_1 < boost::lambda::_2
    #define TRANSFORM boost::lambda::_1
#endif

#ifdef STABLE
    #define SORT std::stable_sort
#else
    #define SORT std::sort
#endif

int main() {

#ifdef LIST
    typedef std::list<x_type> list_t;
#elif defined(VECTOR)
    typedef std::vector<x_type> list_t;
#elif defined(INTRUSIVE)
    typedef boost::intrusive::ilist<boost::intrusive::ilist_member_hook<X>::value_traits<&X::hook> > list_t;
#endif
    list_t list;
    std::vector<X> x;
    for(int i = 0; i < 1000000; ++i) {
        x.push_back(X(i));
    }
    std::random_shuffle(x.begin(), x.end());
    std::for_each(x.begin(), x.end(), boost::lambda::bind(&list_t::push_back, boost::lambda::var(list), TRANSFORM));

    {
        std::clock_t start_time = std::clock();
#if defined(LIST) || defined(INTRUSIVE)
        list.sort(PREDICATE);
#else
        SORT(list.begin(), list.end(), PREDICATE);
#endif
        std::cout << "time for sort: " << static_cast<double>(std::clock() - start_time) / CLOCKS_PER_SEC << std::endl;
    }
    
    list_t::const_iterator iter(list.begin());
    list_t::const_iterator end(list.end());
    list.erase(list.begin(), list.end());
}