proposal: runtime/map: fix map iteration order

[maurolacy]

Fix as in "keeping it fixed". As in, "not changing".

Random iteration order for maps is a serious drawback in some contexts. It would be desirable to have a hash map container that has unpredictable but fixed iteration order. Al least, in the same golang version, and between calls to the same underlying map.

Randomisation was introduced for performance reasons (see commit 55c458e0).

It would be good to have the option, by example during iteration, to define which behaviour we want: either the more performant but random, or the fixed order. And, given that iteration performance isn't necessarily the main concern for a hash map, perhaps the default iteration behaviour should be the fixed order one.

Also, it would be good to have a map impl that doesn't depend on randomisation to achieve better iteration performance. What about other map impls? Can / will run a benchmark in Rust and C++ (which AFAIK have fixed iteration order), to compare the iteration performance of their stock maps with that of Go.

Also, browsing through open issues, noticed that on 2022-03-01, in Go compiler and runtime meeting notes it was mentioned by austin that "our map is pretty old; at what point do we rewrite the map using the latest and greatest techniques?"

Comments?

[seankhliao]

Duplicate of #41289

[maurolacy]

Duplicate of #41289

This is not a duplicate of #41289. I'm not proposing a sorted order (for that I would use a different container), but a fixed one.

[maurolacy]

@seankhliao closing as not planned? If it's not planned, shouldn't you keep it open?

So that it can be eventually planned.

[seankhliao]

That issue also covers other fixed orders, eg insertion order. The decision is the same, use generics if you want a map with different guarantees.

[dominikh]

So that it can be eventually planned.

"Not planned" means "we won't do this."

[maurolacy]

So that it can be eventually planned.

"Not planned" means "we won't do this."

I could do it. Opening this issue for comments, as a first step.

[maurolacy]

A fixed iteration order is a pretty obvious guarantee to require for a map. Sorted order, no, and insertion order, neither. But fixed order, yes.

The fact that you as language designers and writers seem to think otherwise, pikes my curiosity.

[ianlancetaylor]

If your code relies on a specific map iteration order, then your code will break when the map implementation changes. This is not a theoretical problem: large code bases have found it very difficult to improve hash table implementations because changes in iteration order cause many tests to fail. Each of those tests has to be manually adjusted to work with the new hash table implementation.

Go side steps that problem by changing the iteration order each time. That prevents people from writing tests that implicitly rely on the map implementation, making it easy for Go to change that implementation.

[maurolacy]

The way to deal with that is through code base stabilisation, in my opinion. How many times the hash table implementation changed in a way that impacted the iteration order, in the last ten years or so?

I prefer tests to fail because iteration order changes from time to time (or even, across different CPU archs), than being unable to keep a fixed iteration order, even between different runs over the same map.

Side stepping the iteration order problem by making the order random is exactly that: a side step. It introduces more problems than it is supposed to solve.

[ianlancetaylor]

Thanks, but we disagree. This is not something we are going to change at this point in the language's development.