[intrusive] Review
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()); }
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
AMDG Ion Gaztañaga <igaztanaga <at> gmail.com> writes:
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)?
Yes. That's what namespaces are for aren't they?
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.
Classes interact better with mpl.
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?
On second thought, no. There are several possible ways that users might want to handle assignment. It's better to force it to be specified explicitly. You might even make the assignment operator private to be safe.
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.
struct safe_mode {}; struct fast_mode {}; struct auto_unlink_mode {}; template<class Tag, class Mode = safe_mode, class Pointer = void*> struct list_hook; template<class Tag, class Pointer> struct list_hook<Tag, safe_mode, Pointer>; template<class Tag, class Pointer> struct list_hook<Tag, fast_mode, Pointer>; template<class Tag, class Pointer> struct list_hook<Tag, auto_unlink_mode, Pointer>;
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)
<snip>
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?
For class templates ADL looks in the namespaces associated with all the template arguments. The result is that an unqualified call to a function that has the same name as one in namespace std can unexpectedly call the std function.
swap_nodes doesn't handle adjacent nodes correctly.
This isn't a problem now
I take that back. It is a problem.
Thanks for reporting it.
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.
The strong guarantee is that if the function fails the program state is unchanged. A partially constructed tree doesn't meet this criterion.
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"?
Yes. This is a very minor issue of course.
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.
Yes. They are acceptable. In Christ, Steven Watanabe
----- Mensaje original ----- De: Steven Watanabe <steven@providere-consulting.com> Fecha: Sábado, Marzo 17, 2007 9:13 pm Asunto: Re: [boost] [intrusive] Review Para: boost@lists.boost.org
AMDG
Ion Gaztañaga <igaztanaga <at> gmail.com> writes:
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.
What about "iterator_to"? I don't get the rationale for the "from" suffix. If i is an iterator and *i==x, one usually says "i is an iterator to x", right? Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
"JOAQUIN LOPEZ MU?Z" <joaquin@tid.es> writes:
----- Mensaje original ----- De: Steven Watanabe <steven@providere-consulting.com> Fecha: Sábado, Marzo 17, 2007 9:13 pm Asunto: Re: [boost] [intrusive] Review Para: boost@lists.boost.org
AMDG
Ion Gaztañaga <igaztanaga <at> gmail.com> writes:
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.
What about "iterator_to"? I don't get the rationale for the "from" suffix. If i is an iterator and *i==x, one usually says "i is an iterator to x", right?
I understand your point, but I believe the idea behind the name is that the function returns an iterator from a reference to an element. I'll throw out another possibility: iterator_at. -- Jeremy Maitin-Shepard
Steven Watanabe wrote:
struct safe_mode {}; struct fast_mode {}; struct auto_unlink_mode {};
template<class Tag, class Mode = safe_mode, class Pointer = void*> struct list_hook;
template<class Tag, class Pointer> struct list_hook<Tag, safe_mode, Pointer>; template<class Tag, class Pointer> struct list_hook<Tag, fast_mode, Pointer>; template<class Tag, class Pointer> struct list_hook<Tag, auto_unlink_mode, Pointer>;
Nice.
For class templates ADL looks in the namespaces associated with all the template arguments. The result is that an unqualified call to a function that has the same name as one in namespace std can unexpectedly call the std function.
Ok
The strong guarantee is that if the function fails the program state is unchanged. A partially constructed tree doesn't meet this criterion.
You are right. Sorry. Regards, Ion
participants (4)
-
"JOAQUIN LOPEZ MU?Z" -
Ion Gaztañaga -
Jeremy Maitin-Shepard -
Steven Watanabe