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%
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 http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk