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/