Re: [boost] [intrusive] Review

From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2007-03-16 13:03:42

Hi Steven,

Steven Watanabe wrote:
> AMDG
> 
> I think that Intrusive should be accepted into Boost.

Thanks!

> The documentation is good.

Thanks again!

> 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.

Glad to hear it.

> <documentation fixes>

Thanks for your corrections.

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

If Intrusive's containers are placed inside boost::intrusive, you would 
prefer just using boost::instrusive::list, boost::instrusive::slist... 
(without the i prefix)?

> 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 {};

Ok. Even an enum could do the job.

 > <more doc corrections>

Thanks.

> 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.

So you would prefer an empty assignment operator?

> 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.

Ok. I will change that to a compilation error.

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

That can be an option. Other programmers request unifying safe mode/ 
non-safe mode an auto-unlink classes in the same templated class. So I'm 
afraid that someone is not going to be happy ;-) I will think about it.

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

Ok.

> 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;
>      //...
>  };

I must admit that I don't know much about ADL but I can't understand why 
this is problematic. I can understand what "ADL pulls in namespace std 
for the containers" means:

template< class ValueTraits
         , bool  ConstantTimeSize = true
         , class SizeType         = std::size_t>
class ilist
    :  private detail::size_holder<ConstantTimeSize, SizeType>

is the default parameter "std::size_t" doing harm here?

> 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.

Thanks for reporting it.

> For slist you might consider adding a pointer to the last element so that
> swap can execute in constant time.

Maintaining a pointer to the last element would increase the size of the 
container, which is not desirable in some situations. Maintaining an 
extra pointer to the last element would also forbid auto-unlink hooks, 
because those hooks have no reference to the container to update that 
pointer. I will think about it.

> clone_from can use insert_after to
> be optimally efficient.

Right. How could I miss that? ;-(

> 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.  

Well, not in the case of slist and list but I don't think it's the case 
for set/multiset (where insert is not used, and no comparisons are 
performed since it uses structural cloning). Apart from that, I think it 
saves some code to the programmer writing operator=().

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).

You are right. I think I should change all clone_from functions to 
obtain strong guarantee. When dealing with trees, the optimized cloning 
function does not offer strong guarantee, because the tree is not 
balanced if the cloner throws an exception. But I think I could find a 
one offer strong guarantee in that the red-black tree cloning function 
rebalancing that partially constructed tree.

> 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;
>  }

Ummm. I think the nasty offset trick I'm using with member hooks to save 
a pointer to the parent structure might be doing some harm. This can be 
a serious problem. Thanks for reporting it.

> 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?

"iterator_from" sounds good.

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

Why do you prefer them? To avoid specifying the type in the internal 
"value_traits"?

> The BOOST_STATIC_ASSERT in ilist needs to be INTERNAL ONLYed.

You mean that because it appears in the documentation? It's a 
Doxygen/Boostbook problem I've already reported.

> 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

I consider that intrusive list sorting should be specially compared with 
STL list sorting, so do you consider these number acceptable? Thanks for 
the test.

Regards,

Ion