Go: proposal: Go 2: add native type for map that maintains key order

[andig]

Currently, Go maps are unordered, i.e. ranging over a map happens in unspecified order. There are several use cases that could profit from an ordered map type. Examples are https://github.com/golang/go/issues/27179, #27050, #6244, #24375.
An additional example is url.Values.Encode() which is a native map and sorts keys when encoding which makes it unusable with certain apis.

While it is possible to created custom ordered map types, initialisation is cumbersome and they are not used by core types like url.Values (e.g. https://github.com/mickep76/mapslice-json).

I'm proposing to either:
a) make the native map type maintain keys in order of initialisation or
b) add an ordered map type that maintains key order and use that map type in the standard library where applicable

Both approaches would break the compatibility promise as- in order to reap the benefit- additional changes to the standard library would be necessary.

[martisch]

For language change proposals, please fill out the template at https://go.googlesource.com/proposal/+/refs/heads/master/go2-language-changes.md .

When you are done, please reply to the issue with @gopherbot please remove label WaitingForInfo.

Thanks!

[randall77]

Related #39291 #22865

[andig]

• Would you consider yourself a novice, intermediate, or experienced Go programmer?
  intermediate
• What other languages do you have experience with?
  mostly PHP and JS
• Would this change make Go easier or harder to learn, and why?
  It would require to understand potentially two different map types but understanding the existing one is required anyway.
• Has this idea, or one like it, been proposed before?
  Different types of problems have been identified that could be solved by this approach.
• Who does this proposal help, and why?
  Provide a means to solve issues linked above by providing stdlib implementation.
• What is the proposed change?
  Make map ordered or add an ordered map type.
• Please describe as precisely as possible the change to the language.
  Please see above.
• What would change in the language spec?
  An additional type would not change the spec but would require stdlib changes for full effect.
• Please also describe the change informally, as in a class teaching Go.
  Please see above.
• Is this change backward compatible?
  Potentially. If the map implementation is changed it would be compatible (as range order is undefined) but might have runtime cost.
• Breaking the Go 1 compatibility guarantee is a large cost and requires a large benefit.
  This proposal targets Go 2.
• Show example code before and after the change.
  No difference.
• What is the cost of this proposal? (Every language change has a cost).
  Runtime cost or an additional type with accompanying stdlib changes (separate proposals required)
• How many tools (such as vet, gopls, gofmt, goimports, etc.) would be affected?
  Vet would be affected for follow-on stdlib proposals.
• What is the compile time cost?
  None
• What is the run time cost?
  Potentially memory+cpu.
• Is the goal of this change a performance improvement?
  No
• Is this about generics?
  No. Using generics would allow to mimic the the functionality but would not provide the ability of being able to using this as part of stdlib.

[andig]

@gopherbot please remove label WaitingForInfo

[ianlancetaylor]

It seems to me that the right approach here is to use generics if they are added to the language. For example, there is a simplistic possible implementation at https://go.googlesource.com/go/+/refs/heads/dev.go2go/src/cmd/go2go/testdata/go2path/src/orderedmap/orderedmap.go2 . If we do add generics to the language, I don't see any reason to also add an ordered map type.

[andig]

I agree this could be done using generics. The specific implementation pointed to above would not work though as it does not maintain order of initialisation and I couldn't think if a way to do this programmatically.

There are more disadvantages:

• the generics approach would also not be picked up by stdlib as changing the map implementation would
• initialisation of map elements would still be cumbersome and differs from "simple" maps

[martisch]

the generics approach would also not be picked up by stdlib as changing the map implementation would

Could you explain why not? I dont think the std lib is prohibited from using generics once the compiler supports them. Changing the stdlib API if a type is exposed would need to be done with generics and with a new map type and both times break backward compatibility.

[andig]

I don't think the std lib is prohibited from using generics once the compiler supports them.

I guess it wouldn't, but stdlib would need to chose the specific implementation that provides the behaviour described. Changing the default map implementation would give that for free wherever it is used today.

Is there a particular reason why the standard map implementation should retains its per-default indeterministic range behaviour?

[davecheney]

Is there a particular reason why the standard map implementation should retains its per-default indeterministic range behaviour?

Sorted maps are slower. Changing the default map type to be sorted would penalise everyone who does not need a sorted map implementation or has already written code to sort keys when required.

[randall77]

In addition, not all keys have orderable types. For example, in what order do interface{} keys go?
And for float64 (which is ordered), where does NaN go?

[ianlancetaylor]

Based on the discussion above, this is a likely decline. Perhaps if we do not accept generics into the language we can revisit this idea. Leaving open for four weeks for final comments.

[andig]

@randall77 I did not request a map with orderable ytpes. I did request a map than maintains given key order where order is order of initialization.

[randall77]

Ah, sorry, I misunderstood.
So how would you implement such a thing, then?
I could see a doubly-linked list used to keep track of the insertion ordering of the keys. Or an insertion order integer kept along with the key. Both seem pretty expensive.

[DmitriyMV]

Simple wrapper with combination double-linked list of keys (to preserve order of insertion) and map[key]value solves this problem quite well. You can even make mapkey so it would be actually cheap to delete elements. It's quite simple in implementation

With generics it may be reasonable to have some sort of pkg "collections" with this and others map included.

Currently I don't see any reason to have new builtin type or changing the semantics of existing.

[andig]

I understand this is gonna be declined. The downside with all "do it yourself" responses is that stdlib will not profit from such approaches. If you see the examples initially given (json.Encode, url.Values) they will maintain their unsorted or forced-sorted behaviour. But then I realise that this behaviour is even in parts specified (https://golang.org/pkg/net/url/#Values.Encode) so let's close this one.

Thank you for the insightful discussion!