Repository: go
Issue: proposal: arena:  new package providing memory arenas
Labels: Proposal,Proposal-Hold

**Note, 2023-01-17**. This proposal is on hold indefinitely due to serious API concerns. The GOEXPERIMENT=arena code may be changed incompatibly or removed at any time, and we do not recommend its use in production.

- - -

# Proposal: arena: new package providing memory arenas

Author(s): Dan Scales (with input from many others)

Last updated: 2022-2-22

Discussion at https://golang.org/issue/51317

## Abstract

We propose implementing memory arenas for Go. An arena is a way to allocate a set of memory objects all from a contiguous region of memory, with the advantage that the allocation of the objects from the arena is typically more efficient than general memory allocation, and more importantly, the objects in the arena can all be freed at once with minimal memory management or garbage collection overhead. Arenas are not typically implemented for garbage-collected languages, because their operation for explicitly freeing the memory of the arena is not safe and so does not fit with the garbage collection semantics. However, our proposed implementation uses dynamic checks to ensure that an arena free operation is safe. The implementation guarantees that, if an arena free operation is unsafe, the program will be terminated before any incorrect behavior happens. We have implemented arenas at Google, and have shown savings of up to 15% in CPU and memory usage for a number of large applications, mainly due to reduction in garbage collection CPU time and heap memory usage.

## Background

Go is a garbage-collected language. Application code does not ever explicitly free allocated objects. The Go runtime automatically runs a garbage-collection algorithm that frees allocated objects some time after they become unreachable by the application code. The automatic memory management simplifies the writing of Go applications and ensures memory safety.

However, large Go applications spend a significant amount of CPU time doing garbage collection. In addition, the average heap size is often significantly larger than necessary, in order to reduce the frequency at which the garbage collector needs to run.

Non-garbage-collected languages also have significant memory allocation and de-allocation overhead. In order to deal with complex applications where objects have widely varying lifetimes, non-garbage-collected languages must have a general-purpose heap allocator. Because of the differing sizes and lifetimes of the objects being allocated, such an allocator must have fairly complex code for finding memory for a new object and dealing with memory fragmentation.

