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 articleThe 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.
Coming soon