[intrusive] Comments on interface changes and stateful value_traits (long)
Hi to all, First of all, thanks to all who participated in recent threads about Boost.Intrusive options and extended configurability discussions. These days I've been experimenting a bit with this option and also with stateful value_traits (those who could allow non-intrusive hooks). ----------------------------------------- ----------------------------------------- Passing policies to hooks and containers ----------------------------------------- ------------------------------------------ As you know, one of my main concerns is that a container explicitly set with some options, should have the same type as another container defined with the same options in a different order. I meant: list<T, base_hook<my_base_hook>, constant_time_size<false> > should have the same type as: list<T, constant_time_size<false>, base_hook<my_base_hook> > l; My preferred alternative is the more verbose: typedef list_options < base_hook<my_base_hook> , constant_time_size<false>
::type options_t;
list<T, options_t> l; that guarantees the same type for the same options. 1) Implemented interface: I've implemented all current container options using this approach. I've chosen a different options configurer "list_options", "slist_options"... because otherwise, I couldn't set defaults that could lead to the correct types. The default hooks is the base hook so a user can just say: class my_type : public list_base_hook<> {} list<my_type> l; Some options must not be set in the container *but in the hook*, since options affect both the hook and the container. Examples: void pointer definition, the linking policy. I think hook options can be unified so I have: typedef hook_options < void_pointer<offset_ptr<void> > , link<normal_link> , tag<my_tag> >::type hook_options_t; class my_type : public list_base_hook<hook_options_t> { typedef list_base_hook<hook_options_t> my_hook_t; } typedef list_options < base_hook<my_hook_t> , size_type<std::size_t>
::type options_t;
list<T, options_t> l; As you can see, specifying options can be quite verbose (comparing it to the old way, but as new options are added (for example, custom buckets definition in hash containers) users don't have put arguments in order and can change only the options they want to change from the default. 2) Declaration of new classes: template<class T, class ListOptions> class list; template<class T, class SlistOptions> class slist; template<class T, class Pred, class SetOptions> class set; template<class T, class Hash, class Equal, class UsetOptions> class unordered_set; So the declaration of intrusive containers would be exactly the same as the STL containers plus an options argument. 3) Problem: Definition of member hooks is very long class my_type { list_member_hook member_hook_; } typedef list_options < member_hook<my_type, list_member_hook, &my_type::member_hook_>
::type options;
list<my_type, options> l; Why? Because I can't make C++ deduce a pointer to member value in a single template parameter passed to a class. It would be nice that C++ could deduce my_type and list_member_hook from the value directly yielding to: typedef list_options //Deduce my_type and list_member_hook automatically < member_hook<&my_type::member_hook_>
::type options;
If anyone can correct me, I would be *really* glad. 4) Custom value_traits Current interface takes a value_traits class as the first parameter in containers: template<class ValueTraits, bool...> class list; ValueTraits concept is very powerful because allows separating the concepts of a Node and a Value. The node is the minimal structure that is need to form a group of nodes (group of pointers to form a list, a tree...) and the Value is the whole user type that is somehow related to the node (via inheritance, membership, or other). Intrusive documentation offers examples of custom ValueTraits to reuse nodes for different containers or to deal with non modifiable ABI of old code. This is still possible specifying the value_traits instead of the hook: typedef list_options < value_traits<my_value_traits>
::type options;
list<T, my_value_traits> l; --------------------------------------------------------- --------------------------------------------------------- Stateful value_traits (aka allowing extrusive containers) --------------------------------------------------------- --------------------------------------------------------- I've started experimenting with stateful value_traits, while trying to keep zero overhead when ValueTraits is an empty class. There are some problems though: 1) Iterators Iterators containa pointer to node and they use ValueTraits to obtain the user value from the node. If an stateful ValueTraits is used, we also need to store a pointer to the value traits stored in the container. If I want zero overhead when using hooks or just value traits with static functions I have to avoid storing the pointer when the iterator is stateless. How do we know if an allocator is stateless? One possibility is to check if the ValueTraits is empty, that is, has no members. However, this does not guarantee that ValuetTraits will define static functions so that no pointer to ValueTraits is needed to convert from a node to a container. I think it's a good aproximation or I could also define a traits or internal constant to say "this ValueTraits is stateless/stateful". For the moment, my current option is to consider an empty ValueTratis stateless, so it must define conversion functions as static members. 2) Losing static functions Some member functions of intrusive containers are static, so that there is no need to have a reference to the container. This sometimes is very useful (e.g. list::iterator_to) but this can't be achieved if stateful value traits are used. I can think 3 options: -> Convert static functions in non-static (losing some advantages) -> Offer static and non-static versions. Static versions won't compile with stateful allocators (via BOOST_STATIC_ASSERT). -> Someone knows have to make a function static or not depending on a compile-time boolean. 3) Stateless, but taking advantage of composition In a recent discussion about adding custom bucket traits to unordered containers a booster wanted to have the bucket outside the class (for example, to reuse that with other containers). With stateful allocators this can be possible if bucket traits are stateful an contain a pointer to the real bucket traits instance. But this increases the size of your intrusive container. However if the external bucket implementation is very near to the container (said, it's a member of the same structure or whatever), it's possible to obtain the address of the the external resource based on the address of the container or the internal traits instance included in the container. Rei Thiessen was requesting that when he explained the customized bucket info structure. template< unsigned n > struct bucket_info_size_n { /* appropriate constructors... */ bucket_ptr buckets_; template<class T> bucket_ptr buckets( T* container ) const { return buckets_; } size_type buckets_len() const { return 1<<n; } } So based on the address of the container, the user can find the resource (in this case, the bucket array) obtaining zero size overhead (the internal traits is empty). This logic can be extended to every traits class of the container, but specially to ValueTraits. But this would require passing the address of the container to every function the traits class implements. Users not wanting this composition hack surely don't want to change their signatures to just support this extremely advance practice: before class my_value_traits { node_ptr to_node_ptr(value_type &val) //... }; after class my_value_traits { template<class Container> node_ptr to_node_ptr(value_type &val, const Container& cont) //... }; So if there is any metaprogramming hack (if increases compilation time too much, forget it ;-) ) I would like to receive suggestions. Otherwise, a member static const bool saying "pass container address" in value traits might be useful, so that the container changes the calls to the traits with another equivalent one passing the address of the container. I haven't still experimented this composition hack so I'm really open to all suggestions from advanced users. My point is that this should be really optional and should not affect users not using these advanced features. As Rei said (inflating my ego): "These intrusive containers are so close to perfect that it's painful to have to modify them." So let's make them perfect ;-) Regards, Ion
Two more comments on extrusive containers: -> Instead of changing functions passing the address of the container, the traits can define a function called "get_external_traits()" or similar that the container will call before using the trait if the corresponding option is activated (code not compiled, so it might contain errors): //Predeclaration struct external_value_traits; //Internal traits struct internal_value_traits { typedef external_value_traits external_traits; //Suppose external_value_traits is derived //from the container template<class C> static const external_traits *get_external_traits(const C &c) { return static_cast<RealTraits>(c); } }; so we can have something like this: typedef list_options < value_traits<internal_value_traits> , external_value_traits<true>
::type options;
typedef list<T, options> MyList; struct external_value_traits : public MyList { //... snode_ptr to_node_ptr (value_type &value) { //whatever conversion using any external auxiliary data } } -> If external traits are used (for example, external value traits) iterator should be also modified adding an additional pointer pointing to the container (so that the iterator can have access to the external traits to make conversions). I still don't know how can this impact some operations like merging, etc... So external traits look exciting but they might require a bit of work to avoid any overhead to users not activating those advanced options. Regards, Ion
AMDG Ion Gaztañaga <igaztanaga <at> gmail.com> writes:
-> Someone knows have to make a function static or not depending on a compile-time boolean.
static typename boost::enable_if_c<should_be_static, result_type>::type f(); typename boost::disable_if_c<should_be_static, result_type>::type f(); In Christ, Steven Watanabe
On 8/25/07, Steven Watanabe <steven@providere-consulting.com> wrote:
AMDG
Ion Gaztañaga <igaztanaga <at> gmail.com> writes:
-> Someone knows have to make a function static or not depending on a compile-time boolean.
static typename boost::enable_if_c<should_be_static, result_type>::type f(); typename boost::disable_if_c<should_be_static, result_type>::type f();
Does this actually work? Shouldn't enable/disable_if depend on some template arguments of f (and f is not templated here)? I think that, at least under gcc, this doesn't work. GCC will complain (rightly IMHO) that 'type' is not a nested type of disable_if *or* enable_if. gpd gpd
AMDG Giovanni Piero Deretta <gpderetta <at> gmail.com> writes:
Does this actually work? Shouldn't enable/disable_if depend on some template arguments of f (and f is not templated here)?
Right. Never mind. We'll have to wait for concepts. In Christ, Steven Watanabe
AMDG Steven Watanabe <steven <at> providere-consulting.com> writes:
Giovanni Piero Deretta <gpderetta <at> gmail.com> writes:
Does this actually work? Shouldn't enable/disable_if depend on some template arguments of f (and f is not templated here)?
Right. Never mind. We'll have to wait for concepts.
Ok. Here's a method that actually works template<bool is_static, class Derived> struct base; template<class Derived> struct base<true, Derived> { static R f(); }; template<class Derived> struct base<false, Derived> { R f(); }; template<class T> class C : base<f_is_static<T>::value, C<T> > {}; In Christ, Steven Watanabe
Steven Watanabe wrote:
template<bool is_static, class Derived> struct base;
template<class Derived> struct base<true, Derived> { static R f(); };
template<class Derived> struct base<false, Derived> { R f(); };
template<class T> class C : base<f_is_static<T>::value, C<T> > {};
Thanks for your help! So a friendship relationship would be allow implementing the function in the base class. Regards, Ion
AMDG Ion Gaztañaga <igaztanaga <at> gmail.com> writes:
before
class my_value_traits { node_ptr to_node_ptr(value_type &val) //... };
after
class my_value_traits { template<class Container> node_ptr to_node_ptr(value_type &val, const Container& cont) //... };
So if there is any metaprogramming hack (if increases compilation time too much, forget it ) I would like to receive suggestions.
typedef char no; struct yes { no dummy[2]; }; template<class T> yes convert_result(const T&); no convert_result(const no&); template<class T> T make(); template<class Base> struct has_plain_to_node_ptr_impl : Base { no to_node_ptr(...); using Base::to_node_ptr; }; template<class T> struct has_plain_to_node_ptr { enum { value = (sizeof(convert_result( has_plain_to_node_ptr_impl<T>::to_node_ptr( make<const value_type&>() ))) == sizeof(yes))}; }; In Christ, Steven Watanabe
Ion Gaztañaga wrote:
Hi to all,
First of all, thanks to all who participated in recent threads about Boost.Intrusive options and extended configurability discussions. These days I've been experimenting a bit with this option and also with stateful value_traits (those who could allow non-intrusive hooks).
----------------------------------------- ----------------------------------------- Passing policies to hooks and containers ----------------------------------------- ------------------------------------------
As you know, one of my main concerns is that a container explicitly set with some options, should have the same type as another container defined with the same options in a different order. I meant:
list<T, base_hook<my_base_hook>, constant_time_size<false> >
should have the same type as:
list<T, constant_time_size<false>, base_hook<my_base_hook> > l;
My preferred alternative is the more verbose:
typedef list_options < base_hook<my_base_hook> , constant_time_size<false>
::type options_t;
list<T, options_t> l;
that guarantees the same type for the same options.
1) Implemented interface:
I've implemented all current container options using this approach. I've chosen a different options configurer "list_options", "slist_options"... because otherwise, I couldn't set defaults that could lead to the correct types.
That's not necessary: We can combine the options into a nested template in 'options<...>::type' that takes in the defaults.
Some options must not be set in the container *but in the hook*, since options affect both the hook and the container. Examples: void pointer definition, the linking policy. I think hook options can be unified so I have:
typedef hook_options < void_pointer<offset_ptr<void> > , link<normal_link> , tag<my_tag> >::type hook_options_t;
class my_type : public list_base_hook<hook_options_t> { typedef list_base_hook<hook_options_t> my_hook_t; }
typedef list_options < base_hook<my_hook_t> , size_type<std::size_t>
::type options_t;
list<T, options_t> l;
As you can see, specifying options can be quite verbose (comparing it to the old way, but as new options are added (for example, custom buckets definition in hash containers) users don't have put arguments in order and can change only the options they want to change from the default.
Yes. It's inferior to a full named parameter solution and it requires much more metaprogramming to work and probably compiles slower and has more header dependencies than a lightweight solution. Do you really have strong evidence (rather than just suspicions) that you get something in return? IOW: Did you benchmark the difference between a named parameter interface (with measures to reduce bloat, as discussed) and the interface you propose?
2) Declaration of new classes:
template<class T, class ListOptions> class list;
template<class T, class SlistOptions> class slist;
template<class T, class Pred, class SetOptions> class set;
template<class T, class Hash, class Equal, class UsetOptions> class unordered_set;
So the declaration of intrusive containers would be exactly the same as the STL containers plus an options argument.
Consistency with STL weighs little against awkward usage. Everything that has a default is optional and should be an option.
3) Problem: Definition of member hooks is very long
class my_type { list_member_hook member_hook_; }
typedef list_options < member_hook<my_type, list_member_hook, &my_type::member_hook_>
::type options;
list<my_type, options> l;
Why? Because I can't make C++ deduce a pointer to member value in a single template parameter passed to a class. It would be nice that C++ could deduce my_type and list_member_hook from the value directly yielding to:
typedef list_options //Deduce my_type and list_member_hook automatically < member_hook<&my_type::member_hook_>
::type options;
It will always be repetitive. Only thing we could do is provide a macro for convenience.
4) Custom value_traits
Current interface takes a value_traits class as the first parameter in containers:
template<class ValueTraits, bool...> class list;
ValueTraits concept is very powerful because allows separating the concepts of a Node and a Value. The node is the minimal structure that is need to form a group of nodes (group of pointers to form a list, a tree...) and the Value is the whole user type that is somehow related to the node (via inheritance, membership, or other).
Intrusive documentation offers examples of custom ValueTraits to reuse nodes for different containers or to deal with non modifiable ABI of old code. This is still possible specifying the value_traits instead of the hook:
typedef list_options < value_traits<my_value_traits>
::type options;
One could argue ValueTraits (as any traits blob) is too powerful. Why do you still it? Can't you split it up into options? Regards, Tobias
Ion Gaztañaga wrote:
1) Iterators
Iterators containa pointer to node and they use ValueTraits to obtain the user value from the node. If an stateful ValueTraits is used, we also need to store a pointer to the value traits stored in the container. If I want zero overhead when using hooks or just value traits with static functions I have to avoid storing the pointer when the iterator is stateless.
How do we know if an allocator is stateless? One possibility is to check if the ValueTraits is empty, that is, has no members. However, this does not guarantee that ValuetTraits will define static functions so that no pointer to ValueTraits is needed to convert from a node to a container. I think it's a good aproximation or I could also define a traits or internal constant to say "this ValueTraits is stateless/stateful". For the moment, my current option is to consider an empty ValueTratis stateless, so it must define conversion functions as static members.
Boost.TypeTraits defines boost::is_stateless, which would be the appropriate extension point. Some compilers even provide intrinsics for this traits template to work automatically.
2) Losing static functions
Some member functions of intrusive containers are static, so that there is no need to have a reference to the container. This sometimes is very useful (e.g. list::iterator_to) but this can't be achieved if stateful value traits are used. I can think 3 options:
-> Convert static functions in non-static (losing some advantages) -> Offer static and non-static versions. Static versions won't compile with stateful allocators (via BOOST_STATIC_ASSERT). -> Someone knows have to make a function static or not depending on a compile-time boolean.
As we're talking about inline functions you can just pass a (possibly null) pointer to the state into a static functions and the additional argument will get optimized out.
3) Stateless, but taking advantage of composition
In a recent discussion about adding custom bucket traits to unordered containers a booster wanted to have the bucket outside the class (for example, to reuse that with other containers). With stateful allocators this can be possible if bucket traits are stateful an contain a pointer to the real bucket traits instance. But this increases the size of your intrusive container.
Overhead of this kind can always be optional using EBCO (like compressed pair does). Regards, Tobias
Tobias Schwinger wrote:
Ion Gaztañaga wrote:
1) Iterators
Iterators containa pointer to node and they use ValueTraits to obtain the user value from the node. If an stateful ValueTraits is used, we also need to store a pointer to the value traits stored in the container. If I want zero overhead when using hooks or just value traits with static functions I have to avoid storing the pointer when the iterator is stateless.
How do we know if an allocator is stateless? One possibility is to check if the ValueTraits is empty, that is, has no members. However, this does not guarantee that ValuetTraits will define static functions so that no pointer to ValueTraits is needed to convert from a node to a container. I think it's a good aproximation or I could also define a traits or internal constant to say "this ValueTraits is stateless/stateful". For the moment, my current option is to consider an empty ValueTratis stateless, so it must define conversion functions as static members.
Boost.TypeTraits defines boost::is_stateless, which would be the appropriate extension point. Some compilers even provide intrinsics for this traits template to work automatically.
Even if is_stateless is used: template <typename T> struct is_stateless_impl { BOOST_STATIC_CONSTANT(bool, value = (::boost::type_traits::ice_and< ::boost::has_trivial_constructor<T>::value, ::boost::has_trivial_copy<T>::value, ::boost::has_trivial_destructor<T>::value, ::boost::is_class<T>::value, ::boost::is_empty<T>::value >::value)); }; this does not guarantee that the functions will be static. Maybe the only think to do is to use ((T*)0)->func() hack for those classes to avoid storing a pointer to traits. Another problem with is_stateless is that if there are no intrinsic functions, the function will always return false, because trivial destructors,constructors and copy constructor can only be detected using intrinsics (remember that ValueTraits might not be a POD and even if it's a POD, I need intrinsics to detect that).
2) Losing static functions
Some member functions of intrusive containers are static, so that there is no need to have a reference to the container. This sometimes is very useful (e.g. list::iterator_to) but this can't be achieved if stateful value traits are used. I can think 3 options:
-> Convert static functions in non-static (losing some advantages) -> Offer static and non-static versions. Static versions won't compile with stateful allocators (via BOOST_STATIC_ASSERT). -> Someone knows have to make a function static or not depending on a compile-time boolean.
As we're talking about inline functions you can just pass a (possibly null) pointer to the state into a static functions and the additional argument will get optimized out.
Well, I wouldn't like users to do that because that would require knowing the internals of the library (you have to know if "this" is being used somehow). Hoperfully, Steven's solution seems appropriate.
3) Stateless, but taking advantage of composition
In a recent discussion about adding custom bucket traits to unordered containers a booster wanted to have the bucket outside the class (for example, to reuse that with other containers). With stateful allocators this can be possible if bucket traits are stateful an contain a pointer to the real bucket traits instance. But this increases the size of your intrusive container.
Overhead of this kind can always be optional using EBCO (like compressed pair does).
No, you always have an overhead with the proposed example. You must store a pointer inside the internal traits that point to the real external traits. What I want to achieve is storing a stateless traits-proxy (with zero overhead using EBCO) that can get the address of the external traits because the external traits is somehow (inheritance, member...) related to the address of the container. This allows external traits with zero size overhead. Regards, Ion
<...> It seems here's a misunderstanding. I meant: - Always use static functions in the traits - Always pass a 'this' pointer to the static functions - Make that pointer be a NULL pointer if the pointee is_stateless Regards, Tobias
on Fri Aug 24 2007, Ion Gaztañaga <igaztanaga-AT-gmail.com> wrote:
As you know, one of my main concerns is that a container explicitly set with some options, should have the same type as another container defined with the same options in a different order. I meant:
list<T, base_hook<my_base_hook>, constant_time_size<false> >
should have the same type as:
list<T, constant_time_size<false>, base_hook<my_base_hook> > l;
My preferred alternative is the more verbose:
typedef list_options < base_hook<my_base_hook> , constant_time_size<false>
::type options_t;
list<T, options_t> l;
that guarantees the same type for the same options.
What is the advantage to that over make_list < base_hook<my_base_hook> , constant_time_size<false>
::type l;
?? -- Dave Abrahams Boost Consulting http://www.boost-consulting.com The Astoria Seminar ==> http://www.astoriaseminar.com
David Abrahams wrote:
What is the advantage to that over
make_list < base_hook<my_base_hook> , constant_time_size<false>
::type l;
Just that programmers might found it more familiar, like an STL container, but I must say that your approach gives me much more guarantee of a single type, something that is difficult to achieve with: set<T, set_options<...>::type >; because I can't define the same options structure as: set<T, set_options<pred<std::less<T> >, ...>::type >; ... because I have no access to the T type of the set from set_options (I could pass it again, but that would be verbose. Whereas if I define: make_set<T, pred<std::less<T>>, ...>::type l; I have all the needed data to produce a single type. Although it's a bit different from standard container definitions, your suggestion might be the right thing to do to achieve both single type and less typing. So I guess that I can offer both Tobias' approach: set<T, pred<std::greater<T>, > and your approach for people that want to make sure that the same types are being created when specifying the same options. Thanks, Ion
participants (5)
-
David Abrahams -
Giovanni Piero Deretta -
Ion Gaztañaga -
Steven Watanabe -
Tobias Schwinger