Reference
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 articleUnder 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 articleUnder 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