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.