Determinism in hash tables

[tolikzinovyev]

Hello. I really like absl hash tables but non-determinism in the iteration order is not desirable for my purpose: simulations. Would you accept a patch that disables non-determinism with a compiler flag? I can imagine, it will also be useful for debugging a program.

[derekmauro]

This isn't something we'd accept.

Part of Abseil's philosophy is engineering at scale. In addition to making it harder to execute a hash flooding attack, another reason we randomize iteration order is that is makes it easier for use to change the underlying implementation if we need to. When we wanted to change our hash function (for example), we found thousands of unit tests that depended on iteration order. We could not just break these tests and say "sorry, you are violating Hyrum's Law" since we would have thousands of angry Google developers. So instead, we fixed the tests and implemented randomization so that next time we wanted to change something in the implementation, this would not be an issue. The need for iteration order determinism is relatively rare compared to the potential wins we get by being free to change the implementation (maybe to make the hash table faster, which could save millions of cycles at scale, for example). By giving users a knob to disable the randomness, we'd be in the same situation all over again.

[tolikzinovyev]

Makes sense, thank you. I have another proposal then.
We could make a boolean constant in a separate file that when flipped would disable non-determinism. So, when a user needs to debug their program, they would still need to change the absl code but only one line.

[derekmauro]

I think that is a better suggestion, but there are costs to keeping superfluous code around, so we generally don't do it.

[tolikzinovyev]

I understand.