Cache locality in Python

Why this matters

Two programs can do the same job and still run at very different speeds. Suppose both add up one million numbers. One stores the numbers in an array. The other stores them in a linked list, which is a chain of small objects where each object holds a value and a reference to the next object. The list version can be several times slower, and the arithmetic is the same in both. The difference is in where the numbers sit in memory.

This lesson explains that difference. You will see how the CPU reads memory, why nearby data is cheap to read, and why following a chain of references can be slow. Then you will run a timing program and read its output. The stack and heap lesson earlier in this module covers where objects live. This lesson is about how close together they are.

By the end you should be able to say why a linked list can be slower than an array even when both have the same length, and write a timing program that compares them fairly.

Memory is slow to reach

The CPU does arithmetic on values that it holds in its registers. A register is a tiny storage slot inside the chip. Most of a program's data lives in RAM, which is the large main memory outside the chip. To read a value from RAM, the CPU sends a request and waits for the answer. That wait is long. In the time one RAM read takes, a CPU can do many arithmetic steps.

To avoid waiting on every read, the chip keeps a small, fast copy of recently used memory. This copy is called the cache. It sits close to the CPU, in several levels. The first level is the smallest and the fastest. When the CPU asks for a value, one of two things happens:

• If the value is already in the cache, that is a cache hit. The read is fast.
• If the value is not in the cache, that is a cache miss. The chip must fetch it from RAM, and the read is much slower.

The cache does not fetch one byte at a time. It fetches a block of neighbouring memory called a cache line. On most current desktop and server chips a cache line is 64 bytes. When the chip reads one 4-byte number, it brings in the 60 bytes around it too. A later read of a neighbour is then a hit.

A library example makes this concrete. Suppose you ask a librarian for book 7, and the librarian fetches the whole shelf from 1 to 16 because they sit together. The next fifteen requests are answered from the desk in front of you. If your next request is for book 912, which is in a different room, the librarian must walk there, and that trip costs time again.

The rule that follows is simple. Reading memory right next to the memory you just read is cheap. Reading memory somewhere else is expensive. This is what the term cache locality means: how close together the data you use is in memory.

Arrays keep their values in one row

The array module from the standard library stores a list of plain numbers in one block, with a fixed size for each item. An array of five numbers takes five slots side by side, and the value at index 3 sits right after the value at index 2. A loop that goes through the array reads memory in a straight line. Each cache line it fetches holds several values the loop needs next.

A regular Python list is different. It holds references, one for each item, and each item is an object of its own. So a list of integers is a row of references, and the integers are somewhere else in memory. The next example builds an array and a linked list with the same five values, and prints them in order.

Type nothing into the Input box for this program.

array: 10 20 30 40 50
list:  10 20 30 40 50

Both lines show the same values. The difference is in how the program reaches them. The array loop knows where each item is from its index: the address of values[3] is the start address plus 3 times 4 bytes. The list walk cannot do that. It must read p.next to learn where the next node is, and only then can it read that node's value. Each step depends on the read before it, so the CPU cannot start the next read early.

A Python object also carries extra bookkeeping. Each node has a header that tells the interpreter its type, and its attributes take space too, as lesson 11 showed. So a node holds more memory than its value. Five nodes take up more space than five numbers in an array, and that space is spread over more cache lines.

Why the list can be slow even when nodes are close

A linked list is not slow just because it is linked. Its speed depends on where the nodes sit in memory. CPython usually places objects that are created one after another close together, so a list built in creation order is often a straight walk through memory. The trouble starts when the order of the chain differs from the order of the memory. Then each step jumps to a different place, and many steps become cache misses.

The timing program below tests exactly that. It builds one million nodes, and links them in two different ways. One chain follows the creation order. The other chain visits the same nodes in a random order. It then times how long each walk takes, and compares both with a scan of an array that holds the same numbers.

A timing example

Save this program as timing.py and run it with python3 timing.py. It creates three sizes of data, and at the largest size it peaks at about 270 MB of memory, so it can take a little while to finish.

import array
import random
import time
 
 
class Node:
    __slots__ = ("value", "next")
 
    def __init__(self, value):
        self.value = value
        self.next = None
 
 
def sum_array(values):
    total = 0
    for v in values:
        total += v
    return total
 
 
def sum_list(head):
    total = 0
    p = head
    while p is not None:
        total += p.value
        p = p.next
    return total
 
 
