5.9High-Level Language Models

Why languages need memory models too

Everything so far — chapters 3, 4, and 5 — has defined memory models at the hardware/low-level-software interface: what software authors may expect, what hardware implementors may do. The same two questions arise one level up: a high-level language memory model hll memory model A high-level language's memory contract (Java, C++), built on SC for DRF with atomic/synchronized tagging plus bounded semantics for racy programs. defined in Chapter 5 — open in glossary specifies (a) what HLL software authors may expect and (b) what implementors of compilers, runtime systems, and hardware may do:

Many HLLs were born in a largely single-threaded world and simply omitted a memory model — there isn’t one in Kernighan and Ritchie. Java was perhaps the first mainstream language with a memory model, and its first version had real issues (Pugh: “fatally flawed”). Memory models were then re-specified for Java (2005) and specified for C++, and the cornerstone of both is a familiar one — SC for DRF, provided in part by Sarita Adve’s co-authorship of all three papers.

SC for DRF at the language level

To allow synchronization races but not data races, programmers tag variables that might race as synchronization — the atomic keyword, or implicit locks via Java’s monitor-like synchronized methods. Implementations are then free to reorder or even eliminate memory accesses between synchronization accesses. Figure 5.7’s example:

B = 2*A;
D = C - A;

L1: r1 = A;
X1: r2 = 2*r1;
S1: B = r2;
L2: r3 = C;
L3: r1 = A;
X2: r2 = r3-r1;
S2: D = r2;

L1,L3: r1 = A;
X1: r2 = 2*r1;
S1: B = r2;
L2: r3 = C;
/* L3 moved */
X2: r2 = r3-r1;
S2: D = r2;

The reordering is correct because, with SC for DRF, no other thread “can be looking.” And register allocation has plenty of company: constant propagation, common subexpression elimination, loop fission/fusion, loop-invariant code motion, software pipelining, and instruction scheduling all reorder memory accesses. Because SC for DRF allows them, compilers and runtimes produce code with performance comparable to single-threaded code.

When programs race anyway

What if a program has data races data race Two conflicting data operations that appear in the global memory order without an intervening pair of transitively conflicting synchronization operations by the same threads. defined in Chapter 5 — open in glossary — by accident or on purpose? Another thread could then observe a non-SC execution: in Figure 5.7c, a core C2 could update A and C, and C1 — with A parked in r1 — could observe the update to C but not to A. HLL models must handle this, with different motivations:

• Java requires security guarantees for all programs — it can never leave racy behavior undefined.
• C++, for performance, supports low-level atomics — synchronization operations weaker than SC.

So both must specify behavior in all cases, with three goals: (1) allow all optimizations for high-performance DRF programs, (2) unambiguously specify the allowed behavior of all programs, and (3) keep that specification simple. In the book’s judgment, the 2005 Java model made substantial progress — arguably succeeding on (2), mostly succeeding on (1) (it disallowed some compiler optimizations), but not on (3). One “dark corner” every compiler and runtime author must confront: regardless of optimizations, a load must never return a value out of thin air out-of-thin-air A load result with no producing store, arising from speculative load-buffering cycles; forbidden by dependency-induced ordering. defined in Chapter 5 — open in glossary (§5.6.1’s load-buffering example) — and that is not the only complexity. Satisfying all three goals at once remains an open, actively researched problem in C++. Fortunately, most programmers can use SC for DRF and never meet the dark corners.

Must relaxed languages mean relaxed hardware?

Java and C++ adopt the relaxed, SC-for-DRF approach. Should the hardware underneath be relaxed too? On one hand: relaxed hardware maximizes performance, and compilers/runtimes need only translate the HLL’s synchronization into the hardware’s low-level operations and FENCEs. On the other: SC and TSO already perform well, and stronger hardware lets compilers generate more portable code without fences from incomparable models. The debate is not settled, but one thing is clear: relaxed HLL models do not require relaxed hardware.