Boost logo

Boost :

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


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


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>
     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>
print_sizeof_elements<Tuple, I, I>
     void operator()() const

template <class Tuple>
test(const char* name)
     std::printf("---- %s -----\n", name);
     std::printf("is_empty<%s> = %d\n", name,
     std::printf("tuple_size<%s> = %zu\n", name,
     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,
     std::tuple<empty1> 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_;

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!

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! :-)


Boost list run by bdawes at, gregod at, cpdaniel at, john at