Re: [boost] [intrusive] Comments on interface changes and stateful value_traits (long)

From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2007-08-26 05:53:44

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