Follow a store through write-through and write-back caches

When you trace a store through a cache, ask when the updated byte reaches backing memory. The answer depends on the write policy. A second, separate question is whether a store that misses should bring a line into the cache. Mixing those decisions makes write traces difficult to explain and can hide the moment when the only current copy of a value is still dirty in a cache.

This lesson uses one serial, direct-mapped cache with four eight-byte lines and a sixty-four-byte backing store. Addresses range from zero through sixty-three, and stored values are unsigned bytes. The backing store initially contains its own addresses as values. We will execute a small Python data model, not measure a CPU or run a hardware cache-maintenance instruction. You need the idea of a cache line and integer division to follow the index calculations.

Separate propagation from allocation

Under write-through, a store to a resident line updates that line and sends the changed byte to backing memory. Our model completes that byte transfer immediately. Real implementations may buffer writes, so the policy name alone does not establish when another observer can see the update or how many bus transactions occur.

Under write-back, a store to a resident line updates the cached byte and marks the line dirty. Backing memory can retain its earlier value. Before a dirty line is replaced, our model copies the entire eight-byte line back. A clean line can be replaced without a data writeback. The dirty bit records that writeback is required; it need not prove that every byte differs from memory.

Chris Terman’s cache lecture explains the role of dirty state in avoiding unnecessary writebacks. The pinned gem5 cache implementation also distinguishes dirty writebacks from clean evictions. It includes coherence and configuration details absent from this model, so we will not infer actual traffic from its function names alone.

Allocation answers the write-miss question. With write allocation, a miss fetches the whole containing line before modifying the requested byte. Without write allocation, this model writes the byte directly to backing memory and leaves cache contents alone. In particular, a conflicting write miss does not evict an unrelated resident line just to bypass the cache.

These decisions can be specified independently. The historical Dinero IV library manual, d4.3 in its upstream documentation archive, exposes separate wallocf and wbackf policies. We will implement four explicit combinations. This does not claim that a particular processor offers all four, or that the Python model executes Dinero IV.

Follow a dirty value through two conflicts

Use five operations: write nine to address one, read address one, write ten to address one, write seven to address thirty-three, then read address one. Addresses one and thirty-three lie in blocks starting at zero and thirty-two. Both blocks select cache index zero because their block numbers are zero and four in a four-line direct-mapped cache.

With write-back and write allocation, the first store misses, fetches bytes zero through seven and changes cached byte one to nine. Backing byte one remains one. The read hits and returns nine. The second store hits, changes the cached value to ten and leaves the same line dirty. No lower-level byte has yet been written for either store.

The store at thirty-three misses. Before loading its block, the cache writes the old dirty block back, so backing byte one becomes ten. It then fetches bytes thirty-two through thirty-nine and changes cached byte thirty-three to seven. That second block is dirty while backing byte thirty-three still contains thirty-three.

The final read of address one misses again. It writes the dirty second block back, then fetches the first block and returns ten. Backing byte thirty-three is now seven. The sequence required three eight-byte fills and two eight-byte writebacks: twenty-four bytes read from backing memory and sixteen bytes written to it.

View full-size image ↗

Execute the byte values as well as the hit decisions

A tag-only model cannot establish that a dirty value survives eviction. This Python 3 model stores actual bytes and counts payload bytes crossing its single cache-to-memory boundary. Reads always allocate. flush writes back dirty lines and marks them clean while keeping them valid; it does not invalidate the cache or model persistent storage.

