Temporal locality and working sets

A cache only helps with data you read again, and what matters is how soon. This lecture measures that with one number, the reuse distance, and uses it to predict the hit rate of every cache size at once, including the cliff where a loop is just a little too big to fit.

The last two topics were about where lines go. This one is about when they come back. A program that reads a price, does some work, and reads the same price again a moment later is showing temporal locality. The shorter the gap, the better the chance that the line is still in the cache. Think of the books on your desk: a book you used a minute ago is still there, a book you used last month went back to the shelf.

Reading line 5 twice in a row gives distance 0. In the sequence 1, 2, 3, 1 the last read has distance 2, because lines 2 and 3 came in between. Reading line 2 ten times between two reads of line 1 still counts as one line. The code keeps a list of the lines in the order of their last use, most recent last. When a line comes again, the lines after it in the list are exactly the ones used since.

def reuse_distances(lines):    stack = []    out = []    for line in lines:        if line in stack:            position = stack.index(line)            out.append(len(stack) - 1 - position)1            stack.pop(position)        else:            out.append(None)        stack.append(line)    return outprint(reuse_distances([1, 2, 3, 1, 2, 1, 1]))

[None, None, None, 2, 2, 1, 0]

1. 1The lines after this one in the list are exactly the lines used since its last read: their count is the distance.

Here is the useful fact. Take a cache that holds C lines and evicts the least recently used one, whatever the line numbers. At any moment it holds the C different lines used most recently. A read hits exactly when its line is among them, that is, when fewer than C different lines were read since its last use. In other words, the read hits when its reuse distance is smaller than C.

The code below checks the claim. It simulates an LRU cache for capacities from 1 to 4 and also computes the hit rate from the distances alone, with no cache at all. The two columns agree. The distances are computed once, and then they give the hit rate of every cache size.

def lru_hit_rate(lines, capacity):    cache = []    hits = 0    for line in lines:        if line in cache:            hits += 1            cache.remove(line)        elif len(cache) >= capacity:            cache.pop(0)        cache.append(line)    return hits / len(lines)def hit_rate_from_distances(distances, capacity):    hits = sum(1 for d in distances if d is not None and d < capacity)    return hits / len(distances)lines = [1, 2, 3, 1, 2, 3, 4, 1, 2, 3]d = reuse_distances(lines)for capacity in (1, 2, 3, 4):    print(capacity, "lines:", round(lru_hit_rate(lines, capacity), 3), round(hit_rate_from_distances(d, capacity), 3))1

1 lines: 0.0 0.0
2 lines: 0.0 0.0
3 lines: 0.3 0.3
4 lines: 0.6 0.6

1. 1Same numbers in both columns: the distances alone predict the hit rate of every cache size.

The working set of a stretch of reads is the set of different lines they touch. If the working set fits in the cache, the program runs almost entirely from cache. If it is only slightly bigger, LRU can fail completely. Take a loop that reads 48 lines in order, three times. Each line is read again after 47 others, so every reuse distance is 47. A cache of 47 lines or fewer therefore never hits, and a cache of 48 hits on every read after the first pass.

def sweep_lines(n_lines, passes):    return list(range(n_lines)) * passeslines = sweep_lines(48, 3)for capacity in (16, 32, 47, 48):    print(capacity, "lines:", round(lru_hit_rate(lines, capacity), 3))

16 lines: 0.0
32 lines: 0.0
47 lines: 0.0
48 lines: 0.667

A rolling mean computed the slow way reads the last 20 values for every day: it re-reads 19 of the 20 values it read the day before. That is a program with a lot of temporal locality. The code builds the addresses read for the first 600 closes, turns them into lines, and measures the distances, the hit rate for four cache sizes, and the working set of 20 consecutive reads.

def rolling_mean_trace(n, window, elem_bytes):    trace = []    for end in range(window - 1, n):        for position in range(end - window + 1, end + 1):            trace.append(position * elem_bytes)    return tracedef working_set(lines, window):    return max(len(set(lines[i:i + window])) for i in range(len(lines) - window + 1))lines = [address // 64 for address in rolling_mean_trace(600, 20, 8)]d = reuse_distances(lines)print(len(lines), "reads from", len(set(lines)), "lines")for capacity in (1, 2, 4, 8):    print(capacity, "lines:", round(hit_rate_from_distances(d, capacity), 3))print("working set of 20 reads:", working_set(lines, 20), "lines")

11620 reads from 75 lines
1 lines: 0.831
2 lines: 0.831
4 lines: 0.994
8 lines: 0.994
working set of 20 reads: 4 lines

One line is enough for 83% of the reads, because the next value of the array is in the line that was just read. Four lines reach 99.4%. The 75 lines of the whole data set never have to fit: the working set of 20 reads is only 4 lines, so a tiny cache is enough. That is the difference between the size of the data and the size of the working set.

The lab asks for the pieces above, plus the helper that finds the smallest cache for a hit rate, and ends with the study on the real SPY closes.

• Function · questionBuilds on
• reuse_distances(lines)How soon is each line read again?A list in last-use order
• lru_hit_rate(lines, capacity)What does a simulated LRU cache hit?Lines in LRU order
• hit_rate_from_distances(distances, capacity)The same hit rate, without a cache?reuse_distances
• working_set(lines, window)How many lines does a stretch of reads touch?A sliding window
• capacity_for(lines, target)How small can the cache be?reuse_distanceshit_rate_from_distances
• rolling_mean_trace(n, window, elem_bytes)Which addresses does a slow rolling mean read?Plain arithmetic
• study(bars)How local is a rolling mean on the SPY closes?rolling_mean_tracecapacity_for

Next topic: you now know how a layout turns into a trace and a trace into hits and misses. In Array of structs against struct of arrays you use that to choose how to lay out a table of ticks, comparing column reads and whole-row reads in both layouts.