Data Structures · Cluster
Arrays and Sequences
Contiguous storage, dynamic arrays, and deque layouts.
- 01 Row-Major Layout and the Address Arithmetic Behind Indexing How a pair of subscripts becomes one byte offset, why the last subscript varies fastest, and what traversal order does to cache-line consumption.
- 02 Growth Policies in Dynamic Arrays and What the Allocator Does With Them Why doubling beats incremental growth, how realloc can extend a buffer in place, and which costs a growth policy actually controls.
- 03 What a Slice Descriptor Holds and Why It Is Three Words The pointer, length and capacity triple that makes a slice cheap to pass, how subslicing shares storage, and where the shared-buffer aliasing shows up.
- 04 Array of Structs or Struct of Arrays How element stride decides which fields a scan pulls into cache, when splitting a record into parallel columns pays, and what the split costs elsewhere.
- 05 Sequential Scans, Hardware Prefetch, and the Page Walk What happens between a linear loop over an array and the memory it reads, why huge pages change the cost, and where a scan stops being sequential.
- 06 Ring Buffers and the Cost of Telling Full From Empty Why a fixed-size queue needs one extra slot, how the monotonic counter variant trades a mask for a free bit, and where each breaks under concurrency.
- 07 Deque Layouts and the Cost of Push at Both Ends Why a double-ended queue cannot be a plain growable array, how an array of fixed blocks gives O(1) at both ends, and what the extra indirection costs an index.
- 08 Erasing From the Middle: Compaction and the Order It Destroys Why removal from a contiguous array costs a shift, when swap-and-pop is the right substitute, and how tombstone markers defer the cost without hiding it.
- 09 Bit-Packed Integer Arrays and Vectorized Decoding How fixed-width packing puts k-bit integers into words, why decoding costs more than encoding, and how SIMD shuffles make unpacking cheap.
- 10 Immutable Sequences and Structural Sharing in Radix-Balanced Vectors How a fixed branching factor turns an array into a shallow tree whose updates copy one path, and what the size table and tail slot buy the index.