Currently the maps package has no package dependencies. Presumably the implementation of this would at least require unsafe and possibly some hooks into runtime as well, right?

I think I'd rather fix #20135 and #19094, then we wouldn't need this.

I think I'd rather fix #20135 and #19094, then we wouldn't need this.

Definitely agree that directly fixing the underlying issues would be better, but it's also true that the issues have been opened for years, and there seem to be no consensus on how to proceed (or even whether we can proceed).

This proposal should be seen as an effective intermediate step, as it offers a clean way forward even if at a later date we actually fix #20135 and/or #19094.

Presumably the implementation of this would at least require unsafe and possibly some hooks into runtime as well, right?

I think the simplest way is to implement it in runtime, and just expose it via x/exp/maps. This would require a single method (AFAICT no hooks) to be exported via go:linkname from the runtime and into x/exp/maps (and you are correct, this would require importing unsafe in x/exp/maps).

and there seem to be no consensus on how to proceed (or even whether we can proceed).

Shrink-on-delete seems straightforward, we just need someone to implement it. Josh already checked in most of the mechanism needed for the tooManyOverflowBuckets change. "can" = yes, "how" = allocate a person to it.
Grow-on-read seems harder, but I don't see any obvious blockers. We'd need a design sketch first, I think, before "can" is certain. Once we have that, "how" is again people-limited.

Shrink-on-delete seems straightforward, we just need someone to implement it. Josh already checked in most of the mechanism needed for the tooManyOverflowBuckets change.

My interpretation of Josh's comment was the opposite, i.e. that the mechanisms needed for the tooManyOverflowBuckets were somewhat unlikely to help with #20135.

As an additional hurdle, mapclear currently does not change the bucket count. Would the fix for #20135 change this, even though #20138 explicitly argued against changing the bucket count?

And, while I haven't given this too much thought, I can imagine some tricky tradeoffs when dealing with how to deal with the case of a map that starts growing in the middle of a shrink operation.

On the topic of capacity, and intersecting with the previous point, what should the map do with a map with a high hint while it's growing? What if the hint was too large, and the map length never reaches anywhere close to that capacity hint?

Lastly, how do we plan to ensure that the fix for #20135 won't hurt workloads some people may care about, especially since there may be no available workaround for them?

All of this for the simpler case of shrink-on-delete¹; the case of grow-on-read is even fuzzier and may not be solved for quite a while (especially considering the potential performance implications).

Mind you, I am not saying these are insurmountable issues, or that this proposal is an actual alternative to solving them properly. I am just arguing that it has been 5+ years, and that maybe we shouldn't let perfect be the enemy of good (especially in case good won't hurt us in the future, as we would have an easy way to guarantee compatibility across versions).

I'm just advocating that we've long avoided adding API for situations where we could fix the issue without adding API. I understand that could lead to long delays in getting things implemented, but that's the tradeoff we have historically made. Top of mind recently, see #29951.

My interpretation of #20135 (comment) was the opposite, i.e. that the mechanisms needed for the tooManyOverflowBuckets were somewhat unlikely to help with #20135.

It is a good question. I remember when reviewing that change that it seemed applicable to me. Maybe Josh was seeing something I didn't.

As an additional hurdle, mapclear currently does not change the bucket count. Would the fix for #20135 change this, even though #20138 explicitly argued against changing the bucket count?

That is a good point. We probably don't want to shrink if people do the map clear idiom + reinsert a new set of stuff. Perhaps we only start shrinking after 2N operations, so that N delete + N add involves no shrinking. There's definitely a tradeoff here between responsiveness when you use fewer entries and extra work that needs to be done to regrow.

And, while I haven't given this too much thought, I can imagine some tricky tradeoffs when dealing with how to deal with the case of a map that starts growing in the middle of a shrink operation.

I suspect we could deal with this the way inserts work. When we grow from capacity N to 2N, we do enough work at each insert that the grow work is guaranteed to be done by the time the number of entries reaches 2N.
Similarly, when there are fewer than N/4 entries in an N-capacity map, we could shrink to capacity N/2. If we move at least 1 of the N/4 entries on each subsequent operation, then we're guaranteed we won't exceed our new N/2 capacity before the shrink is done. And if we move 2 entries per operation, and we could guarantee that the shrink is done before we'd want to shrink again (@ N/8 entries in our new N/2 capacity map).

On the topic of capacity, and intersecting with the previous point, what should the map do with a map with a high hint while it's growing? What if the hint was too large, and the map length never reaches anywhere close to that capacity hint?

I think this is a case of tuning a heuristic. We do at some point need to give up on the hint and start shrinking. (I guess the other option is to always respect the hint, but I think that overassumes accurate hints.)
We may need to remember the hint for a period of time. But maybe that's not necessary. Maybe as long as inserts, or (inserts-deletes), are happening at a sufficient positive rate, we don't shrink.

Lastly, how do we plan to ensure that the fix for #20135 won't hurt workloads some people may care about, especially since there may be no available workaround for them?

It's going to hurt someone, I'm not too hung up on that. Performance optimization is seldom a win-win. I'm looking for something as good or better than an 80% win / 20% lose.

It sounds like we believe this need can be addressed with better tuning, rather than adding new API. That would suggest we should decline this proposal. Do I have that right?

This proposal has been added to the active column of the proposals project
and will now be reviewed at the weekly proposal review meetings.
— rsc for the proposal review group

Based on the discussion above, this proposal seems like a likely decline.
— rsc for the proposal review group

No change in consensus, so declined.
— rsc for the proposal review group