maps: remove Keys and Values for Go 1.21

[rsc]

Given #61405 and the likelihood of additional operations on those kinds of iterator functions (like Map, Filter, and Reduce), it seems possible that we would want Keys and Values to return iterator functions that can be used with those and do not provoke O(N) storage. I imagine there would also be a slices.Collect that collects values from any iterator into a slice, so existing uses of maps.Keys(m) that still want a slice would become slices.Collect(maps.Keys(m)).

If there's a good chance we're going to want Keys and Values to return iterators in Go 1.22, it seems short-sighted to ship them in Go 1.21 returning slices. I wonder whether we should pull them. It is late in the cycle, but not too late. git grep says there are no mentions of maps.Keys or maps.Values in the standard library.

[zephyrtronium]

I'm not clear on the value of using iterators for those methods rather than the normal range loops that exist today. We don't have map, filter, or reduce that work on iterators. Whatever package provides them can also trivially provide a function to adapt any rangeable value to an iterator.

[jimmyfrasche]

s/Slices/Values/g?

[DmitriyMV]

We have relevant experience with something like maps.Keys and its rather unpleasant one, because most of the time you don't need all keys: you likely don't need 90% of them, since the result of maps.Keys in most cases is going into something like slices.Filter with very specific filter pattern.

And the reason it's unpleasant is because you never know how many keys are in the map now - each time there is chance of unbounded memory growth, that could not happened during original code review, but things had changed since then and now instead of 10 keys you constantly filtering from 10000 keys.

But thats our experience anyway.

[changkun]

Instead of slices.Collect(maps.Keys(m)), what if we keep maps.Keys but do something like slices.Collect(maps.KeyIter(m)). This would make the signature reads more clear that Keys returns an slice, but KeyIter returns an iterator?

[rsc]

@jimmyfrasche Yes thank you. Changed Keys and Slices -> Keys and Values.

@zephyrtronium

I'm not clear on the value of using iterators for those methods rather than the normal range loops that exist today. We don't have map, filter, or reduce that work on iterators. Whatever package provides them can also trivially provide a function to adapt any rangeable value to an iterator.

That's true, but if the rangeable value is the current maps.Keys(m), then Keys builds the entire slice in memory even if you only just want to iterate through the keys and look at them. That's O(N) space that could be O(1) space instead, a large and potentially important difference for big maps. I don't think we should lock ourselves into the O(N) iteration strategy for map keys and map values.

@DmitriyMV: Yes, exactly, that's the situation I am concerned about. If Keys returned an iterator instead of a []K, you wouldn't have the memory or latency hit of collecting all the keys. You might still have the latency of filtering if you are going to go through all of them, but you avoid the memory hit with a filtered iterator. And if you stop early, you avoid the latency hit too.

