Re: [boost] [optional] operator<(optional<T>, T) -- is it wrong?

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.

Niall

-- 
ned Productions Limited Consulting
http://www.nedproductions.biz/ 
http://ie.linkedin.com/in/nialldouglas/