For what it's worth, the JS ecosystem has tried for years to get users to not rely on key iteration order. It was always unspecified but no matter what, users still expected them to iterate in insertion order.

V8 fought against it for years. Look at this bug horror show:

https://bugs.chromium.org/p/v8/issues/detail?id=164

I think Python is doing the right thing. The only reason to not provide a deterministic iteration order for unsorted maps is to give more room for optimizers. But it seems like there is a clean implementation that is faster while also iterating over keys in insertion order.

Sure, maybe someone will come up with an even better optimization in the future that would break this, but at some point, you have to say, "OK, what we have is good enough, and it gives users a more predictable system."

If you are going to declare insertion order is non-deterministic, you really should make it non-deterministic by doing something like shuffling it. Otherwise, users will just inadvertently rely on whatever deterministic-but-unspecified-order the current implementation happens to provide.