Boost logo

Boost :

Subject: Re: [boost] [optional] operator<(optional<T>, T) -- is it wrong?
From: Niall Douglas (s_sourceforge_at_[hidden])
Date: 2014-12-02 15:11:44

On 1 Dec 2014 at 13:45, Gottlob Frege wrote:

> > Why should the lack of a cryptographically safe hash matter when you are not
> > doing cryptography?
> >
> > It doesn't really matter what hash is used in internal data structures.
> > (Although obviously there are desirable properties such as having uniform
> > spread to minimise bucket collisions and improve lookup speed.)
> >
> Denial of Service attack - I carefully force the input data such that
> the hashes collide and you get worse-case hash-table performance.
> This is a real attack. Python and a few other languages have already
> fixed their hashes, we have not.

Actually we need a new std::safe_hash<> I think, one explicitly
prohibited from being a trivial hash. I'd personally like to see that
become the default hash for unordered_map et al, and let the
programmer choose std::hash where safe.

BTW I think MSVC/Dinkumware *has* fixed their std::hash<>, theirs is
several orders of magntitude more complex than the trivial hash
libstdc++ uses. Indeed this leads to MSVC's apparent poor
unordered_map performance when compared to GCC (about a 12-40%
performance loss).

Stephan can probably confirm or refute this claim of MSVC/Dinkumware
having a safe hash though. It may just be he uses a well distributed
hash instead of a trivial hash, not one cryptographically safe.

> As I said,the hash was only one reason. There were others, IIRC. I
> do agree that unordered_map will become more popular in the future, so
> that the issue is lessened. (Also, map should have been called
> ordered_map, and unordered_map called 'map'...)

FYI my proposed concurrent_unordered_map is particularly collision
resistant, and therefore much less prone to DDoS attacks. I use a
linear table scan of 16 byte items to resolve collision, so it takes
quite a while for that to become a serious performance issue. Note I
didn't choose this design for DDoS attacks, rather due to the
proposed design having an extremely costly rehash(), so much so that
you'd put up with a lot of collision before expending the enormous
cost of rehashing.


ned Productions Limited Consulting

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