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: builtin: delete should return the deleted map item #51405

Closed
riobard opened this issue Mar 1, 2022 · 15 comments
Closed

proposal: Go 2: builtin: delete should return the deleted map item #51405

riobard opened this issue Mar 1, 2022 · 15 comments
Labels
LanguageChange Proposal Proposal-FinalCommentPeriod v2 A language change or incompatible library change
Milestone

Comments

@riobard
Copy link

riobard commented Mar 1, 2022

Currently the builtin delete function has the signature

func delete(m map[Type]Type1, key Type)

A common usage pattern is to get an item from a map and then remove it after processing:

doSomethingWith(m[k])
delete(m, k)

which involves hashing k and locating it in m twice.

If delete is changed to

func delete(m map[Type]Type1, key Type) Type1

then getting an item and removing it from a map can be done in one step:

doSomethingWith(delete(m, k))

This is similar to Python's dict.pop(key) method. The proposal changes the builtin function's API but I don't think it would break any existing code, so Go1 compatibility should not be an obstacle.

Additionally, as suggested below by @ydnar, delete could be further enhanced with comma-ok pattern:

v, ok := delete(m, k)
if ok {
    doSomethingWith(v)
}
@gopherbot gopherbot added this to the Proposal milestone Mar 1, 2022
@changkun changkun changed the title proposal: builtin/delete should return the deleted map item proposal: builtin: delete should return the deleted map item Mar 1, 2022
@changkun
Copy link
Member

changkun commented Mar 1, 2022

What happens if k is not in m? Should it return nil an expected behavior? or zero value?
According to the signature, it seems to suggest return zero value in this case. Either way, we cannot differentiate the key is not present in the map or stored a nil/zero value inside the map.

A common usage pattern is to get an item from a map and then remove it [...] in one step:

Could you show how common it is statistically? One single pattern may not be strong enough to support the change.

There was a similar discussion regarding delete in #41130.

@ydnar
Copy link

ydnar commented Mar 1, 2022

What happens if k is not in m? Should it return nil an expected behavior? or zero value? According to the signature, it seems to suggest return zero value in this case. Either way, we cannot differentiate the key is not present in the map or stored a nil/zero value inside the map.

Optional comma-ok like a map read?

v, ok := delete(m, k)

@riobard
Copy link
Author

riobard commented Mar 1, 2022

If k is not in m it should return the zero value of item type, same as v := m[k] would sanely behave. Many common types in Go have useful zero values. Additionally, in the proposed use case there's no ambiguity because k must exist in m for it to be range over.

I don't have useful numbers right now, but this pattern often appears in cleanup routine in order to re-use a map.

#41130 was obviously flawed so not worth further discussion. #5147 could be an alternative but it's not looking very promising.

@riobard
Copy link
Author

riobard commented Mar 1, 2022

@ydnar's proposal is also nice so it's similar to map access.

@ianlancetaylor ianlancetaylor added v2 A language change or incompatible library change LanguageChange labels Mar 1, 2022
@ianlancetaylor ianlancetaylor changed the title proposal: builtin: delete should return the deleted map item proposal: Go 2: builtin: delete should return the deleted map item Mar 1, 2022
@ericlagergren
Copy link
Contributor

ericlagergren commented Mar 2, 2022

#41130 was obviously flawed

The author's usage of map was flawed, but the conclusion to reject the proposal wasn't. See Ian's comment: #41130 (comment)

@ianlancetaylor
Copy link
Contributor

ianlancetaylor commented Mar 2, 2022

For a case like

for k := range m {
	doSomethingWith(m[k])
	delete(m, k)
}

you could instead write

for k, v := range m {
	doSomethingWith(v)
}
m = nil

So while the idea makes sense the example is not wholly convincing.

If the main concern is the double hashing, then perhaps the compiler can detect this kind of pattern. It does already detect some map range patterns. See also #5147.

@riobard
Copy link
Author

riobard commented Mar 5, 2022

Double hashing is indeed the primary concern, but it is not as clean/efficient, as explained in #5147 (comment) by @bradfitz:

The downside is that the subsequent map operations would still need to do == on all entry values hashed to the same bucket, but at least the hash operation itself would only be done once.

I agree the original example isn't ideal. There're common cases where you don't clear the whole map, e.g.

for k := range m {
	if someConditionMatches(k) {
		doSomethingWith(m[k])
		delete(m, k) // double hashing & bucket lookup
	}
}

vs

for k := range m {
	if someConditionMatches(k) {
		doSomethingWith(delete(m, k)) // single hashing & bucket lookup
	}
}

@jimmyfrasche
Copy link
Member

jimmyfrasche commented Mar 5, 2022

I get that you can use faster code if delete doesn't return anything but I don't get why that's relevant here.

The compiler knows whether the returns are used so couldn't it emit the slow delete code when they are used and the fast delete code when they are not? Like:

delete(m, k) // -> fastDelete(m, k)
v, ok := delete(m, k) // -> v, ok := slowDelete(m, k)

That could mean having two delete algorithms but the first version of slowDelete could just be the equivalent of

func slowDelete[M ~map[K]V, K comparable, V any](m M, k K) (V, bool) {
  v, ok := m[k]
  delete(m, k)
  return v, ok
}

Any improvements above that would be an optimization.

As just demonstrated, with generics, it's easy to write your own delete that returns, though. It's possible that more general optimizations could make that just as fast as if the builtin directly supported this operation.

At that point the major win for the builtin is that it could be called with 0, 1, or 2 returns instead of 0 or 2 returns. But you could of course write 3 variants of the generic delete to cover (V, bool), V, and bool returns.

So extending the builtin with a comma-ok return would make it more convenient and probably simpler to optimize in the short term. Is that worth it? I don't know. Maybe it would suffice to add a function or two to the maps package.

@ianlancetaylor
Copy link
Contributor

ianlancetaylor commented Mar 5, 2022

@riobard The first example in #51405 (comment) isn't all that convincing because it would normally be written as

for k, v := range m {
	if someConditionMatches(k) {
		doSomethingWith(v)
		delete(m, k) // double hashing & bucket lookup
	}
}

which does not require double hashing.

@riobard
Copy link
Author

riobard commented Mar 6, 2022

@ianlancetaylor Ah stupid me! I completely forgot about the optional value from range. 😅

I guess then the returning-value delete is useful only in cases where you directly access the map, not iterating over it.

@riobard
Copy link
Author

riobard commented Mar 6, 2022

@jimmyfrasche Is the current delete faster than one that returns value?

@riobard
Copy link
Author

riobard commented Mar 7, 2022

I've updated the proposal based on the discussion so far for clarity.

@ianlancetaylor
Copy link
Contributor

ianlancetaylor commented Apr 6, 2022

We think we should explore compiler optimizations to avoid the double hashing, and only reach for a language change if that seems impossible. It's true that the map data structure has some optimizations for small maps, but those can in principle be replicated by the compiler's internal ABI as well.

It's also unclear how often this case arises. For example, would any code in the standard library be better/easier to read if we had this facility?

@ianlancetaylor
Copy link
Contributor

ianlancetaylor commented May 4, 2022

Based on the discussion above this is a likely decline in favor of looking into compiler optimizations.

Leaving open for four weeks for final comments.

@ianlancetaylor
Copy link
Contributor

ianlancetaylor commented Jun 8, 2022

No further comments.

@ianlancetaylor ianlancetaylor closed this as not planned Won't fix, can't repro, duplicate, stale Jun 8, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
LanguageChange Proposal Proposal-FinalCommentPeriod v2 A language change or incompatible library change
Projects
None yet
Development

No branches or pull requests

7 participants