The Catalogues

Named catalogues, worked one entry at a time. Gamma and company's design patterns, Hohpe and Woolf's integration patterns, the data structures underneath them, and the problems that need several at once. Each post takes one entry: what the mechanism actually is, where the cost goes, the shape of problem it fits, when to reach for something else, and the Go to write it.

These are written to be returned to rather than read through. Sister surfaces: Under the Hood explains how one thing works, and The Exam Room is certification scenarios. The Workshop's facilitator playbooks are reference too, and have no landing page of their own yet.

Data Structures

4 published

Under the Hood · Data Structures

What a Go Slice Actually Is

A Go slice is three words: a pointer to a backing array, a length and a capacity. Append writes into spare capacity when there is some and reallocates when there is not, so whether your caller sees the write depends on a number the caller cannot see. That is where a lot of real Go bugs come from, and it is a consequence of the header being a value while the array is shared.

Read article

Under the Hood · Data Structures

The Dynamic Array, and Why Amortised Growth Is Not a Trick

Growing an array by a constant factor makes n appends cost time proportional to n, so each one is constant on average while some are linear. Growing by a constant number of slots makes the same n appends quadratic. The geometric series that produces that result, why amortised constant still shows up as a latency spike on the request that triggers the copy, and why shrinking at half occupancy thrashes.

Read article

Under the Hood · Data Structures

The Singly Linked List, and When a Pointer Chase Is Worth It

A linked list splices in constant time and never moves an element that something else holds a pointer to. It also allocates once per node and makes every traversal a dependent load the prefetcher cannot follow, which is why a list of small values loses to a slice by a wide margin on real hardware. Where it still wins, and why a slice of nodes with integer indices is often the better linked list.

Read article