Language Design Lessons: append considered harmful
Published: 2022-09-21 03:46:08

CPUs implement very fast access to array data: sequences of values of the same type.  It makes sense, then, that higher-level languages provide abstractions for this approach.  Go provides a [built-in concept of a "slice"](https://go.dev/blog/slices) to handle sequences of values with the same type.

## Slices

How are slices implemented?

A slice is represented by a slice header, something like
```go
type SliceHeader[T any] struct {
	Data *T
	Len  int
	Cap  int
}
```
here, Data points to the zeroth element of the slice.  It points to a separately-allocated array of items of type T.  Len gives the number of elements in the slice, and Cap gives the capacity of the underlying storage; that is, Data + Cap points to the end of the underlying storage allocation.  In terms of garbage collection, Data serves to keep the underlying storage alive.

Slices can be created using literal expressions, or with `make`:

```go
strings := []string{"expedita", "maiores", "quia", "animi"}
fmt.Printf("len=%d, cap=%d\n", len(strings), cap(strings))
// Output: len=4, cap=4
```

```go
ints := make([]int, 5)
fmt.Printf("len=%d, cap=%d, initial=%d\n", len(ints), cap(ints), ints[0])
// Output: len=5, cap=5, initial=0
```

Slices can also be created from other slices:

```go
middleInts := ints[1:4]
fmt.Printf("len=%d, cap=%d\n", len(middleInts), cap(middleInts))
// Output: len=3, cap=4
```

Note that the capacity of this slice is 4, even though the underlying storage has 5 elements.  That's because the `Data` field of the slice header is pointing to the second (index 1) element of `ints`, after which only 4 elements are valid.

Go provides no way to "expand" a slice.  That is, given `middleInts`, there is no way to read `ints[0]` or `ints[4]`.  But there is a way to _write_ to `ints[4]`, given only `middleInts`.  This sentence should set off security-vulnerability alarm bells in your head!

## Append

The common operation of accumulating items into a slice is supported by the [`append` built-in](https://pkg.go.dev/builtin#append).  In Go1.18 and later, the signature can be written `func append[T any]([]T, ...T) []T`.  It was impossible to write such a function in previous versions of Go -- a curious situation for such a ubiquitous operation.

Anyone familiar with functional programming probably recognizes `append`'s signature: it takes a data structure as an argument, along with some additional data, and returns a new data structure with the combined data.  Does it modify the original slice?  For a functional language, this would be an emphatic "no".  A procedural language would answer "yes", and in fact would modify the slice in-place, and return nothing.

Go's choice? "maybe"!  Append _sometimes_ modifies its argument, or more specifically the storage underlying its argument.  An experienced software engineer knows that "sometimes" leads to intermittent bugs, and that's exactly what happens with `append`.  What's going on here?

```go
strings := []string{"expedita", "maiores", "quia", "animi"}
firstTwo := strings[:2]
three := append(firstTwo, "uhoh")
fmt.Printf("three=%#v\n", three)
fmt.Printf("strings=%#v\n", strings)
// Output:
// three=[]string{"expedita", "maiores", "uhoh"}
// strings=[]string{"expedita", "maiores", "uhoh", "animi"}
```

How did that `"uhoh"` appear in `strings`?  Nothing in the code suggests that `strings` is ever mutated.  The `append` on the third line sees that there is room in the underlying storage for another element, and simply writes into the storage without re-allocating anything.  This write _aliases_ with other slices pointing to the same underlying storage -- in this case, with `strings`.  This can cause unexpected results and data corruption even in single-threaded code, but could even cause race conditions and panics in a concurrent program.  And all of those are potential security vulnerabilities.

You can imagine that, in a dynamic application dealing with slices of varying lengths, the same call to append may sometimes reallocate, and sometimes simply write into the existing storage.  The race conditions are data-dependent, and may only happen intermittently, perhaps never in tests and only on some users' systems -- a nightmare bug!

To review, a _fundamental function_ of the language runtime has a design that's similar to other languages, but different in subtle ways.  And, those subtleties can lead to nondeterministic memory corruption and crashes.  The rest of the story writes itself.

## Reallocations

When `append` re-allocates memory, how much does it allocate? Those with a computer-science background might remember the phrase "amortized constant time".  When `append` re-allocates, it allocates twice the size of the existing storage.  Sparing you the big-O details, the effect is to balance the cost of repeatedly allocating and copying memory against the possibility of allocating memory that will never be used.

At least, this was the case until Go1.18.  Buried [deep in the release notes](https://go.dev/doc/go1.18#runtime), the reallocation algorithm has been tuned to be "less prone to sudden transitions in allocation behavior".  This means that in some situations, it may allocate less underlying storage space, but in others, it may allocate more.  In either case, the times at which it reallocates will change, potentially uncovering previously innocuous aliasing issues.  The result has been that some applications, when built with Go1.18, use notably more memory to perform the same tasks.

Tuning this algorithm is a good choice, but it highlights the fragility of software built using `append` -- which is to say, all software written in Go.

## Live Data

A subtle detail of slices is that the Data field keeps the _entire_ backing storage alive, in terms of garbage collection.  

A common error is to allocate a large slice, then return a much smaller sub-slice.  For example:

```go
firstFiveWords := readDictionary()[:5]
```

This is a `[]string` containing 5 elements, so surely it cannot use but a few hundred bytes!  No, in fact, the entire dictionary is kept resident by this single slice, even though it is impossible to access any other words but the first five.

This sort of error is hard to spot, all the more so because memory management is Go is automatic, with no explicit allocation or de-allocation primitives.  This can easily lead to explosions in runtime memory usage, causing out-of-memory errors in users systems.  As with the `append` issues above, these problems are usually not visible in unit tests.

## Summary

Built-in operations in a language will be used _everywhere_, and it's critical to get their design right.  Where that's not the case, bugs creep in due to subtle misunderstandings and implementation details, and seemingly innocent changes can have dramatic, difficult-to-catch, and difficult-to-debug consequences.

Multiplied by hundreds of thousands of engineers using these built-in operations day-to-day, and millions of people relying on the software they're building, the cost of poor language design is staggering.