Re: [boost] [unordered] Buffered functions?

Subject: Re: [boost] [unordered] Buffered functions?
From: David Abrahams (dave_at_[hidden])
Date: 2008-12-27 18:57:55

on Tue Nov 25 2008, Howard Hinnant <howard.hinnant-AT-gmail.com> wrote:

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

One thing I've always wondered about this: in that case -- at least when
you're not also trying to use the small object optimization -- why not
always use a Pimpl idiom where an empty container (with no capacity) can
be represented by a single null pointer?

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

Except that there is no "empty member optimization," right?  Unless this
is one of the langauge changes I've failed to notice (and there are a
few), I think what you mean is that tuple is free to use derivation to
take full advantage of the EBO, right?

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

Until we get CWG to agree that the EMO exists, I doubt straw polls in
LWG can make much difference ;-)

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com