class ByteCache:
    def __init__(self, writeback, allocate):
        if type(writeback) is not bool or type(allocate) is not bool:
            raise ValueError("policy switches must be booleans")
        self.writeback, self.allocate = writeback, allocate
        self.memory = list(range(64))
        self.lines = {}
        self.read_bytes = self.write_bytes = 0

    def _copy_back(self, index):
        line = self.lines.get(index)
        if line is not None and line["dirty"]:
            base = line["base"]
            self.memory[base:base + 8] = line["data"]
            self.write_bytes += 8
            line["dirty"] = False

    def access(self, operation, address, value=None):
        if operation not in ("R", "W"):
            raise ValueError("operation must be R or W")
        if type(address) is not int or not 0 <= address < 64:
            raise ValueError("address must be a built-in integer from 0 to 63")
        if operation == "W":
            if type(value) is not int or not 0 <= value < 256:
                raise ValueError("a write requires an unsigned byte")
        elif value is not None:
            raise ValueError("a read takes no value")
        base = address // 8 * 8
        index = (address // 8) % 4
        line = self.lines.get(index)
        hit = line is not None and line["base"] == base
        if not hit:
            if operation == "W" and not self.allocate:
                self.memory[address] = value
                self.write_bytes += 1
                return False, None
            self._copy_back(index)
            line = {"base": base, "data": self.memory[base:base + 8],
                    "dirty": False}
            self.lines[index] = line
            self.read_bytes += 8
        offset = address - base
        if operation == "R":
            return hit, line["data"][offset]
        line["data"][offset] = value
        if self.writeback:
            line["dirty"] = True
        else:
            self.memory[address] = value
            self.write_bytes += 1
        return hit, None

    def flush(self):
        for index in self.lines:
            self._copy_back(index)


events = [("W", 1, 9), ("R", 1), ("W", 1, 10),
          ("W", 33, 7), ("R", 1)]
for writeback in (False, True):
    for allocate in (False, True):
        cache = ByteCache(writeback, allocate)
        answers = [cache.access(*event) for event in events]
        assert [value for _, value in answers if value is not None] == [9, 10]
        cache.flush()
        assert cache.memory[1] == 10 and cache.memory[33] == 7
        print(writeback, allocate, cache.read_bytes, cache.write_bytes)

In the printed order, the read/write byte totals are eight/three, twenty-four/three, eight/ten and twenty-four/sixteen. All four policies return the same two read values and finish with the same memory contents after writeback. Their intermediate backing-memory values and traffic differ.

The source-level distinction between cleaning and discarding is worth preserving. In the pinned gem5 base-cache code, the writeback visitor copies dirty data and clears dirty state; the invalidation visitor is separate and warns about dirty lines. Our flush is a precisely defined model operation, not a portable spelling for either real hardware operation.

Bypassing one write need not disturb another dirty line

With no write allocation, the first store writes nine directly to backing byte one. The following read misses and loads its block. Under write-back, the next store changes cached byte one to ten, leaving backing byte one at nine.

The store at thirty-three now bypasses the cache. It writes seven directly to memory without replacing the dirty block at index zero. The final read of address one therefore hits and returns ten. Only the ending flush copies that line back, making backing byte one equal ten. Traffic is one eight-byte fill, two bypassed byte writes and one eight-byte writeback: eight bytes read and ten written.

Under write-through without allocation, the cache follows the same placement decisions but writes the hit store through as well. It has no dirty line to flush, so its three stores transfer three payload bytes in total. Different bypass rules need separate effects: evicting the resident line would make the final read miss, while cleaning the dirty line would change when its bytes reach backing memory without necessarily changing the read’s hit status.

View full-size image ↗

Count the complete interval before judging the tradeoff

Write-back sends more bytes than write-through in this small example because each dirty eviction transfers eight bytes after only a few byte stores. That does not make write-through universally cheaper. Repeated writes to a resident block can be combined into one later writeback, while a write-through implementation’s buffering and merging also matter in practice.

Try the following exercise after defining the class. Read address one once to make it resident, then overwrite it one hundred times and flush. Both policies finish with value ninety-nine. Under the declared transfer rules, write-through sends one hundred bytes and write-back sends eight. Both read eight bytes for the initial fill.

for writeback in (False, True):
    cache = ByteCache(writeback, True)
    cache.access("R", 1)
    for value in range(100):
        cache.access("W", 1, value)
    cache.flush()
    assert cache.memory[1] == 99
    assert cache.read_bytes == 8
    assert cache.write_bytes == (8 if writeback else 100)
    print(writeback, cache.write_bytes)

Ending the measurement before dirty data is written back would omit deferred work. Likewise, treating each payload byte as one physical bus transaction would add an assumption the model never made. Real transfers have widths, queues and possible merging; the byte totals here establish neither runtime nor power consumption.

Finally, dirty does not mean invalid. In our single-requester model, the cache’s dirty copy is the current value. Discarding that copy before writeback can lose stores, whereas reading backing memory directly can see an older value. Multiple processors, DMA, coherence, memory ordering and durability introduce additional contracts. This exercise isolates data propagation and allocation so that those later questions start from explicit state rather than an ambiguous policy label.