@changkun Yes, if we keep Keys and Values as they are we will have to introduce some other iterator form for efficiency, maybe called KeysIter and ValuesIter. But I suspect most uses for Keys and Values work better with the iterator form (which would fix @DmitriyMV's example), meaning we should save the good names Keys and Values for them instead of giving them second-rate names.

[changkun]

instead of giving them second-rate names

Why is the Iter suffix a second-rate name? Values vs ValuesIter Comparably we already have artifact pairs like Handler vs HandlerFunc etc.

[zephyrtronium]

That's true, but if the rangeable value is the current maps.Keys(m), then Keys builds the entire slice in memory even if you only just want to iterate through the keys and look at them. That's O(N) space that could be O(1) space instead, a large and potentially important difference for big maps. I don't think we should lock ourselves into the O(N) iteration strategy for map keys and map values.

I don't see how we would be "locked into" an O(n) space iteration strategy for map keys or values. If I want O(1) space iteration over the keys of a map m, I write for k := range m. I don't see why I would ever use maps.Keys for that. When I use maps.Keys, it is to build a list of all the keys, usually followed by sorting the list. That is the most common purpose for which I use package maps, even. I didn't realize that is unusual.

Of course, I could still do this with a slices.Collect that accepts an iterator. And if that doesn't happen, maps.Keys and maps.Values can of course be added later. It just seems unfortunate to me to revise an already accepted proposal to remove the feature I use most frequently from its experimental version because of a language change that might happen and that might be followed by an API addition that can't even be proposed until that language change is decided.

[zephyrtronium]

meaning we should save the good names Keys and Values for them instead of giving them second-rate names.

Another way to provide a "first-class" name for composable map iterators would be to introduce a package iter which might have iter.Map, iter.Keys, iter.Collect, &c. maps.Keys isn't the only option.

[AndrewHarrisSPU]

More general formulations of algorithms might want to parameterize on something like type Pair[K comparable, V any] struct{Key K, Value V}, to preserve the key:value association. Also, there might be a type OrderedValue[V any] Pair[int, V] for slices and OrderedPair[K comparable, V any] OrderedValue[Pair[K,V]] for ordered map elements.

I'm quickly unsure if or when this is "bad idea" territory, but it's probably not in some languages - it's just that I definitely agree about not getting locked in.

[PaluMacil]

@rsc I think we can flip this backwards: instead of talking about leaving the preferred name for iterators, think about how not using a suffix will cause confusion in the rest of the standard library. There are things all over that return slices, and with iterators, it could be valuable to add methods and functions that return them. This won't be the only place, so while we can use a suffix and have the new iterators be consistent, we cannot have the other way. Be consistent. Also, "ThingIter" sounds like a name of a thing iterator and "Things" sounds like I already have those things allocated.

[rsc]

Pretty much everything in the standard library that returns a slice today should return an iterator in a future version. Adding "Iter" suffixes may be OK given the history but it's not where we want to end up. A v2 of those packages might flip the default. Or maybe there are good names available that don't use Iter. Either way, maps and slices are brand new packages. We don't want to go straight to a v2 just to fix this detail. We can avoid making the mistake to begin with if we just leave them out for this release and give ourselves another cycle to get it right. Maybe we'll end up back where we are today, but maybe not. I suspect not.

[PaluMacil]

I don't think it's entirely a mistake though. There are choices all over where we use slices as a return instead of some sort of iterator and have performance that is just fine. Anything that isn't CPU bound won't have a noticeable improvement either way.

However, at any given time, most software developers are fairly junior and the concept of an iterator is more difficult than the concept of a slice. Python has had generators and iterators for quite some time, but most of the time you see people using lists. It's totally unnecessary, but outside shared libraries, it rarely causes a difference. I don't think you'll stop seeing slices used a lot more often than iterators even if we one day have a Go 2 where they are the more common option.

That said, I personally haven't seen much indication that we would ever get to a point where such a big break would be worth it, so using words that are less specific in hopes that you can standardize on that eventually doesn't seem particularly helpful

[blackgreen100]

I think iterators shouldn't be the default choice, in general. They should be something the programmer consciously opts in to when needed. It simply follows the principle of least surprise. It is intuitive and unsurprising that maps.Keys and maps.Values return slices, just as the names imply. I strongly agree with @zephyrtronium 's comment above:

If I want O(1) space iteration over the keys of a map m, I write for k := range m. I don't see why I would ever use maps.Keys for that.

PS: the title of this issue should be updated too: "remove Keys and Slices" -> "remove Keys and Values"

[doggedOwl]

I think iterators shouldn't be the default choice, in general. They should be something the programmer consciously opts in to when needed.

Normally you would want the most costly and specific option to be consciously opted in and clearly returning a slice is more costly than returning an Iterator. having the full slice of elements upfront is usefull only when you are sure that you would need all of them and can justify the memory used. The more generic case is that you would need only some of the values and/or potentially exit early from the loop making Iterators better suited for the default choice.

You can collect the elements of the iterator in a slice if it's needed but while you still can create an iterator that loops over the slice, the "damage" of the memory use is already done and creating an iterator at that point is almost useless.

[earthboundkid]

But I suspect most uses for Keys and Values work better with the iterator form

I don’t suspect that. Python 3 changed from returning a list to returning an iterator, and it was often a pain because I needed to wrap the keys method in a list conversion. For maps.Keys today, my most frequent operation is to take the keys and sort them, which requires it being a slice. I think there should be an easy to use slice function. If it’s called KeySlice instead of Keys, that’s fine, but it is so frequently used it really is a pain to have to add a collect step in.

[jimmyfrasche]

If you need sorted map keys maybe you need a sorted map instead? Even without such a thing, if you need to collect the keys in a slice once it's not a lot of code (with or without stdlib changes) and if you need it more than once you can throw that in a function.

[earthboundkid]

if you need it more than once you can throw that in a function.

And that function could be in the standard library. ;-)

