Repository navigation
irverify+pass: reusedMap's bound misses entries a collection deleted #1152
Description
Problem
reusedMap.emptied, kept alike in ir/irverify/reuse.go and pass/reuse.go, replaces its map when the last collection left it more than reuseLimit entries and clears it in place otherwise. It reads len, what the collection left, while what clearing costs follows the most the map ever held: Go grows a map's tables and never shrinks them, on delete as on clear. A collection that inserts many entries and deletes them leaves a short map, which is cleared in place, and every later collection pays for the size it reached.
reuseLimit's comment calls it "how many entries a reusedMap may have held for it to be emptied in place", which holds only while no collection deletes. Neither package deletes today, so no check is unbounded now; a later one that does would lose the bound with every test green, since TestReusedMap_EmptiesInPlaceUpToTheLimit fills the map and never deletes.
Through reusedMap itself, in an internal test of ir/irverify: fill the map emptied hands back with 1,000,000 entries, delete them all, and emptied hands back the same map, cleared in place. Ten thousand rounds of emptied and one insert then take 33.5 ms, against 0.23 ms on a fresh reusedMap.
The same cost without the type, inserting one entry and clearing after the map grew to n entries and had every one deleted, so len reads 0:
BenchmarkClearAfterDeletedHuge/8-12 15.90 ns/op
BenchmarkClearAfterDeletedHuge/1000000-12 3535 ns/op
func BenchmarkClearAfterDeletedHuge(b *testing.B) {
for _, n := range []int{8, 1_000_000} {
b.Run(strconv.Itoa(n), func(b *testing.B) {
m := map[string]int{}
for i := range n {
m[strconv.Itoa(i)] = i
}
for i := range n {
delete(m, strconv.Itoa(i))
}
for b.Loop() {
m["a"] = 1
clear(m)
}
})
}
}Direction
A proposal: state the precondition where a caller reads it, in the comments on reusedMap, emptied and reuseLimit in both packages (a collection must not delete from the map, since emptied reads the length it leaves), and hold it beside the clear test: each package's TestReusedMaps_AreEmptiedThroughReusedMapAlone could also require FuncsUsing(types.Universe.Lookup("delete")) to be empty, which both packages satisfy today.
The alternative weighed is a type that counts what a collection inserts, through a method beside emptied, so the bound follows the most a collection held whatever it deletes. It routes every insert through the type, for callers none of which deletes.
Out of scope
- The bound's value, and whether the two packages should share one type.
Priority: P4, rule 1 (housekeeping: a comment and a test, changing no lowering, validation, IR or emit-contract behaviour, since no caller deletes). decls.Load(...).FuncsUsing(types.Universe.Lookup("delete")) → empty in ir/irverify and pass; the benchmark above → 16 ns after 8 deleted entries, 3,535 ns after 1,000,000 (go1.27.2, morphic @82908fb8).
Activity
OmarAlJarrah commentedon Oct 29, 2026
The same gap reaches a reused map emptied by deleting each key rather than by
clear. At morphic @82908fb8,listedincheckRequireswas planted as a plain map emptied for each model withfor k := range listed { delete(listed, k) }. BothTestReusedMap_EmptiesInPlaceUpToTheLimitandTestReusedMaps_AreEmptiedThroughReusedMapAlonestay green, since the second looks only for theclearbuiltin.That form also costs more than
clearafter one huge collection. In the benchmark below the compiler kept the loop: the binary callsmapIterStart,mapIterNextandmapdelete_faststrfor it, andmapclearonly for the setupclear. Each round therefore iterates a map sized for every entry it once held. Median of three runs (go1.27.2, darwin/arm64):No production code empties a map this way:
git grep -n -P -A1 'for (\w+) := range (\S+) \{$' -- '*.go' ':!*_test.go' ':!**/testdata/**' | grep -P 'delete\('prints nothing at @82908fb8. The Direction's check, refusingdeletein both packages, closes this form too.[-]irverify+pass: reusedMap bounds no collection that deletes from it[/-][+]irverify+pass: reusedMap's bound misses entries a collection deleted[/+]OmarAlJarrah commentedon Oct 29, 2026
One more sentence for the comments this issue rewrites.
reuseLimit's comment inir/irverify/reuse.goandpass/reuse.gosays "Emptying a map costs in proportion to the most it has ever held", and that holds only for large maps. Inserting one entry and clearing, after the map once held n entries, median of three (go1.27.2, darwin/arm64, morphic @82908fb8):Quadrupling n from 1,024 costs 1.16 times as much; from 1,048,576, 4.3 times. Clearing a non-empty map clears the tables that hold entries and walks the directory, and the walk dominates only once the map is large. "Costs more the more it has ever held" is what holds, and the skill rule
clear-never-shrinksin #1153 says it that way. The doc comments ofTestReusedMap_EmptiesInPlaceUpToTheLimitspeak of "a huge collection", where the cost does track the peak, so they can stand.chore(skills): name the delete-loop gap in the reused-map rule
OmarAlJarrah commentedon Oct 29, 2026
A correction to the delete-loop comment above: its cost holds only where the compiler keeps the loop, which an ordinary build does not.
cmd/compilerewritesfor k := range m { delete(m, k) }into the runtime's map clear (isMapClearincmd/compile/internal/walk/range.go, go1.27.2) unless optimizations are off or the build instruments, as-racedoes.runtime.mapclearunder a plaingo build, and tomapIterStart,mapIterNextandmapdelete_faststrundergo build -race(-gcflags=-S).for i := 0; i < b.N; i++body compiles toruntime.mapclear, and in afor b.Loop()body keepsmapIterNext(go tool objdumpof the test binary), so theb.Loopbody is what kept it in the benchmark above.So in production the form costs what
clearcosts, still unbounded after one huge collection, and more in the gate's race build. The source test misses it either way, so the Direction's check ondeletestands.