W03: From program objects to memory behavior

Prerequisites and observable goals#

The central question: which layer makes the promise?#

A source program names objects. A compiler selects representations and instructions. An operating system maps virtual memory and schedules threads. A processor moves data through caches and executes instructions under its architectural rules. These layers interact, but a fact from one is not automatically a guarantee from another. “The address looks the same” does not establish that an object is still alive. “The processor can load this width” does not make a compound increment atomic in the language.

Begin a memory argument with three questions. Who owns the object? How long does it live? Which aliases may access or mutate it? Only then ask where bytes are placed and how quickly they can be accessed. A diagram with rectangles and arrows is a representation of those relationships, not a literal view of every compiler’s stack layout.

A lifetime failure that a plausible address can hide#

Consider a C++ vector and a reference to its first element:

std::vector<int> values{10, 20};
int& first = values[0];
// Suppose a later push_back triggers reallocation.
values.push_back(30);
// Using first is now invalid if that reallocation occurred.

The reference designates an element object in the old allocation. A reallocation constructs elements in new storage and invalidates references into the former storage. It does not redirect the existing reference to the new first element. Whether this particular insertion reallocates depends on capacity; do not infer the capacity from an initializer’s length. The conditional wording is essential.

This is an ownership schematic; actual addresses, element movement, and allocation details are implementation-dependent. Keeping an index and reacquiring a reference after mutation can solve this particular problem if the element identity and index remain valid. An index can also become stale after erasure or reordering. Reserve capacity only when you can establish a sufficient bound; it is not a general lifetime proof. [CPP]

Virtual addresses are not physical addresses#

In a simplified paged model with page size $P$, split a nonnegative virtual byte address $a$ as

The quotient is the virtual page number and the remainder is the byte offset. A page table maps the virtual page to a physical frame number $F$, giving physical address $FP+(a\bmod P)$. Translation preserves the offset within a page; it need not preserve adjacency between different pages.

For page size 4096 bytes and virtual address 0x2345, page number is 2 and offset 0x345=837. If page 2 maps to frame 9, the physical address is 0x9345. The hexadecimal decomposition works especially neatly because the page size is a power of 16. An unmapped page means this toy translation is unavailable; a real OS may fault, allocate, reject permission, or take another documented action. Our model has no permissions, translation cache, demand paging, or multi-level page tables. It teaches the decomposition, not the full operating system.

A cache model exposes locality and conflict#

For cache-line size $B$ bytes, memory block number is $b=\lfloor a/B\rfloor$. In a direct-mapped cache of $L$ lines, line index is $b\bmod L$ and tag is $\lfloor b/L\rfloor$. A valid line with the matching tag produces a hit; otherwise the access replaces that line and is a miss. This model assumes an initially empty read cache and ignores timing, coherence, stores, prefetching, associativity, and replacement choices beyond direct mapping.

Take $B=32,L=2$ and addresses $0,8,32,64,0$. Blocks are $0,0,1,2,0$ and indices $0,0,1,0,0$. Access 0 misses, 8 hits the already loaded block, 32 misses into the other line, 64 conflicts with block 0, and the final 0 misses because block 2 displaced it. A tiny working set can still suffer conflicts. A real associative cache may behave differently; measure actual programs only after validating outputs and recording the hardware/workload.

The connection to structure-of-arrays versus array-of-structures is now concrete. Reading just one field from many records may transfer unrelated fields too. But if a computation uses all fields together, separating them can add streams and index work. A layout recommendation needs an access pattern, element sizes, compiler behavior, and measurement. There is no unconditional theorem that one fashionable layout is always faster.

Publication: visibility is not just unique work assignment#

Suppose workers read an immutable array and each writes a different preallocated result element. Construct the input and results before starting threads; never resize the result vector while they run; join all workers before reading outputs. These choices establish lifetimes and disjoint ownership. An atomic counter can hand out distinct indices with relaxed ordering because it allocates work, not because it publishes changing payload data. Thread creation and joining supply the relevant synchronization for that design.

Now change the design: a producer writes a payload and sets a ready flag while a consumer waits. Merely changing the flag to an atomic does not automatically synchronize the non-atomic payload under every memory order. A release store paired with an acquire load that observes it can establish a happens-before relationship for preceding writes. Both the matching observation and object lifetime matter. A relaxed flag alone supplies atomic flag operations, not publication of the payload. Tests that happen to pass on one machine cannot replace the language memory-model argument. [CPP]

Performance is a hypothesis about a valid program#

First establish that the measured programs implement the same contract and have defined behavior. Then isolate the variable being changed: layout, allocation, tiling, batching, or scheduling. Record input distribution, warmup, repetitions, setup inclusion, build flags, and output checks. A measurement confounded by a different algorithm, smaller output, or invalid pointer cannot support the intended layout claim. Advanced G06 returns to arithmetic intensity and scaling after these model boundaries are clear.

Independent practice#

F foundation C standard course work T transfer S optional stretch L runnable lab or project. Attempt the complete set before opening its solutions.

Complete solutions: W03#

Compare the first step where your work differs. A corrected answer is not yet an independent success.

Open every solution

"""W03: schematic address translation and a direct-mapped cache, not hardware timing."""


def translate(address, page_map, page_size=4096):
    if type(address) is not int or address<0 or type(page_size) is not int or page_size<=0:
        raise ValueError("nonnegative address and positive page size required")
    if any(type(x) is not int or x<0 for pair in page_map.items() for x in pair):
        raise ValueError("page numbers must be nonnegative integers")
    page,offset=divmod(address,page_size)
    if page not in page_map:raise KeyError("unmapped virtual page")
    return page_map[page]*page_size+offset


def direct_mapped(addresses,line_size=32,lines=2):
    if any(type(x) is not int or x<=0 for x in (line_size,lines)) or lines>65536:
        raise ValueError("bounded positive cache dimensions required")
    tags=[None]*lines
    result=[]
    for address in addresses:
        if type(address) is not int or address<0:raise ValueError("invalid address")
        block=address//line_size
        index=block%lines
        tag=block//lines
        hit=tags[index]==tag
        tags[index]=tag
        result.append({'address':address,'line':index,'tag':tag,'hit':hit})
    return result


if __name__=='__main__':
    print(translate(0x2345,{2:7}))
    print(direct_mapped([0,64,0,64]))

Retention and readiness#

Draw the owner, alias, and lifetime before discussing addresses. Explain a cache conflict without using “slow memory” as a substitute for the mapping. For concurrency, identify the exact synchronizes-with or join relationship, not just the presence of an atomic somewhere in the program.