Series
The Data Structures Series
One structure per post, implemented and tested in Go: what it is, what it costs in time, space and the constant factors Go imposes, when to reach for it, when to reach for something else, how to write it, and how to test it properly. Part of Under the Hood.
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 articleUnder the Hood · Data Structures
The Doubly Linked List, and Why container/list Disappoints
A backward pointer makes removal constant time when all you hold is the node, which is the operation a singly linked list cannot do at all. A circular list with a single sentinel then removes nearly every nil check and every end case. Why container/list, which predates generics, puts an interface box and a type assertion on every element, and when it is still the right thing to reach for.
Read article