runtime: clear() is slow for maps with big capacity and small number of items

[valyala]

The issue

The following pattern is frequently used in order to avoid excess memory allocations by re-using the map:

func f() {
  m := make(map[string]int)

  for {
    addSomeItemsToMap(m)
    useMap(m)

    // clear the map for subsequent re-use
    clear(m)
  }
}

It has been appeared that clear(m) performance is proportional to the number of buckets in m. The number of buckets can grow significantly at addSomeItemsToMap(). After that the performance of clear(m) can slow down significantly (and forever), even if only a few items are added into the map on subsequent iterations.

See https://philpearl.github.io/post/map_clearing_and_size/ for more details.

The solution

Go runtime must be able to switch between the algorithm, which unconditionally clears all the buckets in m, and the algorithm, which clears only the buckets, which contain at least a single item, depending on the ratio between the number of items in the map and the number of buckets in it. This should improve performance of clear(m) in the pattern above when every iteration can store widely different number of items in m.

[gabyhelp]

Related Issues

• proposal: runtime: add way to clear and reuse a map's working storage #45328 (closed)
• runtime: clear() on map doesn't correctly clear existing iterators #59411 (closed)

_{(Emoji vote if this was helpful or unhelpful; more detailed feedback welcome in this discussion.)}

[randall77]

This is another case where I think map shrinking (#20135) is probably the right solution.
Or at least, it would help a lot, and maybe enough. And it helps lots of other cases.

[mknyszek]

Wouldn't shrinking the map partially defeat the original optimization though?

Not saying we shouldn't shrink maps, it's just the particular example OP gave seems like a trade-off between clear performance and map insert performance (because it forces map growths). It may also be that just shrinking maps is better overall.

[mknyszek]

As an additional note, I wonder if this is any better or worse with the Swiss map implementation in Go 1.24.

[thepudds]

FWIW, Keith commented on a related issue regarding clear performance for large maps for the new Swiss map implementation in #52157 (comment).

[thepudds]

Wouldn't shrinking the map partially defeat the original optimization though?

One approach could be that the backing storage would not shrink immediately. For example, there is this comment from Keith in #54454 (comment), including:

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.

(That is an older comment that predates the clear builtin I think, but presumably something similar could apply).

[prattmic]

In https://go.dev/cl/627156, I made swissmap iteration make use of the map metadata to skip runs of empty slots, which significantly speeds up iteration over large but sparse maps (-38% vs old maps).

The same idea could be applied to clear to address this issue. clear will still take longer on large maps, but the increase should be less extreme.