Re: [boost] [unordered] Buffered functions?

Subject: Re: [boost] [unordered] Buffered functions?
From: Howard Hinnant (howard.hinnant_at_[hidden])
Date: 2008-11-25 23:35:06

On Nov 25, 2008, at 4:42 PM, David Abrahams wrote:

> on Mon Nov 24 2008, "Daniel James" <daniel_james-AT-fmail.co.uk>  
> wrote:
>
>> 2008/11/24 Thorsten Ottosen <thorsten.ottosen_at_[hidden]>:
>>>
>>> 1. storing two functors had to do with implementing exception  
>>> safety if
>>> copying of the functors may throw. Was it swap() that was the  
>>> problem?
>>
>> Here's the original post where I described the problem:
>>
>> http://lists.boost.org/Archives/boost/2005/02/80211.php
>>
>> I think it also applies to assignment.
>
> This looks like a bug in the standard.  Equality and hashing should be
> required to be nothrow-swappable.  I've raised that issue on the
> committee reflector.

Fwiw, I support nothrow-swappable and encourage others to express  
their opinions on this issue.  This is a decision that will impact all  
of us.

>>> 2. the space optimization only gave little less space.
>>
>> The cost from not using EBO amounts to a few bytes - which can
>> sometimes be offset due to alignment. Since 4 bytes is typically
>> required per bucket it doesn't seem like a large amount.
>
> Some people really care about the space taken up by an empty  
> container.

<nod> Believe it or not vector<unordered_set<A>> is a viable  
container, even when many of those inner containers are empty.  If the  
overhead(unordered_set<A>) can be 5 words instead of 9 words (or  
more), then the ability to fit a data structure into nearly half the  
space is a significant size *and* speed optimization (for some clients).

It is never the number of words that matter in shaving off the space  
overhead of a container.  It is the percent difference in space  
overhead between an optimized and unoptimized implementation that  
matters.  Because for the clients who care, they have a very large  
number of containers which statically have a small size().  If you can  
cut the overhead(container) by 25% or more, it is a big win.

>> It seems like you think compressed pair can only compress away one
> member, but IIUC you can chain them and then derive your hash table  
> from
> that to compress as much as you like.  Of course it would be nice to
> have a compressed_tuple that handles it all for us, but I thikn you
> _can_ do it.

I have high hopes that std::tuple will become the compressed_pair of  
the future.  Technically, and especially with variadic template  
language support, it is not that hard to do (tuple is a pain no matter  
what without variadic template language support).  Standards-wise, the  
current C++0X draft (N2798) does not outlaw, nor mandate, the empty  
member optimization for tuple, and I hope to keep it that way.  Recent  
straw polls on the LWG have been favorable to allowing the empty  
member optimization for std::tuple.

-Howard