Re: [boost] [unordered] Buffered functions?

Subject: Re: [boost] [unordered] Buffered functions?
From: Howard Hinnant (hinnant_at_[hidden])
Date: 2008-12-28 18:31:44

On Dec 28, 2008, at 4:55 PM, David Abrahams wrote:

> on Sun Dec 28 2008, Howard Hinnant <hinnant-AT-twcny.rr.com> wrote:
>
>>>
>>> And, BTW, this is all way too hard; at its limit it leads to  
>>> building
>>> every generic class template out of tuples instead of ordinary  
>>> members.
>>
>> This conclusion would be an option for class template designers,  
>> not a
>> requirement.  And it would be easier than constantly reinventing EMO.
>
> Yes, but, why should we have to worry about that?

<practical>

Because language supported EMO isn't a realistic possibility in C++0X  
but allowing (not requiring) EMO emulation in tuple is a realistic  
possibility (N2800 arguably already allows the latter).

</practical>

That being said, if you can get an easier to use solution into C++0X,  
then you're the man! :-)

>> Because of this caveat, and because of the associated namespace  
>> rule involving
>> template parameters of template class types, I have not yet  come  
>> up with a way for
>> clients to detect the size optimization with  the following  
>> exceptions (which I hope
>> are acceptable to clients):
>>
>> 1.  The tuple size optimization can be detected with sizeof.
>> 2.  The tuple size optimization can be detected by comparing the  
>> addresses of empty
>> members and seeing that they may not be unique with  respect to  
>> other tuple members:
>
> Hmm,
>
>    int f(void*);
>    char* f(some_empty_type*);
>
>    int x = f(tuple_containing_some_empty_type); // compilation error.

Excellent test case, thanks!

Ok, I've made a slight tweak to my example implementation, and to the  
test case.  The tuple still does space compression, but not to the  
extent as shown previously.  Still, I believe it equals the  
performance of boost::compressed_pair:

#include <tuple>
#include <cstdio>

struct empty1 {};
struct empty2 {};
struct empty3 {};

template <class Tuple, unsigned I = 0,
                        unsigned S = std::tuple_size<Tuple>::value>
struct
print_sizeof_elements
{
     void operator()() const
     {
         std::printf("sizeof element %u is %zu\n", I, sizeof(typename  
std::tuple_element<I, Tuple>::type));
         print_sizeof_elements<Tuple, I+1>()();
     }
};

template <class Tuple, unsigned I>
struct
print_sizeof_elements<Tuple, I, I>
{
     void operator()() const
     {
     }
};

template <class Tuple>
void
test(const char* name)
{
     std::printf("---- %s -----\n", name);
     std::printf("is_empty<%s> = %d\n", name,  
std::is_empty<Tuple>::value);
     std::printf("tuple_size<%s> = %zu\n", name,  
std::tuple_size<Tuple>::value);
     print_sizeof_elements<Tuple>()();
     std::printf("sizeof(%s) = %zu\n", name, sizeof(Tuple));
};

int f(void*) {std::printf("int f(void*)\n");}
char* f(empty1*) {std::printf("char* f(empty1*)\n");}

int main()
{
     test<std::tuple<empty1> >("std::tuple<empty1>");
     test<std::tuple<empty1, empty2> >("std::tuple<empty1, empty2>");
     test<std::tuple<empty1, empty2, empty3> >("std::tuple<empty1,  
empty2, empty3>");
     test<std::tuple<int, empty1> >("std::tuple<int, empty1>");
     test<std::tuple<int, empty1, empty2> >("std::tuple<int, empty1,  
empty2>");
     std::tuple<empty1> t;
     f(&t);
}

---- std::tuple<empty1> -----
is_empty<std::tuple<empty1>> = 0
tuple_size<std::tuple<empty1>> = 1
sizeof element 0 is 1
sizeof(std::tuple<empty1>) = 1
---- std::tuple<empty1, empty2> -----
is_empty<std::tuple<empty1, empty2>> = 0
tuple_size<std::tuple<empty1, empty2>> = 2
sizeof element 0 is 1
sizeof element 1 is 1
sizeof(std::tuple<empty1, empty2>) = 1
---- std::tuple<empty1, empty2, empty3> -----
is_empty<std::tuple<empty1, empty2, empty3>> = 0
tuple_size<std::tuple<empty1, empty2, empty3>> = 3
sizeof element 0 is 1
sizeof element 1 is 1
sizeof element 2 is 1
sizeof(std::tuple<empty1, empty2, empty3>) = 1
---- std::tuple<int, empty1> -----
is_empty<std::tuple<int, empty1>> = 0
tuple_size<std::tuple<int, empty1>> = 2
sizeof element 0 is 4
sizeof element 1 is 1
sizeof(std::tuple<int, empty1>) = 4
---- std::tuple<int, empty1, empty2> -----
is_empty<std::tuple<int, empty1, empty2>> = 0
tuple_size<std::tuple<int, empty1, empty2>> = 3
sizeof element 0 is 4
sizeof element 1 is 1
sizeof element 2 is 1
sizeof(std::tuple<int, empty1, empty2>) = 4
int f(void*)

Note that as you asserted previously, a tuple is never empty.   
However, for this tuple it is possible that the sum of the sizeof its  
elements is less than the sizeof the tuple.  This means that (for  
example), one could write create a smart pointer like so:

template <class T, class D = default_delete<T>>
class unique_ptr
{
     tuple<T*, D> data_;
public:
     ...
};

And not have to worry about whether D is a function pointer or empty  
policy class, and still get sizeof(unique_ptr) == sizeof(T*) when D / 
is/ an empty policy class.

The implementation technique for tuple which is used is:

template <class ..._Tp>
class tuple
{
     typedef __tuple_impl<typename __make_tuple_indices<sizeof... 
(_Tp)>::type, _Tp...> base;
     base base_;  // a member, not a base class!
public:
     ...
};

where __tuple_impl subsequently derives from __tuple_leaf:

template<size_t ..._Indx, class ..._Tp>
struct __tuple_impl<__tuple_indices<_Indx...>, _Tp...>
     : public __tuple_leaf<_Indx, _Tp>...
{ ... };

and __tuple_leaf either derives from _Tp if _Tp is an empty class,  
else it contains _Tp as a member.

>> #include <tuple>
>> #include <cstdio>
>>
>> struct empty1 {};
>> struct empty2 {};
>>
>> int main()
>> {
>>    typedef std::tuple<empty1, empty2> T2;
>>    T2 t;
>>    std::printf("address of std::get<0>(t) is %p\n", &std::get<0>(t));
>>    std::printf("address of std::get<1>(t) is %p\n", &std::get<1>(t));
>> }
>>
>> address of std::get<0>(t) is 0xbffff65f
>> address of std::get<1>(t) is 0xbffff65f
>>
>> "Unacceptable" means of detecting this optimization would include a  
>> change in overload
>> resolution due to associated namespaces depending  on whether or  
>> not the space
>> optimization was performed (which would  likely be error prone).
>
> It's not just a matter of what namespaces are associated, but also  
> which
> functions in those namespaces will match.

<nod>  Thanks for the good test case.  Please come up with more! :-)

-Howard