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:26:53

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

> >> 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.
> >
> > True, but maps suffer from the same problem don't they?
> > Is a fix even available for maps?
> >
> 
> I'm not an expert here; I thought map was "safe" due to its self-balancing.

map<> is usually a red-black tree, these suffer from exponential 
performance loss when written to by multiple threads due to enormous 
cache line invalidation caused by the rebalance.

It is quite trivial to DDoS any network service stupid enough to 
write to a std::map from more than one thread. Just add any load at 
all.

Note that mostly read and very rare writes from multiple thread users 
of a std::map are just fine, but a std::unordered_map will be that 
much better again in that scenario.

It would be nice to have a bitwise_trie STL container, it would 
provide almost all the benefits of std::map but be enormously 
superior in every facet apart from closest fit finds. In particular, 
bitwise tries let you do constant time "close fit" finds whereas a 
red black tree goes all the way and forces closest fit finds when for 
some use cases that is overkill.

Niall

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