One approach to reducing the allocation overhead for non-garbage-collected languages is [region-based memory management](https://en.wikipedia.org/wiki/Region-based_memory_management), also known as arenas. The idea is that applications sometimes follow a pattern where a code segment allocates a large number of objects, manipulates those objects for a while, but then is completely done with those objects, and so frees all (or almost all) of the objects at roughly the same time. The code segment may be allocating all the objects to compute a result or provide a service, but has no need for any of the objects (except possibly a few result objects) when the computation is done.

In such cases, region-based memory allocation using an arena is useful.  The idea is to allocate a large region of memory called an arena at the beginning of the code segment.  The arena is typically a contiguous region, but may be extensible in large chunk sizes.  Then all the objects can be allocated very efficiently from the arena. Typically, the objects are just allocated consecutively in the arena.  Then at the end of the code segment, all of the allocated objects can be freed with very low overhead by just freeing the arena.  Any result object that is intended to be longer-lived and last past the end of the code segment should not be allocated from the arena or should be fully copied before the arena is freed.

Arenas have been found to be useful for a number of common programming patterns, and when applicable, can reduce memory management overhead in non-garbage collected languages.  For instance, for a server serving memory-heavy requests, each request is likely independent, so most or all of the objects allocated while serving a particular request can be freed when the request has been fulfilled.  Therefore, all the objects allocated during the request can be allocated in an arena, and then freed all at once at the completion of the request.

In a related vein, arenas have been useful for protocol buffer processing, especially when unmarshalling the wire format into the in-memory protocol message object. Unmarshalling a message's wire format to memory can create many large objects, strings, arrays, etc., because of the complexity of messages and the frequent nesting of sub-messages inside other messages.  A program may often unmarshal one or more messages, make use of the in-memory objects for a period of time, and then be done with those objects. In this case, all of the objects created while unmarshalling the message(s) can be allocated from an arena and freed all at once. The C++ protocol buffer documentation provides [an example of using arenas](https://developers.google.com/protocol-buffers/docs/reference/arenas). Arenas may similarly be useful for other kinds of protocol processing, such as decoding JSON.

We would like to get some of the benefits of arenas in the Go language.  In the next section, we propose a design of arenas that fits with the Go language and allows for significant performance benefits, while still ensuring memory safety.

Note that there are many applications where arenas will not be useful, including applications that don't do allocation of large amounts of data, and applications whose allocated objects have widely varying lifetimes that don't fit the arena allocation pattern. Arenas are intended as a targeted optimization for situations where object lifetimes are very clear.


## Proposal

We propose the addition of a new `arena` package to the Go standard library. The arena package will allow the allocation of any number of arenas. Objects of arbitrary type can be allocated from the memory of the arena, and an arena automatically grows in size as needed. When all objects in an arena are no longer in use, the arena can be explicitly freed to reclaim its memory efficiently without general garbage collection. We require that the implementation provide safety checks, such that, if an arena free operation is unsafe, the program will be terminated before any incorrect behavior happens.

For maximum flexibility, we would like the API to be able to allocate objects and slices of any type, including types that can be generated at run-time via reflection.

We propose the following API:

```go
package arena

type Arena struct {
	// contains filtered or unexported fields
}

// New allocates a new arena.
func New() *Arena

// Free frees the arena (and all objects allocated from the arena) so that
// memory backing the arena can be reused fairly quickly without garbage
// collection overhead.  Applications must not call any method on this
// arena after it has been freed.
func (a *Arena) Free()

// New allocates an object from arena a.  If the concrete type of objPtr is
// a pointer to a pointer to type T (**T), New allocates an object of type
// T and stores a pointer to the object in *objPtr.  The object must not
// be accessed after arena a is freed.
func (a *Arena) New(objPtr interface{})

// NewSlice allocates a slice from arena a.  If the concrete type of slicePtr
// is *[]T, NewSlice creates a slice of element type T with the specified
// capacity whose backing store is from the arena a and stores it in
// *slicePtr. The length of the slice is set to the capacity.  The slice must
// not be accessed after arena a is freed.
func (a *Arena) NewSlice(slicePtr interface{}, cap int)
```

The application can create an arbitrary number of arenas using `arena.New`, each with a different lifetime.  An object with a specified type can be allocated in a particular arena using `a.New`, where `a` is an arena.  Similarly, a slice with a specified element type and capacity can be allocated from an arena using `a.NewSlice`. Because the object and slice pointers are passed via an empty interface, any type can be allocated.  This includes types that are generated at run-time via the `reflect` library, since a `reflect.Value` can be converted easily to an empty interface.

The application explicitly frees an arena and all the objects allocated from the arena using `a.Free`. After this call, the application should not access the arena again or dereference a pointer to any object allocated from this arena. The implementation is required to cause a run-time erro and terminate the Go program if the application accesses any object whose memory has already been freed. The associated error message should indicate that the termination is due to access to an object in a freed arena. In addition, the implementation must cause a panic or terminate the Go program if `a.New` or `a.NewSlice` is called after `a.Free` is called.  `a.New` and `a.NewSlice` should also cause a panic if they are called with an argument which is not the correct form (`**T` for `a.New` and `*[]T` for `a.NewSlice`).

Here is some sample code as an example of arena usage:

```go
import (
	“arena”
	…
)

type T struct {
	val int
}

func main() {
	a := arena.New()
	var ptrT *T
	a.New(&ptrT)
	ptrT.val = 1

	var sliceT []T
	a.NewSlice(&sliceT, 100)
	sliceT[99] .val = 4

	a.Free()
}
```

There may be an implementation-defined limit, such that if the object or slice requested by calls to `a.New` or `a.NewSlice` is too large, the object cannot be allocated from the arena.  In this case, the object or slice is allocated from the heap. If there is such an implementation-defined limit, we may want to have a way to expose the limit.  We’ve listed it as  one of the possible metrics mentioned in the “Open Issues” section.  An alternate API would be to not allocate the object or slice if it is too large and instead leave the pointer arguments unchanged.  This alternate API seems like it would be more likely to lead to programming mistakes, where the pointer arguments are not properly checked before being accessed or copied elsewhere. 

For optimization purposes, the implementation is allowed to delay actually freeing an arena or its contents. If this optimization is used, the application is allowed to proceed normally if an object is accessed after the arena containing it is freed, as long as the memory of the object is still available and correct (i.e. there is no chance for incorrect behavior). In this case, the improper usage of `arena.Free` will not be detected, but the application will run correctly, and the improper usage may be detected during a different run.

The above four functions are the basic API, and may be sufficient for most cases. There are two other API calls related to strings that are fairly useful. Strings in Go are special, because they are similar to slices, but are read-only and must be initialized with their content as they are created. Therefore, the `NewSlice` call cannot be used for creating strings. `NewString` below allocates a string in the arena, initializes it with the contents of a byte slice, and returns the string header.

```go
// NewString allocates a new string in arena a which is a copy of b, and
// returns the new string.
func (a *Arena) NewString(b []byte) string
```

In addition, a common mistake with using arenas in Go is to use a string that was allocated from an arena in some global data structure, such as a cache, which that can lead to a run-time exception when the string is accessed after its arena is freed. This mistake is understandable, because strings are immutable and so often considered separate from memory allocation. To deal with the situation of a string whose allocation method is unknown, `HeapString` makes a copy of a string using heap memory only if the passed-in string (more correctly, its backing array of bytes) is allocated from an arena. If the string is already allocated from the heap, then it is returned unchanged. Therefore, the returned string is always usable for data structures that might outlast the current arenas.

```go
// HeapString returns a copy of the input string, and the returned copy
// is allocated from the heap, not from any arena. If s is already allocated
// from the heap, then the implementation may return exactly s.  This function
// is useful in some situations where the application code is unsure if s
// is allocated from an arena.
func HeapString(s string) string
```

Of course, this issue of mistakenly using an object from an arena in a global data structure may happen for other types besides strings, but strings are a very common case for being shared across data structures.

We describe an efficient implementation of this API (with safety checks) in the "Implementation" section. Note that the above arena API may be implemented without actually implementing arenas, but instead just using the standard Go memory allocation primitives. We may implement the API this way for compatibility on some architectures for which a true arena implementation (including safety checks) cannot be implemented efficiently.


## Rationale

There are a number of possible alternatives to the above API.  We discuss a few alternatives, partly as a way to justify our above choice of API.

### Removing Arena Free

One simple adjustment to the above API would be to eliminate the arena `Free` operation. In this case, an arena would be freed automatically only by the garbage collector, once there were no longer any pointers to the arena itself or to any objects contained inside the arena. The big problem with not having a `Free` operation is that arenas derive most of their performance benefit from more prompt reuse of memory. Though the allocation of objects in the arena would be slightly faster, memory usage would likely greatly increase, because these large arena objects could not be collected until the next garbage collection after they were no longer in use. This would be especially problematic, since the arenas are large chunks of memory that are often only partially full, hence increasing fragmentation. We did prototype this approach where arenas are not explicitly freed, and were not able to get a noticeable performance benefit for real applications. An explicit `Free` operation allows the memory of an arena to be reused almost immediately. In addition, if an application is able to use arenas for almost all of its allocations, then garbage collection may be mostly unneeded and therefore may be delayed for quite a long time.

### APIs that directly return the allocated objects/slices

An alternate API with similar functionality, but different feel, would replace `(*Arena).New` and `(*Arena).NewSlice` with the following:

```go
// New allocates an object of the given type from the arena and returns a
// pointer to that object.
func (a *Arena) New(typ reflect.Type) interface{}

// NewSlice allocates a slice of the given element type and capacity from the
// arena and returns the slice as an interface. The length of the slice is
// set to the capacity.
func (a *Arena) NewSlice(typ reflect.Type, cap int) interface{}
```

An example of usage would be:

```go
a := arena.New()
floatPtr := a.New(reflect.TypeOf(float64(0))).(*float64)
byteSlice := a.NewSlice(reflect.TypeOf(byte(0)), 100).([]byte)
```

This API potentially seems simpler, since it returns the allocated object or slice directly, rather than requiring that a pointer be passed in to indicate where the result should be stored. This allows convenient use of Go’s idiomatic short variable declaration, but does require type assertions to convert the return value to the correct type.  This alternate API specifies the types to be allocated using `reflect.Type`, rather than by passing in an interface value that contains a pointer to the required allocation type. For applications and libraries that already work on many different types and use reflection, specifying the type using `reflect.Type` may be convenient. However, for many applications, it may seem more convenient to just pass in a pointer to the type that is required.

There is an efficiency distinction in the `NewSlice` call with the two choices. In the `NewSlice` API described in the "Proposal" section, the slice header object is already allocated in the caller, and only the backing element array of the slice needs to be allocated. This may be all that is needed in many cases, and hence more efficient. In the new API in this section, the `Slice` call must allocate the slice object as well in order to return it in the interface, which causes extra heap or arena allocation when they are often not needed.

Another alternative for `a.New` is to pass in a pointer to type T and return a pointer to
type T (both as empty interfaces):

```go
// New, given that the concrete type of objPtr is a pointer to type T,
// allocates an object of type T from the arena a, and returns a pointer to the
// object.
func (a *Arena) New(objPtr interface{}) interface{}
```
An example use of this API call would be:  `intPtr := a.New((*int)(nil)).(*int)`.  Although this also allows the use of short variable declarations and doesn’t require the use of reflection, the rest of the usage is fairly clunky.

### Simple API using type parameterization (generics)

We could have an optional addition to the API that uses type parameterization to express the type to be allocated in a concise and direct way.  For example, we could have generic `NewOf` and `NewSliceOf` functions:

```go
// NewOf returns a pointer to an object of type T that is allocated from
// arena a.
func arena.NewOf[T any](a *Arena) *T
```

```go
// NewSliceOf returns a slice with element type T and capacity cap
// allocated from arena a
func arena.NewSliceOf[T any](a *Arena, cap int) []T
```

Then we could allocate objects from the arena via code such as:

```go
intPtr := arena.NewOf[int](a)
```

We don’t think these generic variants of the API can completely replace the suggested methods above, for two reasons.  First, the `NewOf` function can only allocate objects whose type is specified at compile-time.  So, it cannot satisfy our goal to support allocation of objects whose type is computed at run-time (typically via the `reflect` library).  Second, generics in Go are just arriving in Go 1.18, so we don’t want to force users to make use of generics before they are ready.

## Compatibility

Since this API is new, there is no issue with Go compatibility.

## Implementation

In order to fit with the Go language, we require that the semantics of arenas in Go be fully safe.  However, our proposed API has an explicit arena free operation, which could be used incorrectly.  The application may free an arena A while pointers to objects allocated from A are still available, and then sometime later attempt to access an object allocated from A.

Therefore, we require that any implementation of arenas must prevent improper accesses without causing any incorrect behavior or data corruption. Our current implementation of the API gives a memory fault (and terminates the Go program) if an object is ever accessed that has already been freed because of an arena free operation.

Our current implementation performs well and provides memory allocation and GC overhead savings on the Linux amd64 64-bit architecture for a number of large applications.  It is not clear if a similar approach can work for 32-bit architectures, where the address space is much more limited.

The basic ideas for the implementation are as follows:
 * Each arena `A` uses a distinct range in the 64-bit virtual address space
 * `A.Free` unmaps the virtual address range for arena `A`
 * The physical pages for the arena can then be reused by the operating system for other arenas.
 * If a pointer to an object in arena `A` still exists and is dereferenced, it will get a memory access fault, which will cause the Go program to terminate.  Because the implementation knows the address ranges of arenas, it can give an arena-specific error message during the termination.

So, we are ensuring safety by always using a new range of addresses for each arena, in order that we can always detect an improper access to an object that was allocated in a now-freed arena.

The actual implementation is slightly different from the ideas above, because arenas grow dynamically if needed. In our implementation, each arena starts as a large-size "chunk", and grows incrementally as needed by the addition of another chunk of the same size. The size of all chunks is chosen specifically to be 64 MB (megabytes) for the current Go runtime on 64-bit architectures, in order to make it possible to recycle heap meta-data efficiently with no memory leaks and to avoid fragmentation.

The address range of these chunks do not need to be contiguous.  Therefore, when we said above that each arena A uses a distinct range of addresses, we really meant that each chunk uses a distinct range of addresses.

Each chunk and all the objects that it contains fully participate in GC mark/sweep until the chunk is freed. In particular, as long as a chunk is part of an arena that has not been freed, it is reachable, and the garbage collector will follow all pointers for each object contained in the chunk. Pointers that refer to other objects contained in the chunk will be handled very efficiently, while pointers to objects outside the chunk will be followed and marked normally.

The implementation calls `SetFinalizer(A, f)` on each arena A as it is allocated, where `f` calls `A.Free`.  This ensures that an arena and the objects allocated from it will eventually be freed if there are no remaining references to the arena.  The intent though is that every arena should be explicitly freed before its pointer is dropped.

Because unmapping memory is relatively expensive, the implementation may continue to use a chunk for consecutively allocated/freed arenas until it is nearly full. When an arena is freed, all of its chunks that are filled up are immediately freed and unmapped. However, the remaining part of the current unfilled chunk may be used for the next arena that is allocated. This batching improves performance significantly.

Because of the large 64-bit address space, our prototype implementation has not required reusing the virtual addresses for any arena chunks, even for quite large and long-running applications. However, the virtual addresses of most chunks can eventually be reused, since there will almost always be no more reachable pointers to anywhere in the chunk. Since the garbage collector sees all reachable pointers, it can determine when an address range can be reused.

The implementation described above demonstrates that it is possible to implement the Arena API for 64-bit architectures with full safety, while still providing performance benefits. Many other implementations are possible, and some may be tuned for other types of usage. In particular, because of the 64 MB chunk size, the above implementation may not be useful for applications that need to create a large number of arenas that are live at the same time (possibly because of many concurrent threads). It is probably most appropriate that there should only be a few to 10's of arenas in use at any one time. Also, it is not intended that arenas be shared across goroutines. Each arena has a lock to protect against simultaneous allocations by multiple goroutines, but it would be very inefficient to actually use the same arena for multiple goroutines.  Of course, that would rarely make sense anyway, since the lifetimes of objects allocated in different goroutines are likely to be quite different.

## Open issues

Another possibility in the design space is to implement the API described in the "Proposal" section, but without the safety checks, or with an option to disable the safety checks. The idea here is that the performance savings from the use of arenas can be increased by doing an implementation that doesn't have safety guarantees. As compared to the implementation described above, we can avoid the mapping and unmapping overhead, and reuse the memory of an arena much more quickly (and without OS involvement) when it is freed. We have done a prototype of such an implementation, which we call "unsafe arenas". We have seen an additional 5-10% improvement in performance in some cases when using unsafe arenas rather than our safe arena implementation. However, we feel very strongly that arenas in Go need to be safe. We do not want the use of arenas to lead to memory bugs that may be very hard to detect and debug, and may silently lead to data corruption. We think that it is better to continue to optimize the implementation of safe arenas, rather than trying to support unsafe arenas.

It would be useful to have some run-time metrics associated with arenas.  The desired metrics will depend somewhat on the final API, so we have not yet tried to decide the exact metrics that will cover the application needs.  However, here are some metrics which might be useful:

 * the number of arena created and freed
 * the number of current arenas and the maximum number of arenas that have been active at one time
 * the total number of bytes allocated via arenas, and the average number of bytes allocated per arena
 * the (constant) limit on the largest-size object or slice that can be allocated from an arena

Another open issue is whether arenas can be used for allocating the elements of a map.  This is
possible, but it is not clear what a good API would be.  Also, there might be unusual cases if the arena used for the main map object is different from the arena used to allocate new elements of the map.   With generics arriving in Go 1.18, generic maps (or hash tables) can now be implemented in user libraries.  So, there could be a user-defined generic map implementation that allows optionally specifying an arena for use in allocating new elements.  This might be the best solution, since that would allow for greater flexibility than adjusting the semantics of the built-in `map` type.

## Protobuf unmarshalling overheads

As noted above, arenas are often quite useful for reducing the allocation and GC overhead associated with the objects that are created as a protobuf message is being unmarshaled. We have prototyped changes to the [protobuf package](https://pkg.go.dev/google.golang.org/protobuf) which allow for providing an arena as the allocation option for objects created during unmarshalling. This arrangement makes it quite easy to use arenas to reduce the allocation and GC overhead in applications that make heavy use of protobufs (especially unmarshalling of large protobufs). If the arena proposal is accepted and implemented in Go, then it would make sense to extend the protobuf package to provide such an arena allocation option.