def best_ms(work, runs=5):
    best = float("inf")
    for _ in range(runs):
        start = time.perf_counter()
        work()
        best = min(best, (time.perf_counter() - start) * 1000)
    return best
 
 
def build(n):
    values = array.array("q", range(n))
 
    # List 1: node i points to node i + 1, so the walk follows allocation order.
    nodes = [Node(i) for i in range(n)]
    for i in range(n - 1):
        nodes[i].next = nodes[i + 1]
    in_order = nodes[0]
 
    # List 2: its own nodes, linked in a random order, so the walk jumps around memory.
    shuffled_nodes = [Node(i) for i in range(n)]
    order = list(range(n))
    random.Random(42).shuffle(order)
    for i in range(n - 1):
        shuffled_nodes[order[i]].next = shuffled_nodes[order[i + 1]]
    shuffled = shuffled_nodes[order[0]]
 
    return values, in_order, shuffled
 
 
def main():
    for n in (10_000, 200_000, 1_000_000):
        values, in_order, shuffled = build(n)
        sum_array(values)
        sum_list(in_order)
        sum_list(shuffled)
 
        array_ms = best_ms(lambda: sum_array(values))
        in_order_ms = best_ms(lambda: sum_list(in_order))
        shuffled_ms = best_ms(lambda: sum_list(shuffled))
        print(f"n={n:<9} array {array_ms:7.1f} ms   list in allocation order {in_order_ms:7.1f} ms   "
              f"list shuffled {shuffled_ms:7.1f} ms")
        print("  sums agree:", sum_array(values) == sum_list(in_order) == sum_list(shuffled))
 
 
main()

Read the program in four parts.

The data is built first. The array holds the values 0 to n - 1 in order. The two lists hold the same values, but each list has its own set of nodes, so the two chains do not share objects. The first list links node i to node i + 1. The second list follows a random order produced by random.Random(42).shuffle, with a fixed seed so every run uses the same order.

The warm-up runs each sum once before anything is timed. The first run of a function can be slower, because of set-up that happens once. Without the warm-up, the first timed run would include that cost.

best_ms runs the work five times and keeps the fastest. A single run can be slowed by background activity on the computer, such as garbage collection or other programs. Taking the best of several runs gives a steadier number.

The sums are printed and compared, so you can see that all three walks visit every value. A timing that skips the work it measures tells you nothing.

On the machine used to write this lesson, a WSL2 Linux system with Python 3.14.4, one run printed these lines:

n=10000     array     0.1 ms   list in allocation order     0.2 ms   list shuffled     0.2 ms
  sums agree: True
n=200000    array     3.8 ms   list in allocation order     4.3 ms   list shuffled    36.6 ms
  sums agree: True
n=1000000   array    20.1 ms   list in allocation order    25.7 ms   list shuffled   240.0 ms
  sums agree: True

At one million values, the list walked in shuffled order took about nine times longer than the same list walked in allocation order. The two list walks do the same work and visit the same objects, so the difference comes from where the nodes sit in memory.

The array and the list in allocation order are close in this run, and the array is only a little faster. This is the Python difference from a lower-level language. Each step in a Python loop costs a lot of interpreter work, and that work hides part of the cost of reading memory. Also, reading an item from an array creates a new Python integer object for each value, while the list walk reads integers that already exist. The shuffled walk shows the cache cost most clearly, because its extra cost is the cache misses and nothing else.

The exact numbers depend on the machine, the Python version and what else the computer is doing. Your numbers will differ. The ordering of the shuffled walk against the allocation-order walk should stay the same.

A second example: the gap grows with size

A timing run at one size can hide the reason for the gap. The three sizes in the run above show the pattern. At 10,000 nodes, the whole structure is small enough to mostly stay in the cache after the first walk, so the two list walks cost about the same. At 200,000 nodes the list no longer fits in the cache, and the shuffled walk falls behind. At one million nodes, the random jumps cost a trip to RAM on almost every step, and the shuffled walk is about nine times slower than the walk in allocation order.

This is why cache locality matters more as data grows. A small list may look fine in a test. A large list in a real program can be dominated by cache misses.

Common mistakes

Blaming the linked structure for every slow walk. A list built in creation order and walked in that order is much faster than the same list walked in shuffled order. The cost comes from where the nodes sit in memory, not from the links themselves. The timing run above showed about 26 ms for the allocation-order walk and about 240 ms for the shuffled walk, with the same nodes.

