cmd/compile: escape analysis for backing arrays

[snadrus]

Go's automatic memory management doesn't rely entirely on garbage collection. Escape analysis provides a faster solution where possible.
Lets apply escape analysis to backing arrays (the arrays behind slices).

Example

In the next example, if append grows the array, it could put the old array directly back into the free lists:

func filter(haystack []X, predicate func(X) bool) []X {
  var result []X
  for _, v := range haystack {
    if predicate(v) {
      result = append(result, v)               // result may grow many times. 
  }
  return result
}

An alternate append-grow that returns the heap memory to a thread-local free list could be proven safe.

The compiler can verify that no references to intermediate slice values survive later iterations, so there are zero references at the function end to previous backing arrays. If an intermediate was used in a function call, this would follow the regular escape analysis logic.

Collision with GC

To avoid Garbage Collection competition, these non-escaping slices could be removed from stack maps. Their capturing func would need an implicit defer-type behavior to add them to GC when returned.

 defer func(){ retValGC = retValNoEscape }()      // added by compiler. Shouldn't affect line numbers, etc.

This also enables panic() scenarios to not leak. This is perhaps too literal as all that would happen would be a stack map reference.

Result

Garbage Collection would be reduced and Go programs would use considerably less memory-over-time (derivative). No language changes would be necessary, and the Go1 promise is kept. Potentially the same work will be completed with less total CPU.

Maps' private slices should be able to benefit from this too as they only grow when a single thread is writing and no other activity is taking-place. I doubt escape analysis can determine this, so it may need to be hard-coded.

Future

Future advances in Escape Analysis would help more cases of Go's automatic memory management to have a minimal footprint in all but the most especially-complex cases where Garbage Collection is the most reasonable solution.

[ianlancetaylor]

There is no user-visible change suggested here, so no need to use the proposal process. I will change to a suggestion for the compiler.

[mdempsky]

I think this requires flow-sensitive analysis, which escape analysis isn't currently setup for. This might be more feasible once escape analysis moves to SSA.

It also requires the runtime to prove a "free" operation that the compiler could emit calls to for allocations that are known to no longer be in use.

[adonovan]

I suspect there would be quite a lot of opportunities for improvement if escape analysis ran on the SSA form, after inlining. All those small functions that allocate, populate, and return a slice only for the caller to iterate over it could avoid generating garbage if the compiler emitted explicit calls to free; and when inlining causes the array size to become a constant, the array can simply be stack allocated.

[randall77]

Escape analysis already runs after inlining. For instance, the inlined version of f does not allocate, even though the uninlined version of f does allocate.

package main

func f() []byte {
	x := [4]byte{'a','b','c','d'}
	return x[:]
}

func main() {
	a := f()
	println(string(a))
}

[adonovan]

Sorry, I didn't mean to imply that escape analysis happened before inlining, only that the two are synergistic... but I guess inlining is synergistic with nearly everything.

[snadrus]

I wrote this ticket to investigate dynamic allocations whose pointers don't escape. Inlining doesn't prevent these allocations. The proposal is to consider if these can be freed and kept out of garbage collection by: 1) escape analysis verifying the pointers don't escape. 2) free() calls added by the compiler-suite I could see this removing a chunk of work from the garbage collection process (30% - 50%) in exchange for a free() call which needs to be light. If the return goes to thread-local pools, it may rely on the garbage collection cycle to re-distribute the free blocks or risk greater disarray of the free lists. (I'd guess). The result (I suspect) would be greater overall performance via fewer cycles spent on garbage collection.

…

On Fri, Mar 4, 2022, 1:01 PM Alan Donovan ***@***.***> wrote: Sorry, I didn't mean to imply that escape analysis happened before inlining, only that the two are synergistic... but I guess inlining is synergistic with nearly everything. — Reply to this email directly, view it on GitHub <#42165 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAOU4LTV7ZHWOAR3ETPG4ULU6JM2HANCNFSM4S4TTWAQ> . Triage notifications on the go with GitHub Mobile for iOS <https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675> or Android <https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub>. You are receiving this because you authored the thread.Message ID: ***@***.***>

[adonovan]

See also:

• cmd/compile: improve escape analysis of make([]T, n) where n is non-constant #20533: a near-dup. It suggests alloca for variable-sized slices, but the thread-local heap and explicit free proposed here seem safer. Presumably stores to the thread-local heap wouldn't need the write barrier either.
• cmd/compile: improve escape analysis of make([]T, len, cap) where len is non-constant #37975: special case where slice len is variable but cap is constant. Already fixed.