It was recently discovered that the implementation of
HashMap in the standard library can be susceptible to behavior which can cause pathological performance typically seen as part of HashDoS attacks. The default implementation of
HashMap is specifically designed to be resistant to this style of attack, though, so this is definitely a bug that needs fixing!
The specific issue here is currently purely
map.extend(other_map) and isn’t actually at all related to SipHash being used, but rather the fact that we expose key insertion order when iterating over map. This pathological performance seems to be tied to the linear probing done by our robin hood hash maps currently.
There’s some possible mitigation strategies outlined in the issue iteslf at the top, some of the more promising being:
- Go back to having per-hashmap SipHash keys so all iteration order is random.
- Otherwise try to randomize iteration order
- Explore alternate implementations which aren’t susceptible to this problem (as proposed by @bluss)
Are you interested in helping out here? Got some ideas of what we might be able to do to solve this? Post here!