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



Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk