Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Closed
andig opened this issue Sep 9, 2020 · 15 comments
Closed

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

andig opened this issue Sep 9, 2020 · 15 comments

Comments

@andig
Copy link
Contributor

@andig andig commented Sep 9, 2020

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 #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.

@gopherbot gopherbot added this to the Proposal milestone Sep 9, 2020
@gopherbot gopherbot added the Proposal label Sep 9, 2020
@martisch martisch changed the title proposal: add native type for map that maintains key order proposal: Go2: add native type for map that maintains key order Sep 9, 2020
@martisch
Copy link
Contributor

@martisch martisch commented Sep 9, 2020

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!

@martisch martisch changed the title proposal: Go2: add native type for map that maintains key order proposal: Go 2: add native type for map that maintains key order Sep 9, 2020
@randall77
Copy link
Contributor

@randall77 randall77 commented Sep 9, 2020

Related #39291 #22865

@andig
Copy link
Contributor Author

@andig andig commented Sep 9, 2020

  • 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
Copy link
Contributor Author

@andig andig commented Sep 9, 2020

@gopherbot please remove label WaitingForInfo

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Sep 9, 2020

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
Copy link
Contributor Author

@andig andig commented Sep 10, 2020

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
Copy link
Contributor

@martisch martisch commented Sep 10, 2020

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
Copy link
Contributor Author

@andig andig commented Sep 10, 2020

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
Copy link
Contributor

@davecheney davecheney commented Sep 10, 2020

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
Copy link
Contributor

@randall77 randall77 commented Sep 10, 2020

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
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Sep 15, 2020

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
Copy link
Contributor Author

@andig andig commented Sep 16, 2020

@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
Copy link
Contributor

@randall77 randall77 commented Sep 16, 2020

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
Copy link

@DmitriyMV DmitriyMV commented Sep 16, 2020

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 map[key](value, pointer-to-key-in-list) 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
Copy link
Contributor Author

@andig andig commented Sep 18, 2020

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!

@randall77 randall77 closed this Sep 18, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
7 participants
You can’t perform that action at this time.