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

[riobard]

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)
}

[changkun]

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]

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]

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]

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

[ericlagergren]

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

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]

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]

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]

@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]

@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]

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

[riobard]

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

[ianlancetaylor]

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]

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]

No further comments.