Boost logo

Boost :

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk