Boost logo

Boost :

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

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