Growing storage by multiplying it rather than adding to it is the difference between n appends costing time proportional to n and costing time proportional to n squared. Counting the element moves: a million pushes into an array that doubles from a four-slot block perform 19 allocations and copy 1,048,572 elements, about 1.05 moves per push. A million pushes into an array that grows by 64 slots at a time perform 15,625 allocations and copy 7,812,000,000 elements, about 7,812 moves per push. The same million pushes, and about seven thousand times the copying.
Both are the same structure with the same operations. One line differs.
A block of storage and a number
A dynamic array is a fixed block of contiguous storage plus an integer saying how much of that block currently holds elements.
Call the block’s size the capacity and the integer the length. The invariant that makes this a dynamic array and not something else is that the length is never negative and never greater than the capacity. The elements live in the first length slots; the remaining capacity - length slots are reserved and meaningless. Every operation has to leave that true. The reserve is not empty in any physical sense. It holds whatever the allocator left there, and the structure’s contract says nothing about it.
Reading element i is address arithmetic: the base address of the block plus i times the size of one element. There is no search and no indirection, which is why indexing a dynamic array takes the same time whether the array holds ten elements or ten million.
Appending has two cases. While the length is below the capacity there is a free slot, so the element goes into slot length and the length increases by one. When the length reaches the capacity there is no free slot. The structure allocates a larger block, copies the live prefix across, releases the old block, and then does the ordinary append into the new one. That reallocation is the only interesting thing a dynamic array ever does, and the size of the new block is the only design decision in the structure.
Removing from the end reverses it: decrease the length, and the slot that was last becomes part of the reserve. Nothing moves.
Go hands you one of these already, since a slice is a pointer, a length and a capacity over an array it does not own, and append is the growth policy. Writing one by hand is how the policy becomes visible.
What the growth actually costs
Index, read and write at a known position are constant time. Append and remove at the end are constant time when no reallocation happens. Insert or delete at position i costs len - i moves, because everything after the insertion point shifts. The standard library says so itself: slices.Delete is documented as O(len(s)-i), and advises deleting a range in one call rather than one element at a time.
The cost that needs an argument is the reallocation, and the usual claim is that doubling makes append “amortised constant”. Here is the series that produces it.
Start at capacity 1 and double on every overflow. Over n appends, a reallocation happens as the length passes 1, 2, 4, 8, and so on, copying that many elements each time. The total copying is 1 + 2 + 4 + ... + 2^k where 2^k is the largest power of two below n, and the sum of a geometric series with ratio 2 is one less than twice its final term. So the total is bounded by 2n, for any n. Divide by n appends and the average copying per append is bounded by 2 element moves. The bound is the same small constant for any n, because every doubling before the last one costs less in total than the last one did.
For a general growth factor r, the reallocations before reaching n copy roughly n/r + n/r² + n/r³ + ..., which sums to n/(r-1). That counts the final copy as n/r, where the 2n bound above took the worst case of n landing just past a doubling and the last copy being nearly n itself. Doubling gives n, a factor of 1.5 gives 2n, a factor of 1.25 gives 4n. All of them are proportional to n. The factor sets the constant and not the complexity. It trades against wasted memory at the other end: a block grown by factor r can be as much as (r-1)/r unused, so doubling may leave nearly half the block idle where 1.25 leaves at most a fifth.
Now grow by a constant k slots instead. A reallocation happens every k appends, copying k, then 2k, then 3k, up to n. That is an arithmetic series, and its sum is about n²/(2k). Increasing k tenfold divides the work by ten and leaves it quadratic. Counting the moves for k = 64: 100,000 appends copy 78,124,992 elements, and 1,000,000 appends copy 7,812,000,000. The second is ten times the work of the first in appends and a hundred times in copying, which is what quadratic looks like when you watch it.
Amortised constant is an average, and a latency budget is not an average. The analysis above says the total is linear. It says nothing about any individual append, and one append in every growth run copies the entire live prefix, so its cost is proportional to n. On a request path, that append lands on one request. The request that triggers the copy of a 2-million-element array waits for 2 million element moves, an allocation, and the page faults as the new block is touched for the first time. Every other request on the same path returns in microseconds. The mean is unchanged and the high percentiles are not. This is why code with a hard latency bound sizes the block once, up front, and treats capacity as a limit to be enforced rather than a hint to be exceeded.
Shrinking is optional, and the threshold decides whether it is cheap or ruinous. A structure that only ever grows keeps the peak memory of its whole life, so there is a reason to release storage when the length falls. The intuitive rule, halve the block when the length falls to half the capacity, is the broken one. After that shrink the length equals the new capacity exactly, so the next append has to reallocate, and the removal after that shrinks again. Counting it on an alternating workload sitting at the boundary: 100,000 push-and-pop pairs performed 200,000 reallocations and moved 102,400,000 elements.
Halve at a quarter occupancy instead and the same 100,000 pairs performed zero reallocations. The reason is the gap the rule leaves behind it. Shrinking a block when the length is a quarter of capacity leaves the length at half of the new capacity. Growing again takes another length appends, and shrinking again takes another half of the length in removals. Neither threshold is reachable from the other without real work in between, and that gap is what keeps the amortised argument true in both directions rather than only in the growing one.
Contiguity is a constant factor that the complexity hides. Every element sits beside the next, so a cache line fetched for one element arrives holding several, and a linear scan has a stride the hardware prefetcher recognises. A linked list of the same elements costs an indirection per element and puts each node wherever the allocator had room. Both traversals are O(n). The measured times are not close. The ratio depends on element size, access pattern and machine, so benchmark your own case rather than repeat a figure from somewhere else.
Allocation is where the cost shows up in Go. On one machine (Intel Xeon at 2.80GHz, go1.24.7, linux/amd64), building a 10,000-element []int by appending to a nil slice took 108,907 ns and reported 357,627 bytes allocated across 19 allocations. The same loop into make([]int, 0, 10000) took 28,689 ns and reported 81,920 bytes across 1 allocation. Four and a half times the bytes, nineteen times the allocations, and on this machine about four times the wall clock.
Note the 19. A pure doubling from the first append needs 15 allocations to reach 10,000, so the runtime is not purely doubling, and the growth strategy has changed between Go releases. The language specification does not define it, and the documentation for append says only that a new underlying array is allocated when the existing capacity is insufficient. Treat the growth as amortised and the factor as unspecified. Where a specific capacity matters, state it with make or slices.Grow, both of which are documented to give you what you asked for.
Escape analysis can keep a backing array in the frame, and that is a compiler decision rather than a promise. When the compiler can prove that nothing outside a function retains the array and the size is known at compile time, the array can live on the stack and cost no allocation at all. Whether it does depends on the compiler version and on details of the surrounding code. go build -gcflags=-m prints what it decided for the function in front of you, which is the only reliable way to know.
Where it fits
The commonest shape in Go code is collecting results whose count is not known in advance and then either iterating over them or indexing into them. Read rows from a query, transform each one, return the lot. A dynamic array is the right structure for that. The only decision worth making is whether you can estimate the count well enough to preallocate, which you usually can from the length of the input.
It is also the structure a stack should be built from. Push and pop at the end are the two operations it does best, and a depth-first traversal, an expression evaluator, an undo history and a recursion made explicit are all stacks. The reserve left behind by a pop is already the right size for the next push. A stack that oscillates around a working depth stops reallocating entirely once it has grown to that depth.
Read-mostly tables belong here for a different reason. If the data is built once and then sorted, binary-searched, scanned, or passed to anything that takes a slice, contiguity is worth more than anything a pointer structure offers: one allocation, no per-element overhead, and a layout that every other part of the standard library already expects.
The real-time case is the same structure with the growth switched off. Size the block to the maximum the system is specified to handle, allocate it during startup, and treat an attempt to exceed it as an error the system reports rather than a reallocation it performs. That gives constant-time appends with no amortisation, no allocator on the hot path, and a hard answer to how much memory the component uses.
Where it does not fit, and what to use instead
A FIFO queue. Removing from the front either shifts every remaining element, which is O(n) per removal, or reslices with s = s[1:], which is constant time and never reclaims the head. The second looks free and is not: a long-lived queue’s block grows without bound while its length stays small, and the abandoned head slots keep references to dequeued elements alive against the collector. A ring buffer is the structure for this. Two indices into one fixed block, both ends constant time, and the block reused rather than consumed.
Frequent insertion away from the end. Each insert at position i moves len - i elements, and a workload that splices at a cursor it already holds is better served by a doubly linked list, where the splice is a few pointer writes. In Go that argument is weaker than the textbook makes it sound. container/list predates generics and stores each element as Value any, so every read is a type assertion over an interface value and every node is a separate allocation the collector has to trace. A generic linked list written by hand avoids the assertion and keeps the scattered nodes. Measure before switching, and expect the array to win up to a larger n than seems reasonable.
Lookup by key. Scanning a dynamic array is O(n), and keeping it sorted to binary-search in O(log n) makes every insertion O(n). A map is the answer, with one property to remember: Go’s map iteration order is unspecified and the runtime deliberately randomises it, so anything that needs a stable order collects the keys and sorts them on the way out. The randomisation exists so that code accidentally depending on the order fails early rather than in production.
Anything holding a pointer to an element. Growth moves every element to a new block, so &v.buf[i] is a pointer into an array the structure may have abandoned by the next append. If callers need stable addresses, store pointers in the array rather than values, or allocate elements in fixed-size chunks that are never moved and index across the chunks.
Priority order. container/heap is the right choice here, and it is implemented over exactly the structure described above: a slice, with the heap property maintained by index arithmetic. Its interface also predates generics, so you implement Len, Less, Swap, Push and Pop on your own type, which is still less work than getting the sift operations right by hand.
Large elements that grow often. Every reallocation copies every live element, so the copying cost scales with the size of one element. A slice of 200-byte structs that grows repeatedly moves a great deal of memory. Storing pointers instead cuts the copying to one word per element, adds an indirection per access, and gives the collector more pointers to trace, so benchmark it rather than assuming.
Writing one in Go
The type keeps the block at its full length and tracks the live count separately, so the reserve is visible in the code rather than hidden behind a slice header’s spare capacity.
package vector
// Vector is a dynamic array: one contiguous block of storage, plus a count of
// how much of it is live. A Vector is not safe for concurrent use.
type Vector[T any] struct {
buf []T // len(buf) is the capacity; buf[:n] is live, buf[n:] is reserve
n int
}
// New returns an empty Vector with room for capacity elements.
func New[T any](capacity int) *Vector[T] {
if capacity < 0 {
panic("vector: negative capacity")
}
return &Vector[T]{buf: make([]T, capacity)}
}
func (v *Vector[T]) Len() int { return v.n }
func (v *Vector[T]) Cap() int { return len(v.buf) }
func (v *Vector[T]) At(i int) T {
if i < 0 || i >= v.n {
panic("vector: index out of range")
}
return v.buf[i]
}
The generic parameter is [T any] and not a constraint, because nothing here compares or orders elements. Before generics this type was written with interface{}, which forced an allocation per boxed element for most types and a type assertion on every read. container/list still shows what that looked like.
Push and the growth policy:
const minCapacity = 4
func (v *Vector[T]) Push(x T) {
if v.n == len(v.buf) {
v.resize(v.growthTarget(v.n + 1))
}
v.buf[v.n] = x
v.n++
}
// growthTarget doubles, which makes the total copying across n pushes
// proportional to n. A constant increment here would make it quadratic.
func (v *Vector[T]) growthTarget(need int) int {
next := 2 * len(v.buf)
if next < minCapacity {
next = minCapacity // doubling from zero stays at zero
}
if next < need {
next = need // honour a Reserve larger than one doubling
}
return next
}
func (v *Vector[T]) resize(capacity int) {
next := make([]T, capacity)
copy(next, v.buf[:v.n])
v.buf = next
}
Two cases in growthTarget exist because of specific failures. Doubling a capacity of zero gives zero, so an empty Vector would loop or write out of range without the floor. And a caller asking for room for a thousand more elements needs a block that holds them, not a doubling that falls short, so the target takes whichever is larger.
Pop, with the shrink rule from the cost section:
func (v *Vector[T]) Pop() (T, bool) {
var zero T
if v.n == 0 {
return zero, false
}
v.n--
x := v.buf[v.n]
v.buf[v.n] = zero // stop the array keeping the popped element alive
v.maybeShrink()
return x, true
}
// maybeShrink halves the block once the live count falls to a quarter of it.
// Halving at half occupancy reallocates on every push-and-pop pair.
func (v *Vector[T]) maybeShrink() {
if len(v.buf) <= minCapacity || v.n > len(v.buf)/4 {
return
}
v.resize(len(v.buf) / 2)
}
// Reserve guarantees room for n more pushes without reallocating.
func (v *Vector[T]) Reserve(n int) {
if n < 0 {
panic("vector: negative reservation")
}
if need := v.n + n; need > len(v.buf) {
v.resize(v.growthTarget(need))
}
}
The assignment of zero into the vacated slot matters when T contains a pointer. Without it the block still references the popped element, and the collector cannot free it while the Vector lives. The standard library does the same thing: slices.Delete is documented to zero the elements it leaves behind at the tail.
Every mutating method takes a pointer receiver, and for this type the value-receiver bug is worse than usual. A Push declared on a value receiver would get a copy of the struct, write the element into the shared block through the copied slice header, and increment the copy’s length. The caller’s element is in the array and the caller’s length never changed, so the data is there and invisible.
Append aliasing is the bug this type exists to avoid, and it catches experienced Go programmers.
base := make([]int, 3, 8) // length 3, capacity 8
a := append(base, 10)
b := append(base, 20)
fmt.Println(a[3], b[3]) // prints: 20 20
Both appends found capacity 8 against length 3, so neither reallocated, both wrote slot 3 of the same array, and the second overwrote the first. a and b are the same array viewed twice. Change the capacity to 3 and the output becomes 10 20, because both appends allocate. The behaviour of two appends from one slice depends on a capacity that no type signature shows and no reader of the call site can see. Passing a slice to a function that appends to it is therefore a question about ownership. slices.Clip returns s[:len(s):len(s)], forcing the next append to allocate, and is the fix when a slice is handed out and must not be written through. The Vector above has no such hazard, because nothing outside it holds a slice into buf.
Preallocation with make removes the repeated growth measured earlier, and it is one argument:
func lengths(words []string) []int {
out := make([]int, 0, len(words))
for _, w := range words {
out = append(out, len(w))
}
return out
}
make([]int, 0, len(words)) allocates once and sets the length to zero, so append fills the reserve rather than growing. Writing make([]int, len(words)) instead and then appending is the mistake next to it: that produces a slice of len(words) zeroes with the real values appended after them. Where the slice already exists, slices.Grow(s, n) is documented to guarantee room for another n appends without a further allocation.
Testing it
The invariant checker comes first, and it is called after every mutation in every test. The invariant is what makes the structure the structure, and a test that checks only return values passes while the structure rots underneath it. A checker invoked after each operation turns a corrupted length into a failure at the operation that corrupted it rather than four operations later.
func checkInvariant[T any](t *testing.T, v *Vector[T]) {
t.Helper()
if v.n < 0 {
t.Fatalf("length %d is negative", v.n)
}
if v.n > len(v.buf) {
t.Fatalf("length %d exceeds capacity %d", v.n, len(v.buf))
}
}
t.Helper() makes the failure report the caller’s line rather than this function’s, which is what you want from something called from thirty places.
The table-driven test covers the cases with names, and the names are all boundaries:
func TestPopOrder(t *testing.T) {
tests := []struct {
name string
push []int
want []int // the order Pop returns them in
}{
{"empty", nil, nil},
{"single", []int{1}, []int{1}},
{"exactly the initial capacity", []int{1, 2, 3, 4}, []int{4, 3, 2, 1}},
{"one past it", []int{1, 2, 3, 4, 5}, []int{5, 4, 3, 2, 1}},
{"several growth steps", []int{1, 2, 3, 4, 5, 6, 7, 8, 9}, []int{9, 8, 7, 6, 5, 4, 3, 2, 1}},
}
for _, tc := range tests {
t.Run(tc.name, func(t *testing.T) {
v := New[int](0)
for _, x := range tc.push {
v.Push(x)
checkInvariant(t, v)
}
var got []int
for {
x, ok := v.Pop()
if !ok {
break
}
got = append(got, x)
checkInvariant(t, v)
}
if !slices.Equal(got, tc.want) {
t.Errorf("popped %v, want %v", got, tc.want)
}
})
}
}
Exactly at capacity and one past it are separate rows because that is where off-by-one errors live, and draining to empty exercises the shrink path on the way down.
The randomised test against a reference implementation finds what hand-written rows miss. The reference is a plain slice used as a stack. You are not testing the reference; you are testing that two independent implementations of the same contract agree, under sequences nobody would write by hand.
func TestAgainstReference(t *testing.T) {
rng := rand.New(rand.NewPCG(1, 2))
v := New[int](0)
var ref []int
for step := 0; step < 20000; step++ {
if rng.IntN(3) < 2 {
x := rng.IntN(1000)
v.Push(x)
ref = append(ref, x)
} else {
got, ok := v.Pop()
if len(ref) == 0 {
if ok {
t.Fatalf("step %d: popped %d from an empty vector", step, got)
}
} else {
want := ref[len(ref)-1]
ref = ref[:len(ref)-1]
if !ok || got != want {
t.Fatalf("step %d: popped (%d, %v), want (%d, true)", step, got, ok, want)
}
}
}
checkInvariant(t, v)
if v.Len() != len(ref) {
t.Fatalf("step %d: length %d, reference length %d", step, v.Len(), len(ref))
}
}
for i, want := range ref {
if got := v.At(i); got != want {
t.Fatalf("At(%d) = %d, reference has %d", i, got, want)
}
}
}
Three details carry this test. Pushes are weighted at two in three so the length drifts upward and the walk reaches capacities a balanced walk would not. The seed is fixed, from math/rand/v2’s explicit NewPCG, so a failure reproduces exactly instead of appearing once a fortnight on continuous integration. And the final loop compares every element rather than only the length, because a structure can agree on its length and still have moved an element to the wrong slot during a resize.
Fuzzing is for structures that consume bytes, and the operation script is a legitimate use of it. Driving the sequence of operations from the fuzz input lets the coverage-guided engine find interleavings. More usefully, it writes its own regression tests: go test -fuzz saves any failing input under testdata/fuzz, and from then on an ordinary go test replays it.
func FuzzOperations(f *testing.F) {
f.Add([]byte{0, 2, 1, 4, 3, 3, 6})
f.Fuzz(func(t *testing.T, script []byte) {
v := New[byte](0)
var ref []byte
for _, op := range script {
if op%2 == 0 {
v.Push(op)
ref = append(ref, op)
} else if got, ok := v.Pop(); len(ref) == 0 {
if ok {
t.Fatalf("popped %d from an empty vector", got)
}
} else {
want := ref[len(ref)-1]
ref = ref[:len(ref)-1]
if !ok || got != want {
t.Fatalf("popped (%d, %v), want (%d, true)", got, ok, want)
}
}
checkInvariant(t, v)
}
if v.Len() != len(ref) {
t.Fatalf("length %d, reference length %d", v.Len(), len(ref))
}
})
}
A few seconds of -fuzztime on the machine quoted earlier ran on the order of a hundred thousand executions and added a couple of dozen inputs to the corpus, none of them failures. For a structure with no parsing in it, that is about what the randomised walk already covers, and the corpus is the part worth having.
Benchmark any claim about cost, and report it as a measurement rather than as a fact about Go.
var sink []int
func BenchmarkBuild(b *testing.B) {
const n = 10000
b.Run("append to nil", func(b *testing.B) {
for range b.N {
var s []int
for i := 0; i < n; i++ {
s = append(s, i)
}
sink = s
}
})
b.Run("make with capacity", func(b *testing.B) {
for range b.N {
s := make([]int, 0, n)
for i := 0; i < n; i++ {
s = append(s, i)
}
sink = s
}
})
}
The assignment to a package-level sink stops the compiler eliminating a result nothing reads. Run it with -benchmem, and read the allocs/op column before the ns/op column: the nanoseconds belong to one machine and one release, while the allocation count follows from the code and the release rather than from the machine.
-race is required the moment the structure is shared, and the failure it catches does not look like a crash. A Vector is not safe for concurrent use, which is why its doc comment says so. If a version of it is going to be reached from several goroutines behind a mutex, the test for that version runs goroutines pushing and popping concurrently under go test -race. An unsynchronised write to the length field produces a wrong length rather than a fault, and a wrong length passes every test that does not happen to look at it on the unlucky interleaving. The race detector reports the unsynchronised access itself, at the line that made it, whether or not the run produced a wrong answer.
Between the invariant checker, the named boundaries and the random walk, a defect in the growth or shrink policy fails in the test run rather than in the request that was unlucky enough to trigger the copy.