Re: [boost] [unordered] Buffered functions?

Subject: Re: [boost] [unordered] Buffered functions?
From: Howard Hinnant (hinnant_at_[hidden])
Date: 2008-12-28 15:39:09

On Dec 28, 2008, at 2:41 PM, David Abrahams wrote:

>
> on Sun Dec 28 2008, Howard Hinnant <hinnant-AT-twcny.rr.com> wrote:
>
>> On Dec 28, 2008, at 1:25 AM, David Abrahams wrote:
>>
>>> The conundrum here is that if we use that technique for tuple,  
>>> then a
>>> tuple of empty types can never be empty itself.  I'm starting to  
>>> get ill
>>> just thinking about a generic framework for composing "logically  
>>> empty"
>>> types that undoes this "EBO erasure" effect when necessary.
>>
>> Perhaps I'm misunderstanding.  Reverting from English to C++ in the  
>> hopes of
>> clarification. :-)  The C++0X program and its output below  look  
>> quite reasonable to
>> me:
>>
>
> <snip>
>
> Reasonable, but unless I'm missing something, impossible, unless the
> tuple itself is derived from all those empty bases.  A class  
> containing
> an empty member is not itself empty, IIUC.

Ah, I see what you are saying.  Yes, I agree.

>> I currently favor the "shallow hierarchy" design Doug outlined in c+
>> +std-lib-18989.  Though EMO isn't shown in that description, it is  
>> pretty simple to
>> add to that design.
>
> /me rummages through his committee message archive...
>
> As far as I can tell from that thread, your solution and Doug's  
> shallow
> refinement show exactly the problem you were trying to warn about: any
> empty element types become (private) bases of the tuple type itself,
> leading to unintended namespace associations.  As far as I can tell  
> this
> is no different in spirit from
>
>  namespace std {
>
>  template <class T, class A>
>  class vector
>     : private A
>  {
>      ...
>  };
>
>  }  // std
>
>  Such an implementation of "EMO" is error prone as it associates the  
> namespace of the
>  client-supplied A with that of the vector

Quite so.  I forgot one other language rule when I posted the vector  
example.

[basic.lookup.argdep]/p2/b2:

> ... Furthermore, if T is a class template specialization, its  
> associated namespaces and classes also include: the namespaces and  
> classes associated with the types of the template arguments provided  
> for template type parameters (excluding template template parameters);

Demonstration:

typedef char one;
struct two {one _[2];};

namespace std
{

template <class T, class A>
struct vector
{
};

template <class T, class A>
one test(vector<T, A>);

}  // std

namespace mine
{

struct A {};

two test(std::vector<int, A>);

}  // mine

#include <cstdio>

int main()
{
     std::printf("%zu\n", sizeof(test(std::vector<int, mine::A>())));
}

Output:

2

I.e. The namespace of A is associated with std::vector<T, A>, whether  
or not vector derives from A.  Silly me for forgetting that.  /Some/  
day I may master C++...

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

Back when c++std-lib-18989 was written (about 18 months ago) I  
implemented such a tuple, and used that implementation in preparing my  
previous message demonstrating a space-optimizing tuple.  You are  
quite correct that the tuple does indeed end up deriving (indirectly  
in my example implementation) from client-supplied empty members.  I  
think perhaps one important caveat is that the tuple *does not* derive  
from client-supplied types which have virtual functions (at least no  
known implementation of polymorphic types qualify as "empty").  Said  
differently, this implementation of tuple only derives from empty  
class types, and not from non-empty class types.

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:

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

> We probably should have an EMO in the core language after all.

I would probably be in favor of such a core change.  Indeed, in the  
"next language" I imagine that a tuple-like construct might be a built- 
in type which lays the foundation for the layout of every client- 
defined aggregate type (complete with built-in type and value  
introspection).  Imagine if you could inspect the member types of a  
struct as easily as you can a std::tuple. :-)

-Howard