runtime: allocate no-escape map buckets to the stack more aggressively

[fredbi]

Context

Whenever a map is created and identified as not escaping the called function,
I observe that the first bucket (8 entries) comes literally for free on the stack.

However, when the map is grown to a higher number of buckets (e.g. make(map[int]string,9) or grown dynamically),
the next buckets are allocated on the heap, then garbage-collected.

This makes a huge difference for relatively small maps, but not as small as the tiny 8 slots.

The same occurs, whether the map size is known or not known at compile time, yet correctly detected as not escaping the function.

Proposal

I suggest allocating buckets of unescaped maps to the stack more aggressively and only resorting to the heap
when the stack is getting close to its max.

The criterion to switch from stack to heap should be determined at runtime and could be either when the stack is maxed out (super aggressive) or merely when allocating the new bucket would require a new stack segment (super conservative).

In either case, I believe this improvement would largely speed up the dozens of small map-based utility functions that we use routinely (see an example below).

Example

In the 3 simplistic examples below (all inspired by real-life utilities, such as "deduplicate an input slice", but much simplified here...), the compiler correctly identifies the map as not escaping the func.

In all examples, if the input size (variable or const) is <= 8, no allocation on the heap takes place (the first bucket comes for free).
In all examples, if an extra bucket is needed, either by calling make with a hint or by growing the map, it is always allocated on the heap.

const ok = "ok"

// dynamic allocation, up to a capacity not known at build time
func mapAllocString(n int) int {
	index := make(map[int]string) // does not escape: ok

	for i := 0; i < n; i++ { // if n>8, dynamic allocation of new buckets occurs on the heap
		index[i] = ok
	}

	return len(index)
}

// pre-allocation with hint, up to a capacity not known at build time
func mapAllocMakeString(n int) int {
	index := make(map[int]string, n) // does not escape: ok if n>8, pre-allocation of new buckets occurs on the heap

	for i := 0; i < n; i++ {
		index[i] = ok
	}

	return len(index)
}

// pre-allocation with hint, up to a capacity known at build time
func mapAllocMakeConstString(_ int) int {
	const size = 32

	index := make(map[int]string, 32) // does not escape: ok if size>8, pre-allocation of new buckets occurs on the heap

	for i := 0; i < size; i++ {
		index[i] = ok
	}

	return len(index)
}

[fredbi]

Relates to #37757

[randall77]

Same as #58215, stack frames are fixed size so allocating dynamic things on the stack is hard.

Taking out of the proposal process, as this is just an optimization.

[mknyszek]

What @randall77 said, and also stacks aren't segmented. They're contiguous but when there's not enough space for the next (fixed-sized) frame they're reallocated and their contents are copied. (Stacks aren't segmented because you get some pretty bad performance cliffs if you make an unrelated change and a hot leaf function ends up crossing segments.)

[fredbi]

@randall77 thanks for your feedback.
This issue is indeed very similar to the one I reported #58215 (I just wanted to separate maps and slices).
There is a slight difference with slices in how the escape analysis reports the case for "make" with a capacity known at runtime. It reports "no escape" for maps but "escape" for slices.