The other option is to consider non-determinism a bug and to fix it where possible. For instance, several language runtimes (JS, Python) now use dictionary collections that are enumerated in insertion order, removing a long standing source of non-deterministic behaviour.
This happened only after the discovery that for languages like Python, guaranteeing insertion order iteration is virtually free. As I understand how to do that wasn't widely known in, say, 2010, and how to do that for C++/Rust/etc is still unknown.
It's not so much that it's free, as that what they were doing before to implement an unordered dict was so terrible that by comparison a reasonable design for an ordered dict is cheaper, so, why not? The options were:
* Existing design: Unordered behaviour confuses new programmers, Slow, Wastes space
* OrderedDict: New programmers aren't tripped up. Faster, smaller.
* Hypothetical UnorderedDict: Confuses new programmers again. Maybe even faster, if anybody builds it, which no-one volunteered to do.
Choosing OrderedDict was a no brainer for a language like Python.
You can't beat say Swiss Tables (a modern C++ unordered map with excellent performance) with the approach taken in OrderedDict not because we just don't know some optimisation, but because Swiss Tables is doing something a lot faster than what Python does today.
Swiss Tables is SIMD. In a single CPU instruction it can examine an entire cacheline of RAM to see if it matches your key (suggesting your value is probably in one of those slots) and in the process identify cases where any slots are empty and yet your key matched nothing, meaning it can stop looking because your key wasn't in this map at all.
This requires a very low-level understanding of how the CPU and RAM hierarchy works, and also knowledge of how to use SIMD instructions to get right, but that's fine the Swiss Tables team had those things and needed that performance. To make it fly though, you can't preserve order, the information needed isn't stored anywhere and storing it would make it slower and bigger.
