PJ Malloy (@thepudds)
January 2025
Discussion at https://go.dev/issue/74299.
CL stack at https://go.dev/cl/673695.
This is a design for implementing a runtime.free within the runtime, and then using it via automatic calls inserted by the compiler and via a limited set of explicit calls from the standard library.
When triggered, the goals include faster reuse of user memory, less overall CPU usage by the GC, longer times between GC cycles (with less overall time with the write barrier enabled), and more cache-friendly allocations for user code.
This hopefully complements other on-going work like:
The compiler today might be able to prove that an allocation does not escape, but in many cases today the allocation is still placed on the heap (such as because of a variable size that is not statically visible at compile time, or the size is too large for the stack).
Separately, in some cases, the runtime or standard library might know a heap object is logically dead but the compiler is unable to prove that.
More generally, for reducing allocations, there is sometimes a chicken and egg problem.
For example, #72036 is a WIP approach to update escape analysis so that interface arguments do not always escape, with a primary target of w.Write(b) and friends, but many interesting byte slices are variable size known only at runtime. Currently, a make with an unknown capacity (beyond 32 bytes) causes a slice to be heap allocated, so solely improving escape analysis in this case has limited impact on actual applications -- if a slice is heap allocated for two reasons, eliminating one reason just means it is still heap allocated for the other reason, which lessens the value of doing the work to eliminate the first reason.
In an attempt to help triangulate on what is possible for the runtime, compiler, and standard library to do together to reduce how much work the GC must do, this document proposes updates to:
The runtime: implement the ability to free memory explicitly without waiting for a GC cycle. Freed objects are recorded in one of two types of new free lists, and are then immediately reusable for the next allocation in the same span class, and hence can dramatically reduce pressure on the GC. Challenges here include:
The standard library: update code to invoke a runtime.free explicitly in a few targeted places.
The compiler: automatically insert runtime calls to track and free slices allocated via make when the compiler can prove it is safe to do so.
All three steps have been implemented (with some of this work in review, some close to review, and some running but still in WIP stage).
A sample benchmark included below shows strings.Builder operating roughly 2x faster.
For the explicit invocation in the standard library, separate CLs update the builtin maps to free backing map storage during growth and split, as well as a small number of lower-level stdlib things like strings.Builder (which are “low level” in the sense that they already encapsulate some low-level performance tricks, but also in the sense that they let other higher-level pieces of the stdlib then safely benefit from their performance).
Note: It is not intended that higher-level portions of the stdlib (like net/http) would have manual calls to a runtime.free.
Additional steps that are natural follow-ons (but not yet attempted) include:
In the compiler, automatically insert calls to free the intermediate memory from repeated calls to append in a loop without freeing the final slice, such as for the patterns of append usage shown in slices.Collect and slices.AppendSeq. (The first round of work manually updates those two in particular, but that could wait for the compiler to automatically recognize those two patterns.)
Possibly extend to freeing more than just slices. (Slices are a natural first step, but the large majority of the work implemented is independent of whether the heap object represents a slice.)
In addition, having a runtime.free makes other improvements more appealing, such as in escape analysis.
The APIs in this section have a working initial implementation:
func freeSized(ptr unsafe.Pointer, size uintptr, noscan bool)
func freeTracked(trackedObjs *[]trackedObj)
Currently, the first API freeSized can be called by the standard library, with initial targets in the map grow/split code, strings.Builder, possibly places like slices.Collect and slices.AppendSeq, and other locations where the code knows it owns a pointer and has knowledge of when it is logically dead.
The second API freeTracked is automatically inserted by the compiler. freeTracked is paired with a new slice allocation function. Together, this allows for heap-allocated objects to be tracked and later automatically freed as a scope is exited:
func makeslicetracked64(et *_type, len64 int64, cap64 int64, trackedObjs *[]trackedObj) unsafe.Pointer
Note that freeSized accepts an unsafe.Pointer and hence keeps the pointer alive. It therefore could be a pessimization in some cases (such as a long-lived function) if the caller does not call freeSized before or roughly when the liveness analysis of the compiler would otherwise have determined the heap object is reclaimable by the GC.
In contrast, freeTracked operates on uintptr plus a sequence number to know whether it is still valid to use the uintptr. This avoids keeping the heap object alive longer than it otherwise would have been, which is important for performance and also simplifies where the runtime calls can be automatically placed by the compiler.
There are more details on these functions at the bottom of this document, including draft API doc.
An additional runtime API (most likely a temporary convenience) is currently inserted by the compiler instead of using makeslicetracked64:
func trackSlice(sl unsafe.Pointer, trackedObjs *[]trackedObj)
Additional CLs update the compiler to automatically insert free calls for slices allocated via make when the compiler can prove it is safe to do so.
Consider for example the following code:
func f1(size int) { s := make([]int64, size) // heap allocated if > 32 bytes _ = s }
In today's compiler, the backing array for s is not marked as escaping, but will be heap allocated if larger than 32 bytes.
As part of this work, the compiler has been updated so that the backing array for s is recognized as non-escaping but unknown size and it is valid to free it when f1 is done.
The compiler automatically transforms f1 to roughly:
func f1(size int) { var freeablesArr [1]struct { // compiler counts how many are needed (one, in this case) ptr uintptr sweepgen uint32 } freeables := freeablesArr[:] defer freeTracked(&freeables) s := make([]int64, size) trackSlice(unsafe.Pointer(&s), &freeables) _ = s }
The freeablesArr is stored on the stack and automatically sized by the compiler based on the number of target sites. The defer is inserted in a way so that it is an open-coded defer and hence has low performance impact.
See the API doc below for details on freeTracked.
The transformed code just above shows what is currently implemented, but two items seen there that might change as the implementation is polished:
freeTracked currently takes a slice for convenience, but we could make that tighter.makeslicetracked64 (for example, in f1 above), but the compiler currently inserts calls to a new runtime.trackSlice instead, which initially seemed slightly easier to implement on the compiler side. The current plan is to have the compiler use makeslicetracked64 instead.If there are multiple target sites within a function, such as in f2 here:
func f2(size1 int, size2 int, x bool) { s1 := make([]int64, size1) // heap allocated if > 32 bytes if x { s2 := make([]int64, size2) // heap allocated if > 32 bytes _ = s2 } _ = s1 }
The compiler counts the max number of sites (not sensitive to conditionals), and sizes freeablesArr appropriately (two element array in this case), with a single call to freeTracked per function:
func f2(size1 int, size2 int, x bool) { var freeablesArr [2]struct { // compiler counts how many are needed (two, in this case) ptr uintptr sweepgen uint32 } freeables := freeablesArr[:] defer freeTracked(&freeables) // only a single freeTracked call, regardless of how many tracked sites s1 := make([]int64, size1) trackSlice(unsafe.Pointer(&s1), &freeables) if x { s2 := make([]int64, size2) trackSlice(unsafe.Pointer(&s2), &freeables) _ = s2 } _ = s1 }
The max number of automatically inserted call sites is bounded based on the count of make calls in a given function.
Inside for loops or when a goto looks like it is being used in an unstructured loop, the compiler currently skips automatically inserting these calls.
However, a modest extension (and the current plan) is to have the compiler instead insert a separate runtime entry point in loops to allow heap-allocated slice memory to be reclaimed on each loop iteration that returns back to the same allocation spot when the compiler can prove it is safe to do so, without requiring unbounded or dynamic space in the trackedObj slice. (The compiler can already prove it is safe and the runtime entry point is prototyped.)
Using strings.Builder as an example target -- this is already a somewhat low-level part of the stdlib that already helps encapsulate some performance-related trickery, including using unsafe and bytealg.MakeNoZero. The strings.Builder already owns its in-progress buffer that is being built up, until it returns a usually final string. The existing internal comment says:
// External users should never get direct access to this buffer, since // the slice at some point will be converted to a string using unsafe, // also data between len(buf) and cap(buf) might be uninitialized. buf []byte
If we update strings.Builder to explicitly call runtime.freeSized on that buf after a resize operation (but without freeing the usually final incarnation of buf that will be returned to the user as a string), we can see some nice benchmark results on the existing strings benchmarks that call Builder.Write N times and then call Builder.String. Here, the (uncommon) case of a single Builder.Write is not helped (given it never resizes after first alloc if there is only one Write), but the impact grows such that it is up to ~2x faster as there are more resize operations due to more strings.Builder.Write calls:
│ disabled.out │ new-free-20.txt │
│ sec/op │ sec/op vs base │
BuildString_Builder/1Write_36Bytes_NoGrow-4 55.82n ± 2% 55.86n ± 2% ~ (p=0.794 n=20)
BuildString_Builder/2Write_36Bytes_NoGrow-4 125.2n ± 2% 115.4n ± 1% -7.86% (p=0.000 n=20)
BuildString_Builder/3Write_36Bytes_NoGrow-4 224.0n ± 1% 188.2n ± 2% -16.00% (p=0.000 n=20)
BuildString_Builder/5Write_36Bytes_NoGrow-4 239.1n ± 9% 205.1n ± 1% -14.20% (p=0.000 n=20)
BuildString_Builder/8Write_36Bytes_NoGrow-4 422.8n ± 3% 325.4n ± 1% -23.04% (p=0.000 n=20)
BuildString_Builder/10Write_36Bytes_NoGrow-4 436.9n ± 2% 342.3n ± 1% -21.64% (p=0.000 n=20)
BuildString_Builder/100Write_36Bytes_NoGrow-4 4.403µ ± 1% 2.381µ ± 2% -45.91% (p=0.000 n=20)
BuildString_Builder/1000Write_36Bytes_NoGrow-4 48.28µ ± 2% 21.38µ ± 2% -55.71% (p=0.000 n=20)
An alternative to strings.Builder calling runtime.freeSized itself would be to provide an alternate runtime entry point for appends where the backing array is known to be logically dead after a resize, and the runtime therefore knows it can do the free itself. Such a function could automatically be inserted by the compiler in many cases of appends in a loop, such as in the patterns shown by slices.Collect and slices.AppendSeq, though for more complex cases such as strings.Builder, it is probably unlikely that the compiler would be able to prove it is safe to automatically do so, including for strings.Builder, the manual edit must track whether Builder.String has already been called. (I suspect it is not the common case to call Builder.String multiple times on a single instance, but the API allows it).
Whether we ever use a runtime.free with strings.Builder is debatable (including there are alternatives that could be used for strings.Builder, such as a segmented buffer and/or sync.Pool such as used within cmd/compile). We are mainly using it here as a small-ish concrete example.
There are other potential optimizations for strings.Builder, like allocating an initial buf (e.g., 64 bytes) on the first Write, faster growth than current 1.25x growth for larger slices, and “right sizing” the final string, where these could use runtime.freeSized if those optimizations end up being worthwhile; an earlier cut did implement those optimizations, and the intent is to measure again with the more recent implementation.
For the cases where a normal allocation is happening without any reuse, some initial micro-benchmarks suggest the impact of these changes could be small to negligible (at least with GOAMD64=v3):
goos: linux
goarch: amd64
pkg: runtime
cpu: AMD EPYC 7B13
│ base-512M-v3.bench │ ps16-512M-goamd64-v3.bench │
│ sec/op │ sec/op vs base │
Malloc8-16 11.01n ± 1% 10.94n ± 1% -0.68% (p=0.038 n=20)
Malloc16-16 17.15n ± 1% 17.05n ± 0% -0.55% (p=0.007 n=20)
Malloc32-16 18.65n ± 1% 18.42n ± 0% -1.26% (p=0.000 n=20)
MallocTypeInfo8-16 18.63n ± 0% 18.36n ± 0% -1.45% (p=0.000 n=20)
MallocTypeInfo16-16 22.32n ± 0% 22.65n ± 0% +1.50% (p=0.000 n=20)
MallocTypeInfo32-16 23.37n ± 0% 23.89n ± 0% +2.23% (p=0.000 n=20)
geomean 18.02n 18.01n -0.05%
This section lists the runtime APIs that are either automatically inserted by the compiler or can be called from a targeted set of locations in the standard library.
Note: the term “logically dead” here is distinct from the compiler's liveness analysis, and the runtime free and re-use implementations must be (and attempt to be) robust in sequences such as a first alloc of a given pointer, GC observes and queues the pointer, runtime.free, GC dequeues pointer for scanning, runtime re-uses the same pointer, all within a single GC phase. (TODO: more precise term than “logically dead”?)
// freeSized records that a heap object is reusable and available for // immediate reuse in a subsequent mallocgc allocation, without // needing to wait for the GC cycle to progress. // // The information is recorded in a free list stored in the // current P's mcache. The caller must pass in the user size // and whether the object has pointers, which allows a faster free // operation. // // freeSized must be called by the effective owner of ptr who knows // the pointer is logically dead, with no possible aliases that might // be used past that moment. The intended callers are // a limited number of places in the standard library (e.g., strings.Builder) // or the runtime (e.g., maps grow/split code, append-handling // code). In the future, the compiler could also insert direct freeSized calls, // though currently a related API freeTracked serves that purpose. // // freeSized is a no-op if called on a stack pointer. It must not be called // on memory in the data or bss sections, which is partially enforced. // // In addition, the caller must know that ptr's object has no specials, such // as might have been created by a call to SetFinalizer or AddCleanup. // (Internally, the runtime deals appropriately with internally-created // specials, such as specials for memory profiling.) // // If the size of ptr's object is less than or equal to 16 bytes or // greater than 32 KiB, freeSized is currently a no-op. It must only // be called in alloc-safe places. func freeSized(p unsafe.Pointer, size uintptr, noscan bool) bool // makeslicetracked64 is like the existing makeslice64, but the caller // also passes in a pointer to a trackedObj slice that allows the runtime // to track the heap-allocated backing array and possibly later // free the tracked objects via freeTracked. The contents of // the trackedObj slice are opaque to the caller, but the caller // provides the space for the trackedObj slice. // // Currently, the only intended caller is code inserted by // the compiler, which only does so when escape analysis can // prove the associated pointer has a known scope -- currently, // when it can prove the pointer does not outlive the current // function. This effectively creates a scope for the // associated heap pointers. The compiler also arranges for // freeTracked to be called on function exit, so that // the heap objects are automatically freed when leaving the // scope. The compiler also arranges for the trackedObj slice's // backing array to be placed on the user's normal goroutine // stack to provide storage for the tracking information, // with that storage matching the lifetime of the tracked // heap objects (that is, both match the lifetime of // the function call). func makeslicetracked64(et *_type, len64 int64, cap64 int64, trackedObjs *[]trackedObj) unsafe.Pointer // freeTracked marks as reusable the objects allocated by // calls to makeslicetracked64 and tracked in the trackedObjs // slice, unless the GC has already possibly reclaimed // those objects. // // The trackedObj slice does not keep the associated pointers // alive, and freeTracked becomes a no-op if the GC cycle // has progressed such that the GC might have already reclaimed // the tracked pointers before freeTracked was called. // This might happen for example if a function call lasts // multiple GC cycles. This is currently decided per tracked // object. // // The compiler statically counts the maximum number of // possible makeslicetracked64 calls in a function // in order to statically know how much user // stack space is needed for the trackedObj slice. func freeTracked(trackedObjs *[]trackedObj) // trackedObj is used to track a heap-allocated object that // has a proven scope and can potentially be freed by freeTracked. // // trackedObj does not keep the tracked object alive. // // trackedObj is opaque outside the allocation and free code. // The common case is the sweepgen matches the current sweepgen // but if there is a mismatch, the runtime does not attempt // to reuse the tracked object. // // TODO: there is a plan to allow a trackedObj to have specials, // including user-created via SetFinalizer or AddCleanup, but // not yet implemented. (In short -- update runtime.addspecial // to update a bitmap of objIndexes that have specials so // that the fast path for allocation & free does not need to // walk an mspan's specials linked list, and then a trackedObj with // specials will not be reused. An alternative might be to // sweep the span and process the specials after reaching // the end of an mspan in the mcache if there are reusable // objects with specials, but that might be harder or perhaps // infeasible. More generally, sweeping sooner than the // normal GC but not in the allocation/free fast path (perhaps // in a goroutine managed by the runtime), might be worth // exploring for other reasons than just specials). type trackedObj struct { ptr uintptr // tracked object sweepgen uint32 // TODO: perhaps use more bits; mheap_.sweepgen is 32 bits. spc spanClass // 1 byte; potential optimization (not used yet) }
An earlier version of this work also implemented an API that just took an unsafe.Pointer, without any size or noscan parameters, like:
func free(ptr unsafe.Pointer)
However, this was more expensive than the more explicit freeSized API, primarily due to needing to call spanOf, findObject or similar. It might make sense to re-introduce this simpler API, though currently the best guess is it is not worthwhile. (Early measurements suggested that passing the size and noscan parameters like in freeSized allowed eliminating roughly 60% of the cost of a free operation, though the implementation has changed and improved since then, and it might be worth re-measuring.)
If we do not use that signature, we likely should use the name runtime.free for the API described as runtime.freeSized in this document.
Separately, we will likely also use a runtime.freeSlice.
In the current implementation, it is primarily used as a test function, but currently leaning towards using it in some spots in the standard library as a convenience for callers over runtime.freeSized.