cmd/compile: escape: induction through map values

[adonovan]

It's common to create maps that have stack-like lifetimes. Though the compiler avoids heap allocation for the map itself, the values of the map are pessimistically assumed to escape. I wonder how hard it would be be to compute escape inductively through the map; I suspect it would eliminate a lot of allocations.

For example:

func g() {
	m := make(map[string]*int)
	m["a"] = new(int)
	m["b"] = new(int)
}

foo.g STEXT size=320 args=0x0 locals=0x138 funcid=0x0 align=0x0
...
// stack-allocate a new map
	0x0020 00032 	MOVD	$foo..autotmp_2-48(SP), R0
	0x0024 00036 	STP	(ZR, ZR), (R0)
	0x0028 00040 	STP	(ZR, ZR), 16(R0)
	0x002c 00044 	STP	(ZR, ZR), 32(R0)
	0x0030 00048 	MOVD	$foo..autotmp_3-248(SP), R0
	0x0034 00052 	MOVD	$3, R1
	0x0038 00056 	STP.P	(ZR, ZR), 16(R0)
	0x003c 00060 	STP.P	(ZR, ZR), 16(R0)
	0x0040 00064 	STP.P	(ZR, ZR), 16(R0)
	0x0044 00068 	STP.P	(ZR, ZR), 16(R0)
	0x0048 00072 	SUB	$1, R1
	0x004c 00076 	CBNZ	R1, 56
	0x0050 00080 	MOVD	ZR, (R0)
	0x0054 00084 	MOVD	$-9187201950435737472, R0
	0x0058 00088 	MOVD	R0, foo..autotmp_3-248(SP)
	0x005c 00092 	MOVD	$foo..autotmp_3-248(SP), R0
	0x0060 00096 	MOVD	R0, foo..autotmp_2-32(SP)
	0x0064 00100 	PCDATA	$1, $1
	0x0064 00100 	CALL	runtime.rand(SB)

// insert one entry
	0x0068 00104 	MOVD	R0, foo..autotmp_2-40(SP)
	0x006c 00108 	MOVD	$8, R0
	0x0070 00112 	MOVD	$type:int(SB), R1
	0x0078 00120 	MOVD	$1, R2
	0x007c 00124 	CALL	runtime.mallocTiny8(SB)                  // heap allocated int
	0x0080 00128 	MOVD	R0, foo..autotmp_9-256(SP)
	0x0084 00132 	MOVD	$type:map[string]*int(SB), R0
	0x008c 00140 	MOVD	$foo..autotmp_2-48(SP), R1
	0x0090 00144 	MOVD	$go:string."a"(SB), R2
	0x0098 00152 	MOVD	$1, R3
	0x009c 00156 	PCDATA	$1, $2
	0x009c 00156 	CALL	runtime.mapassign_faststr(SB)
	0x00a0 00160 	PCDATA	$0, $-3
	0x00a0 00160 	MOVWU	runtime.writeBarrier(SB), R1
	0x00a8 00168 	PCDATA	$0, $-1
	0x00a8 00168 	PCDATA	$0, $-2
	0x00a8 00168 	CBNZW	R1, 180
	0x00ac 00172 	MOVD	foo..autotmp_9-256(SP), R4
	0x00b0 00176 	JMP	196
	0x00b4 00180 	MOVD	(R0), R3
	0x00b8 00184 	CALL	runtime.gcWriteBarrier2(SB)
	0x00bc 00188 	MOVD	foo..autotmp_9-256(SP), R4
	0x00c0 00192 	STP	(R4, R3), (R25)
	0x00c4 00196 	MOVD	R4, (R0)
	0x00c8 00200 	PCDATA	$0, $-1
	
// and another
	0x00c8 00200 	MOVD	$8, R0
	0x00cc 00204 	MOVD	$type:int(SB), R1
	0x00d4 00212 	MOVD	$1, R2
	0x00d8 00216 	PCDATA	$1, $1
	0x00d8 00216 	CALL	runtime.mallocTiny8(SB)               // heap allocated int
	0x00dc 00220 	MOVD	R0, foo..autotmp_9-256(SP)
	0x00e0 00224 	MOVD	$type:map[string]*int(SB), R0
	0x00e8 00232 	MOVD	$foo..autotmp_2-48(SP), R1
	0x00ec 00236 	MOVD	$go:string."b"(SB), R2
	0x00f4 00244 	MOVD	$1, R3
	0x00f8 00248 	PCDATA	$1, $3
	0x00f8 00248 	CALL	runtime.mapassign_faststr(SB)
	0x00fc 00252 	PCDATA	$0, $-4
	0x00fc 00252 	MOVWU	runtime.writeBarrier(SB), R3
	0x0104 00260 	PCDATA	$0, $-1
	0x0104 00260 	PCDATA	$0, $-2
	0x0104 00260 	CBNZW	R3, 272
	0x0108 00264 	MOVD	foo..autotmp_9-256(SP), R2
	0x010c 00268 	JMP	288
	0x0110 00272 	MOVD	(R0), R1
	0x0114 00276 	CALL	runtime.gcWriteBarrier2(SB)
	0x0118 00280 	MOVD	foo..autotmp_9-256(SP), R2
	0x011c 00284 	STP	(R2, R1), (R25)
	0x0120 00288 	MOVD	R2, (R0)
	0x0124 00292 	PCDATA	$0, $-1
...

[JunyangShao]

@golang/compiler

I feel like we might need to walk all accesses to the maps, this is a most simple case:
all accesses to the map is through constant keys, and those accesses do not escape.

If there are variable keys it might be harder 🤔 .

[cherrymui]

In the general case, even if the map does not escape, the size is often not statically known. So the map buckets still need to be allocated on the heap. And we cannot allocate keys and values on the stack, as otherwise it would create heap to stack pointers. A more feasible approach is probably making use of scope-bounded runtime.free, so they are still heap allocated, but may not cause much GC pressure.

If the size is statically bounded, we might be able to do the stack allocations. I'm not sure if it is a common case, though.

[gabyhelp]

Related Issues

• cmd/compile: improve map iteration #18004
• runtime: bad pointer due to map iteration #9384 (closed)
• runtime: allocate no-escape map buckets to the stack more aggressively #58214
• cmd/compile: Pointer escapes when stored in a non-escaping map #63343 (closed)
• cmd/compile: map literals should be allocated on the stack if not escaping #21830 (closed)
• cmd/compile: map lookup of boolean, then converted to interface{}, causes parameter smash #19275 (closed)

Related Code Changes

• cmd/gc: allocate non-escaping maps on stack
• cmd/gc: optimize existence-only map lookups
• cmd/compile: add more constmodify/modify OPs on AMD64
• runtime: evacuate maps more aggressively

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

[randall77]

We do allocate a single map bucket (now called a slot group) as well as the map header on the stack if the map doesn't escape.
Not sure that helps this situation, but FYI.

[adonovan]

We do allocate a single map bucket (now called a slot group) as well as the map header on the stack if the map doesn't escape. Not sure that helps this situation, but FYI.

Yeah, I noticed the 3x8-word inlined memclr. :)