Arrays and memory layout

An array stores its items side by side in one block of memory. That sounds simple, and it is the most important fact in data structures for real performance. The CPU never reads one byte at a time. It loads a cache line, typically 64 bytes, and it prefetches the lines it expects you to need next. Items packed together come in with the same load, so scanning an array is cheap.

A linked list has the same big-O cost for traversal, but each node sits somewhere else in memory. Every step can be a cache miss, which costs far more than the arithmetic. The asymptotics say the two are equal. The hardware says they're not.

The big idea

Locality is the principle behind this. Programs reuse nearby data (spatial locality) and recently used data (temporal locality). Layouts that keep related data together win because the cache and prefetcher assume the same thing. A dense array of small values can run an order of magnitude faster than a pointer-heavy structure with the same number of items.

Three rules follow:

1. Prefer contiguous storage for data you scan often.
2. Keep the hot fields of a record together, and move cold fields out.
3. Measure before you optimize. A profiler, covered in performance and profiling, shows whether time goes to misses or to work.

Walking through it: a ring buffer

A ring buffer is a fixed-size array with a moving start. It holds the most recent items of a stream and never allocates more memory after creation. Pushing into a full buffer overwrites the oldest item. That makes it a good fit for logs, metrics windows and audio samples.

class Ring:
    def __init__(self, n):
        self.buf = [None] * n; self.head = 0; self.size = 0
    def push(self, x):
        n = len(self.buf)
        if self.size == n:                       # full: overwrite the oldest
            self.head = (self.head + 1) % n; self.size -= 1
        self.buf[(self.head + self.size) % n] = x; self.size += 1
    def items(self):
        return [self.buf[(self.head + i) % len(self.buf)] for i in range(self.size)]

r = Ring(3)
for x in range(1, 6): r.push(x)
print(r.items())

Output:

[3, 4, 5]

Pushing 1 through 5 into a three-slot buffer keeps only the last three. Memory use is fixed at three slots, however long the stream runs. Operations are O(1), and the data sits contiguously, so reading it back is cache-friendly.

Dynamic arrays

Most languages' lists are dynamic arrays. When full, they allocate a bigger block, usually about 1.5 to 2 times the size, copy the items over, and free the old block. Any single append may be slow, but the average over many appends stays O(1). That is amortized cost. A latency-sensitive path that appends in bursts can still suffer from the occasional copy, so preallocate when the size is known.

Common mistakes

• Choosing a linked list for a workload that scans, when an array would be faster in practice.
• Storing a record as an object of pointers when a packed struct would fit more per cache line.
• Growing an array one element at a time on a hot path, instead of preallocating.
• Using a ring buffer with no policy for the overwritten items, when the data must not be lost.

Check yourself

• Why can a linked list be slower than an array with the same big-O for scanning? Answer: each node may be in a different cache line, so each step can miss the cache, while an array's items arrive together in a few loads.
• Why does a ring buffer's memory stay fixed? Answer: it allocates its slots once, and new items overwrite the oldest instead of growing the array.

Key takeaways

• The CPU loads cache lines, not bytes, so contiguous data is much faster.
• Locality explains most of the gap between a linked structure and an array.
• A ring buffer keeps a bounded window of a stream with fixed memory.
• Dynamic arrays give amortized O(1) appends, so preallocate on hot paths.

Further learning

Next, see hash maps for keyed lookup, and how buckets and collisions work.