The hidden cost of growing data structures
You write a loop to parse a CSV file with fifty thousand rows. Locally it finishes in a blink. In production, the same code spikes CPU to ninety percent and memory usage jumps unpredictably. The algorithm looks fine. The logic is correct. The bottleneck is usually how Go handles slice growth and map resizing behind the scenes.
Big O notation measures how the work required by an operation scales as the input grows. It does not measure wall-clock time. It measures the relationship between data size and computational steps. When you call append on a slice or insert a key into a map, Go promises fast average performance. That promise comes with hidden reallocation costs that only show up when your data crosses a threshold. Understanding those thresholds separates code that scales from code that stalls.
How slices actually grow
A slice is not an array. It is a lightweight descriptor containing three values: a pointer to the underlying array, the current length, and the allocated capacity. When you index a slice or read its length, Go just reads those fields. That is strictly O(1). The work never changes regardless of whether the slice holds ten items or ten million.
Appending is where the math gets interesting. If the slice has spare capacity, append writes the new element into the next empty slot and increments the length. Still O(1). When capacity is exhausted, the runtime must allocate a larger backing array, copy every existing element into it, and update the slice header. That copy step is O(n).
The runtime does not panic. It handles the reallocation automatically. The cost is amortized across many appends. Doubling the capacity each time means you copy one element once, two elements once, four elements once, and so on. The average cost per append stays constant. Amortized O(1) is a statistical guarantee, not a per-call guarantee. A single append can still trigger an O(n) copy.
// BuildSlice demonstrates the difference between unbuffered and pre-allocated slices.
func BuildSlice(count int) []string {
// Pre-allocating capacity avoids repeated memory allocations and element copies.
items := make([]string, 0, count)
for i := 0; i < count; i++ {
// Append writes directly into the reserved backing array.
items = append(items, fmt.Sprintf("item-%d", i))
}
return items
}
Pre-allocating capacity turns the amortized average into a consistent O(1) per operation. The runtime never needs to hunt for a larger block of memory. You pay the allocation cost once upfront instead of spreading it across unpredictable spikes. The Go community treats make([]T, 0, expectedSize) as standard practice when the size is known. The extra characters in the function call are accepted because they make memory behavior explicit and predictable.
Slices are cheap descriptors. Capacity is your contract with the runtime.
Map lookups and the hash table reality
Maps in Go are hash tables. The runtime takes your key, runs it through a hash function, and uses the result to find a bucket. Insertion, lookup, and deletion all follow the same path. Under normal conditions, they are O(1) on average.
Hash collisions happen when two different keys produce the same bucket index. Go resolves collisions by chaining entries within the bucket. If your keys are well-distributed, collisions stay rare. If you feed the map adversarial keys or use a weak custom hash, lookups degrade to O(n). The standard library hash function is cryptographically rotated and heavily tested, so accidental worst-case collisions are virtually impossible in production code.
Map resizing works differently from slices. When a map grows past a load factor threshold, the runtime allocates a larger set of buckets and begins migrating entries. Modern Go performs this migration incrementally during subsequent map operations. You do not see a single O(n) pause. The work is spread out, keeping the amortized cost at O(1). Deletion does not shrink the map. Go leaves empty slots to avoid constant resizing churn.
// CountOccurrences builds a frequency map from a slice of words.
func CountOccurrences(words []string) map[string]int {
// Maps cannot be pre-allocated with a fixed size, but you can hint at expected capacity.
counts := make(map[string]int, len(words))
for _, w := range words {
// Incrementing an existing key or inserting a new one averages O(1).
counts[w]++
}
return counts
}
The make(map[K]V, hint) syntax accepts a capacity hint. It does not reserve memory like slice capacity. It tells the runtime to start with enough buckets to hold that many entries before resizing. The runtime ignores the hint if it is zero or negative. This convention saves multiple incremental resize cycles when you know the approximate dataset size.
Maps are unordered by design. Iteration order changes every run to prevent code from accidentally relying on insertion sequence.
When slicing and copying diverge
Slicing a slice creates a new header that points to the same backing array. s = s[:n] or s = s[2:5] is O(1). No data moves. The original array stays alive as long as the new slice holds a reference. This is why dropping a slice prefix can keep a large buffer pinned in memory.
The copy function is different. It moves data element by element. copy(dst, src) runs in O(min(len(dst), len(src))) time. It is explicitly O(n) relative to the number of elements transferred. Use slicing when you want a view. Use copy when you need an independent duplicate.
// TrimAndDuplicate shows the memory difference between slicing and copying.
func TrimAndDuplicate(data []byte) []byte {
// Slicing keeps a reference to the original backing array.
trimmed := data[2:10]
// Copying allocates a fresh buffer and moves the bytes.
independent := make([]byte, len(trimmed))
copy(independent, trimmed)
return independent
}
The compiler rejects programs that mix incompatible types in copy. You will see cannot use src (type []int) as type []byte in argument to copy if the element types do not match. The type system catches this at compile time, so runtime panics from mismatched slices never happen.
Slicing borrows memory. Copying buys it.
Realistic workload: processing an HTTP request body
Web servers frequently read a request body, split it into lines, and index the results. A naive implementation looks clean until traffic scales.
// IndexLines reads from an io.Reader, splits by newline, and builds a position map.
func IndexLines(r io.Reader) map[string]int {
// Reading the entire body into a buffer is O(n) relative to input size.
body, err := io.ReadAll(r)
if err != nil {
return nil
}
// Splitting creates a slice of byte slices. Capacity hint prevents reallocation spikes.
lines := bytes.Split(body, []byte{'\n'})
indices := make(map[string]int, len(lines))
for i, line := range lines {
// String conversion allocates a new string copy. The map insertion averages O(1).
indices[string(line)] = i
}
return indices
}
The bytes.Split call allocates a new slice for every line. The backing arrays are independent, so dropping the original body variable allows the garbage collector to reclaim the large buffer. The map insertion loop runs in amortized O(1) per line. If you omit the capacity hint, the map resizes multiple times as entries accumulate. Each resize triggers incremental bucket migration. The total work stays linear, but the constant factor grows.
Context cancellation belongs at the top of long-running reads. Pass ctx as the first parameter and check ctx.Err() after blocking calls. The convention keeps cancellation paths visible and prevents goroutine leaks when clients disconnect mid-request. Functions that accept a context should always respect deadlines and propagate cancellation down the call stack.
Context is plumbing. Run it through every long-lived call site.
Pitfalls and runtime behavior
Accessing a slice beyond its length triggers a panic. The runtime halts the goroutine and prints runtime error: index out of range [X] with length Y. This is not a compiler error. The compiler only checks constant bounds. Variable indices are validated at runtime. Always verify len(s) before indexing with a dynamic value.
Assuming map iteration preserves insertion order is a common trap. Go deliberately randomizes iteration order to expose fragile code. If you need deterministic output, collect the keys into a slice and sort them. The sort step is O(k log k) where k is the number of keys.
Repeatedly appending to a slice inside a tight loop without capacity hints causes CPU spikes during reallocation. The garbage collector must track the old backing arrays until they become unreachable. High allocation rates increase GC pause times. Pre-allocating capacity is the standard community practice. The boilerplate of make([]T, 0, expectedSize) is accepted because it makes memory behavior explicit.
Deleting keys from a map does not free memory immediately. Go marks slots as empty and reuses them. The map only shrinks if you explicitly create a new map and copy the remaining entries. This design avoids the O(n) cost of constant resizing.
The worst performance bug is the one that only appears under load. Measure before optimizing.
Choosing the right structure
Use a pre-allocated slice when you know the approximate number of elements upfront. Use an unbuffered slice with append when the count is dynamic and reallocation spikes are acceptable. Use copy when you need an independent duplicate that survives changes to the original backing array. Use a map when you need fast key-based lookups and do not require ordered iteration. Use a sorted slice with binary search when memory footprint matters more than insertion speed. Use plain sequential code when you do not need concurrency or complex indexing.