Timing the first run only. The first call to a function can include setup costs, so the first number is often wrong. Run the work a few times before you measure, and take the best of several timed runs, as best_ms does.

Assuming a list of numbers is as compact as an array of numbers. A list holds references to separate integer objects, and each object lives somewhere in memory. Summing a list follows a reference to each object. An array stores the numbers themselves in one block.

Forgetting the end of a list. The walk stops when p becomes None. If you read p.value when p is None, the program fails. This program reads the next attribute of a node that has none set:

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None
 
p = Node(1)
print(p.next.value)

It fails with this error (the file path and line numbers will differ):

Traceback (most recent call last):
  File "/home/you/example.py", line 7, in <module>
    print(p.next.value)
          ^^^^^^^^^^^^
AttributeError: 'NoneType' object has no attribute 'value'

The message names the attribute that was read from a None value. The fix is to check p is not None in the loop condition, as sum_list does.

Reading past the end of an array. An array's valid indexes run from 0 to len(values) - 1. This program writes one past the end of a three-item array:

Type nothing into the Input box for this program.

IndexError: array assignment index out of range

Loops such as for i in range(len(values) + 1) cause this error on their last pass. Use range(len(values)) instead. A loop that goes through the items directly, as for v in values, cannot go past the end at all.

Practice

Exercise 1. A program needs to add up one million numbers. It can store them in an array or in a linked list of nodes. Which one is likely to run faster, and why?

Show the answer

The array is likely to run faster. Its values sit side by side, so the loop reads memory in order and most reads are cache hits. Each list node is a separate object, and the walk must read each next reference before it can reach the following value. The list also uses more memory for object headers and references, so the same values take up more cache lines. In Python, the gap can be smaller than this reasoning suggests, because each interpreter step costs a lot, so measure the program that you care about.

Exercise 2. Write sum_even_indexes that adds the values at indexes 0, 2, 4 and so on in a list or an array. Then say why it is cache friendly.

Show the answer

def sum_even_indexes(values):
    total = 0
    for i in range(0, len(values), 2):
        total += values[i]
    return total

It is cache friendly because the loop still moves forward through memory in order. It skips every other value, but each cache line it fetches still holds values that the loop will reach soon after, so most reads stay close to the previous one. The call sum([1, 2, 3, 4, 5][0::2]) gives the same answer, because the slice [0::2] takes every second item from index 0.

Exercise 3. The timing program gives the same sum for both lists. Explain why the order of the nodes does not change the sum.

Show the answer

The sum adds every value in the list once. The shuffled list links the same nodes as the allocation-order list, only in a different order, so the walk visits every node exactly once. Addition does not depend on the order of the terms, so the total is the same. Only the time changes, because the order decides which memory each step reads.

Exercise 4. A colleague writes this timing code and reports that the list is fifty times slower than the array:

start = time.perf_counter()
head = build_list(1_000_000)
total = sum_list(head)
elapsed = time.perf_counter() - start

List two problems with this measurement.

Show the answer

First, the timed part includes build_list, which creates a million objects. Building the list is slow work of its own, so the measured time mixes building with walking. The fix is to build the list before starting the clock. Second, the code runs only once, so it includes any set-up cost, and any garbage collection that happens to run during the timing. The fix is to run a warm-up and take the best of several timed runs.

Exercise 5. Write a function that counts how many values in a linked list are greater than a given limit. Make it safe for an empty list.

Show the answer

def count_above(head, limit):
    count = 0
    p = head
    while p is not None:
        if p.value > limit:
            count += 1
        p = p.next
    return count

For an empty list, head is None, so the loop body never runs and the function returns 0. The check p is not None in the loop condition is what keeps the function from reading a None node.

Summary

• A CPU reads memory through a cache. A hit is fast, and a miss waits for RAM, which is much slower.
• The cache loads a whole cache line at a time, so reading neighbouring memory is cheap.
• An array keeps its values side by side, so a loop over it reads memory in order. A list keeps references to objects that can be anywhere in memory.
• A linked list walk must follow one reference at a time. When the nodes are scattered, most steps are cache misses.
• To compare two data structures fairly, build the data before the clock starts, warm up the code, check that both walks give the same result, and take the best of several runs.