5 ms·

This bug is an example of why the absl swiss tables have nondeterministic iteration order. Found so many bugs in the codebase when this got turned on. https://

This bug is an example of why the absl swiss tables have nondeterministic iteration order. Found so many bugs in the codebase when this got turned on. https://abseil.io/docs/cpp/guides/container#iteration-order-instability https://abseil.io/docs/cpp/guides/container#iteration-order-...

yxhuvud 5y ago
Yes, hash tables need to iterate in either a guaranteed order (usually insertion order) or a guaranteed to be random order. Either choice make sense, but one of them needs to be picked or people will create bugs like this.
- masklinn 5y ago
  FWIW most modern hash tables are randomised on a per-run basis as side-effect if the hash being seeded with a random value for attacker-controlled collision resistance.
  - mikemike 5y ago
    One year ago I hardened LuaJIT's VM against these kind of attacks. Since then, there has been a constant influx of complaints and issues filed. All bitterly complaining their code, which mistakenly assumed a fixed hash table iteration order, is now broken. Even when told that the Lua manual clearly states the undefined order since 20 years, they do not cease to complain. They do not realize this change helped them to discover a serious bug in their code (the order could differ even before that change). Sigh. You can now have a guess, what one of the lesser enlightened forks of LuaJIT did ...
    - masklinn 5y ago
      I’m not surprised. The same issue occurred in python. And to be fair it’s a pain in the ass to debug and find out why something happens to implicitly depend on iteration order (float stability is common but not alone). And their code did work beforehand, for most values of work. The biggest pain in the ass is that — at least in python - while you can set the hash seed explicitely if you don’t the langage doesn’t tell you. This makes reproducing the issue very annoying when only some seeds trigger it. > the order could differ even before that change While the order could differ I assume it was deterministic and nothing influencing those bits had changed in a while.
      - Rendello 5y ago
        > The same issue occurred in python. And now, as predicted by core developer Raymond Hettinger in his Modern Dictionaries talk, Python's dicts are now guaranteed to be ordered by default (as of 3.7).
        randomswede 5y ago
        That makes me sad.
        xsmasher 5y ago
        Curious why? Clearly this is a landmine that many people step on. Why not remove it?
        asdfasgasdgasdg 5y ago
        To the extent this creates a performance penalty, it's a little annoying that a few systems create a behavior dependency that is not truly needed in a core type when there is a separate type that implements the desired semantics. But then again if it doesn't make it slower it should be fine.
        Rendello 5y ago
        Fwiw, the way Raymond re-implemented dictionaries made them more efficient (the algorithms are the same, but it's now much more cache friendly), and had the side effect of making them ordered. He and many others advocated for having the ordering guaranteed going forward.
        randomswede 5y ago
        And now they're locked into an implementation that is order-preserving, even if an optimization tomorrow could eke out another 10%, if ordering was not guaranteed.
    - BlueTemplar 5y ago
      Reminds me how Factorio devs modified Lua 5.2 to actually guarantee a fixed table iteration order so as to insure determinism : https://lua-api.factorio.com/latest/Libraries.html https://lua-api.factorio.com/latest/Libraries.html
  - yxhuvud 5y ago
    That hash values get distributed differently inside the hash to avoid collision attacks is totally unrelated to what iteration order you get when you iterate elements in the hash. You can easily get predictable iteration order and have hash collisions that is not predictable. Look at Python, Ruby, PHP - they have defined iteration order to be insertion order. Javascript also have predictable order though the order is a bit more complex. Go is the outlier in that it defines it as guaranteed to be random. But both choices are just fine.
    - masklinn 5y ago
      > totally unrelated to what iteration order you get when you iterate elements in the hash That is a bit too strong am assertion: you can decorrelate the two when you build the collection, but the naive set up is very much that hash randomisation will randomise iteration order.

yxhuvud 5y ago

Yes, hash tables need to iterate in either a guaranteed order (usually insertion order) or a guaranteed to be random order. Either choice make sense, but one of them needs to be picked or people will create bugs like this.

masklinn 5y ago
FWIW most modern hash tables are randomised on a per-run basis as side-effect if the hash being seeded with a random value for attacker-controlled collision resistance.
- mikemike 5y ago
  One year ago I hardened LuaJIT's VM against these kind of attacks. Since then, there has been a constant influx of complaints and issues filed. All bitterly complaining their code, which mistakenly assumed a fixed hash table iteration order, is now broken. Even when told that the Lua manual clearly states the undefined order since 20 years, they do not cease to complain. They do not realize this change helped them to discover a serious bug in their code (the order could differ even before that change). Sigh. You can now have a guess, what one of the lesser enlightened forks of LuaJIT did ...
  - masklinn 5y ago
    I’m not surprised. The same issue occurred in python. And to be fair it’s a pain in the ass to debug and find out why something happens to implicitly depend on iteration order (float stability is common but not alone). And their code did work beforehand, for most values of work. The biggest pain in the ass is that — at least in python - while you can set the hash seed explicitely if you don’t the langage doesn’t tell you. This makes reproducing the issue very annoying when only some seeds trigger it. > the order could differ even before that change While the order could differ I assume it was deterministic and nothing influencing those bits had changed in a while.
    - Rendello 5y ago
      > The same issue occurred in python. And now, as predicted by core developer Raymond Hettinger in his Modern Dictionaries talk, Python's dicts are now guaranteed to be ordered by default (as of 3.7).
      - randomswede 5y ago
        That makes me sad.
        xsmasher 5y ago
        Curious why? Clearly this is a landmine that many people step on. Why not remove it?
        asdfasgasdgasdg 5y ago
        To the extent this creates a performance penalty, it's a little annoying that a few systems create a behavior dependency that is not truly needed in a core type when there is a separate type that implements the desired semantics. But then again if it doesn't make it slower it should be fine.
        Rendello 5y ago
        Fwiw, the way Raymond re-implemented dictionaries made them more efficient (the algorithms are the same, but it's now much more cache friendly), and had the side effect of making them ordered. He and many others advocated for having the ordering guaranteed going forward.
        randomswede 5y ago
        And now they're locked into an implementation that is order-preserving, even if an optimization tomorrow could eke out another 10%, if ordering was not guaranteed.
  - BlueTemplar 5y ago
    Reminds me how Factorio devs modified Lua 5.2 to actually guarantee a fixed table iteration order so as to insure determinism : https://lua-api.factorio.com/latest/Libraries.html https://lua-api.factorio.com/latest/Libraries.html
- yxhuvud 5y ago
  That hash values get distributed differently inside the hash to avoid collision attacks is totally unrelated to what iteration order you get when you iterate elements in the hash. You can easily get predictable iteration order and have hash collisions that is not predictable. Look at Python, Ruby, PHP - they have defined iteration order to be insertion order. Javascript also have predictable order though the order is a bit more complex. Go is the outlier in that it defines it as guaranteed to be random. But both choices are just fine.
  - masklinn 5y ago
    > totally unrelated to what iteration order you get when you iterate elements in the hash That is a bit too strong am assertion: you can decorrelate the two when you build the collection, but the naive set up is very much that hash randomisation will randomise iteration order.