[jimmyfrasche]

I'm not opposed to functions that collects the keys/values in a slice, but I agree with @rsc that is less general than the iterator form and hence the short name should go to the iter form. For the specific use case you bring up, I wonder if a more generally useful way to expose that would be a sorting func that takes an iterator as input and returns a slice.

[earthboundkid]

I agree that this is a release blocker and should be resolved definitively before 1.21 releases, but I also think this is a bit of retreading previous decisions. Iterators were discussed as part of the planning for the maps package. In #47330 (reply in thread) @ianlancetaylor wrote,

A normal map iterator will be over key/value pairs. I don't think that an iterator over just keys or just values will be the common case. While I can imagine adding them (if we ever have iterators), I don't think we need to reserve better names for them.

Did something change to make us rethink that?

[gazerro]

Reading the keys of a map to obtain a sorted slice of keys is a use case that I have encountered several times. Without the slices and maps package, I would have written

i := 0
s := make([]T, len(m))
for k := range m {
	s[i] = k
	i++
}
sort.Slice(s, func(i, j int) { return s[i] < s[j] })

With the slices and maps packages, you can write

s := maps.Keys(m)
slices.Sort(s)

but with the change of this proposal I suggest introducing a slices.Sorted function

s := slices.Sorted(maps.Keys(m))

declared as

Sorted[T comparable](iter func(func(T) bool) bool) []T

This would be a good improvement, using only the standard library, compared to the current situation.

[heschi]

A process comment: we say to people that they should write code against release candidates and deploy them to production. At this point these functions have been in RCs for about a month, and I think it's plausible that people have uses functions in their codebase that will break when they update from the last RC to the final release. Are we concerned about the risk of breakage?

[cuiweixie]

The current version of maps.Keys is impl by me. I think https://go-review.googlesource.com/c/go/+/481435 and https://go-review.googlesource.com/c/go/+/481436. I do not know the detail impl of iters. but I think the current version of maps.Keys/Values could be faster that the Iter version. I think performance is also an important consideration.

[eihigh]

As many have already mentioned, the main use of maps.Keys is for sorting.

GitHub Code search results

In this case, what we need is not an iterator, but a slice to be sorted.
(The method proposed by @gazerro does not allow us to make([]T, len(m)) before sorting, which would be inefficient.)

[ianlancetaylor]

CL 513715 is landed.

[zxysilent]

Common cases named map.Keys, maps.Values

for Iter named maps.KeyAll ,maps.ValueAll

[dablelv]

That's true, but if the rangeable value is the current maps.Keys(m), then Keys builds the entire slice in memory even if you only just want to iterate through the keys and look at them. That's O(N) space that could be O(1) space instead, a large and potentially important difference for big maps. I don't think we should lock ourselves into the O(N) iteration strategy for map keys and map values.

I don't see how we would be "locked into" an O(n) space iteration strategy for map keys or values. If I want O(1) space iteration over the keys of a map m, I write for k := range m. I don't see why I would ever use maps.Keys for that. When I use maps.Keys, it is to build a list of all the keys, usually followed by sorting the list. That is the most common purpose for which I use package maps, even. I didn't realize that is unusual.

Of course, I could still do this with a slices.Collect that accepts an iterator. And if that doesn't happen, maps.Keys and maps.Values can of course be added later. It just seems unfortunate to me to revise an already accepted proposal to remove the feature I use most frequently from its experimental version because of a language change that might happen and that might be followed by an API addition that can't even be proposed until that language change is decided.

Can't agree more, please add maps.Keys and maps.Values back to the standard library.

[earthboundkid]

This issue is closed. See #61900 for the proposal to bring back maps.Keys and maps.Values as iterators.