Overview

Faster storage technology is physically more expensive per byte (SRAM for caches vs. DRAM vs. disk), so a machine can afford only a little of the fastest tier and progressively more of each slower one -- capacity grows as latency grows. An L1 hit costs a handful of cycles; a DRAM access costs on the order of a hundred-plus cycles -- roughly two orders of magnitude apart.

Memory moves between cache levels in fixed-size blocks (cache lines) because fetching a whole line amortizes the fixed per-transaction overhead of a memory access and exploits spatial locality -- neighboring bytes are usually needed soon. Code that hardcodes a 64 B line (common on x86) will under-count how many elements share a line on a 128 B-line machine, misjudging both false-sharing risk and prefetch/stride math -- line size must be detected or documented per target, never assumed universal.

Spatial locality predicts that an address near a recently-accessed one is likely already cached, because it shared that address's cache line. Row-major storage places a[i][j] and a[i][j+1] adjacent in memory, so a row-major (inner loop over j) traversal walks each cache line fully before moving on; column-major traversal jumps a full row's stride between consecutive accesses, landing in a different, likely-uncached line almost every step.

Temporal locality predicts that re-accessing a recently-touched address is fast because it's still resident in a cache level. Once the working set exceeds a level's capacity, earlier entries get evicted to make room for newer ones before they're re-read, so the "recently touched" data is no longer there when it's needed again -- the benefit degrades to whatever the next (slower) level provides.

A modern core can retire multiple arithmetic instructions per cycle, but a DRAM fetch has a fixed, much larger physical latency (on the order of a hundred-plus cycles) that arithmetic throughput cannot hide unless there's independent work to overlap with it. A tight loop with one dependent miss per iteration is bottlenecked by that miss latency, not by the handful of cycles its arithmetic would otherwise cost.

Direct-mapped caches map each address to exactly one line slot, so two frequently-used addresses that happen to map to the same slot will repeatedly evict each other (a conflict miss) even though the cache overall has free capacity. Set-associative placement gives each address a small set of candidate slots, absorbing some of these collisions. A power-of-two stride can make every accessed address map to the same (or very few) sets, causing conflict misses regardless of overall cache occupancy.

Write-through propagates every store immediately to the next level (simpler, more memory traffic); write-back holds the modified data in cache and only flushes it to the next level on eviction (fewer transfers, but requires tracking "dirty" lines). Write-allocate governs what happens on a write MISS specifically: whether the line is first fetched into cache before being modified (so a subsequent read/write to the same line hits) or written directly to the next level without caching it.

A private virtual address space lets the OS isolate processes from each other (one process can't read/corrupt another's physical memory by address alone), relocate physical memory freely, and present a uniform address layout to every process regardless of what's physically resident. The MMU (memory management unit), consulting per-process page tables, translates each virtual address to its physical counterpart in fixed-size pages.

The TLB (translation-lookaside buffer) caches recent virtual-to-physical page translations, so a hit skips the full page-table walk. Randomly touching many distinct pages exhausts the TLB's limited entry count, forcing frequent TLB misses (each requiring a multi-level page-table walk) -- whereas confining accesses to a few pages keeps their translations resident in the TLB across repeated touches.

Both trap to the OS because the accessed virtual page isn't currently mapped. A minor fault is resolved cheaply in memory (e.g. the page is already resident elsewhere, or is a fresh zero-fill/first-touch page) -- microseconds. A major fault requires reading the page's data from disk/swap -- milliseconds, many orders of magnitude slower, and the real performance emergency when a workload's resident set exceeds available RAM.

A bit pattern has no inherent sign -- it's the TYPE of the read that decides the interpretation. C's signed integers use two's-complement encoding, where the high bit contributes a negative weight (-2^(n-1)) instead of a positive one; reinterpreting the exact same bits as unsigned makes that same high bit contribute +2^(n-1), so -1 (all-ones bits) reads back as the unsigned type's maximum value.

The C standard defines unsigned arithmetic as modulo 2^n (wraparound is guaranteed, specified behavior), but leaves signed overflow explicitly undefined -- the compiler is allowed to assume it never happens and optimize accordingly, which can silently eliminate an overflow check the programmer intended, rather than just producing a "wrong but predictable" wrapped value. A size computation like n * record_size that overflows can therefore under-allocate a buffer in a way that's both a correctness bug and, in unsigned code, a reliably-wrapped (and thus exploitable) value.

Sign (1 bit), biased exponent, and mantissa (fractional significand) together encode a sign-magnitude-with-scaling representation. 0.1, 0.2, and 0.3 each already round to the nearest representable binary value the moment the literal is parsed -- before any arithmetic runs -- so the sum of two already-rounded values doesn't have to land on the rounding of the third; this is structural to finite binary floating point, not an implementation defect.

Because floating-point arithmetic accumulates rounding error at nearly every operation, two mathematically-equal expressions computed via different paths (or the same expression computed twice with different compiler optimizations) can land on adjacent-but-different bit patterns. An epsilon-tolerant comparison (fabs(a - b) < epsilon) should replace exact equality -- and the epsilon itself needs care when comparing values of very different magnitudes, since a fixed absolute epsilon can be too loose for tiny values and too tight for huge ones.

Little-endian stores a multi-byte value's least-significant byte first; big-endian stores the most-significant byte first. The same bytes read in the wrong order produce a different, still plausible-looking number rather than an error. htonl/ntohl convert a 32-bit value between host byte order and network byte order (which is defined as big-endian), so code that serializes across machines/the wire doesn't silently assume its own host's order.

The compiler inserts padding bytes so each field starts at an address satisfying its own alignment requirement (and so the whole struct's size is a multiple of its strictest member's alignment, for correct behavior in arrays). Declaring a large-alignment field after a small one can force padding between them that a largest-first field order would have avoided -- the same fields, reordered, can produce a smaller sizeof.

Array-of-structs interleaves every field of a record together, so a loop reading only one hot field still pulls each record's ENTIRE cache line (including cold fields it never touches) into cache -- wasted memory bandwidth. Struct-of-arrays stores that one field as its own dense array, so every fetched cache line is 100% useful data for that loop, cutting memory traffic roughly in proportion to how much of the original record was cold.

An ISA (x86, ARM, RISC-V, ...) is the hardware/software contract: the set of instructions, registers, and encoding rules a compiler can target and a CPU implementation must execute correctly -- it's an abstraction boundary, not an implementation. RISC (Reduced Instruction Set Computer) favors a small set of simple, uniform, fixed-latency instructions (favoring pipelining and compiler-driven optimization); CISC (Complex Instruction Set Computer) favors fewer, denser instructions that can each do more work (e.g. a memory operand built into an arithmetic instruction), trading instruction count for per-instruction complexity.

The C source describes WHAT the computation should produce; the assembly reveals HOW the compiler actually implemented it on the target ISA -- which values live in registers vs. spill to the stack, whether a division became a shift, whether a loop got vectorized or unrolled, and exactly which ABI argument registers hold the function's parameters -- all invisible in the source itself.

Pipelining overlaps the fetch/decode/execute/memory/writeback stages of consecutive instructions, so a new instruction can enter the pipeline every cycle even though any single instruction still takes several cycles to fully complete. A data hazard occurs when one instruction needs a result a prior, still-in-flight instruction hasn't produced yet (forcing a stall or forwarding); a control hazard occurs when a branch's outcome isn't known yet but the pipeline must decide what to fetch next.

A pipelined, speculative CPU guesses a branch's outcome and starts executing down that path before the branch actually resolves; if the guess is wrong, every speculatively-executed instruction must be discarded and the correct path re-fetched from scratch -- a pipeline flush costing roughly the pipeline's depth in cycles. Sorted/predictable data lets the branch predictor learn a stable, repeating pattern (near-perfect prediction); random data defeats prediction, paying the mispredict penalty on close to every branch.

A superscalar core has multiple parallel execution units (ports) and can issue several independent instructions in the same cycle; out-of-order execution additionally lets the core run a LATER instruction ahead of an EARLIER one that's stalled waiting on an operand, as long as no dependency is violated. A dependent chain (each result feeding the next) forces strictly sequential execution regardless of how many ports are free; splitting the same total work into independent chains (e.g. multiple accumulators) lets the core actually use its parallel execution capacity.

A SIMD instruction applies one operation to several data lanes packed into a single wide register in one instruction (e.g. adding 4 floats at once), instead of one value per instruction. Vectorizing a loop requires loading several CONSECUTIVE, same-type values into one vector register; array-of-structs interleaves different fields between the values a vectorized loop would want side by side, forcing an expensive gather instead of a simple contiguous load, while struct-of-arrays already stores the needed values contiguously.

An atomic operation guarantees the read-modify-write happens as one indivisible step from every other core's point of view, so concurrent increments from multiple threads can't interleave and lose an update; a plain (non-atomic) increment can be interrupted mid-sequence by another thread's conflicting update, silently dropping increments (a data race). False sharing is a DIFFERENT problem -- two threads updating logically-independent variables that happen to share one cache line still serialize on that line's coherence traffic, even though there's no actual data race, because the cache-coherence protocol treats the whole line as the unit of ownership.

Modern out-of-order, superscalar, speculatively-executing CPUs are complex enough that back-of-envelope cycle-counting intuition routinely gets the actual bottleneck wrong; a profiler is the arbiter that turns a plausible-sounding performance story into a verified one. perf stat/perf record are Linux-kernel-only; on macOS the equivalent tooling is Instruments (the "CPU Counters"/"Time Profiler" templates) or dtrace.

This is signed integer overflow (co-12) -- the true product exceeds INT_MAX and wraps into negative range, which is undefined behavior in C even though it "looks like" a predictable wrap on most toolchains. The fix is to compute the multiplication in a wider type (int64_t or long long) or use a checked-multiply builtin (__builtin_mul_overflow) that detects the overflow before it happens, not to add a business-logic check for a negative result after the fact.

Restructure from array-of-structs to struct-of-arrays (co-17) -- store position and velocity as their own dense arrays, separate from the rarely-touched cold fields. The update loop then streams only the bytes it actually needs per cache line instead of dragging along a dozen unrelated fields on every fetch, cutting memory traffic roughly in proportion to how much of the original struct was cold for that loop.

False sharing (co-02, co-24) -- if the two counters happen to be allocated close enough together to share one cache line, every increment from either thread invalidates the other core's cached copy of that line via the cache-coherence protocol, even though there's no actual race on the DATA. The fix is padding each counter onto its own separate cache line (or otherwise separating them in memory).

An endianness mismatch (co-15) -- the raw cast reads the 4 bytes in the LOCAL machine's byte order, but the wire protocol's bytes are in the REMOTE device's (big-endian) order; the same bytes reinterpreted in the wrong order produce a different, still-plausible-looking integer instead of an obvious error. The fix is ntohl() (or an explicit byte-order-aware unpack) on every multi-byte field crossing a network boundary, never a raw pointer cast.

Floating-point comparison hazard (co-13, co-14) -- the accumulated rounding error from however average was computed almost certainly left it a few ULPs away from the exact literal 100.0, even though it prints as "100" at typical printf precision. The fix is an epsilon-tolerant comparison (fabs(average - 100.0) < epsilon), with the epsilon sized to the values' actual magnitude.

Plausible and likely correct (co-16) -- placing the largest-alignment field (double, needing 8-byte alignment) first, followed by the two 1-byte char fields, minimizes the padding the compiler must insert between fields (the original order likely pads after flag to align value, and again at the end to align the struct's own size); reordering fields never changes the VALUES stored, only their byte offsets, so it's a safe, pure layout optimization as long as nothing in the codebase depends on the struct's specific byte offsets (e.g. hand-rolled serialization) without recomputing them.

Branch prediction (co-21) -- mostly-sorted data produces a branch outcome pattern the CPU's predictor can learn and predict correctly almost every time, avoiding the tens-of-cycles pipeline- flush cost of a misprediction; randomly shuffled data defeats the predictor, paying that cost on close to every comparison, even though the total INSTRUCTION count (comparisons) is identical between the two runs.

The compiler already performs this exact strength-reduction optimization itself (co-19, co-25) -- at any optimization level above -O0, dividing a signed or unsigned integer by a compile-time-known power of two is routinely lowered to a shift instruction automatically, because the compiler can prove the two are equivalent for that specific divisor. The hand-written shift and the compiler-optimized division compile to the same (or near-identical) assembly, so no measurable difference is expected.

Not a bug -- expected behavior (co-08, co-10). mmap reserves virtual address space essentially instantly without necessarily backing every page with physical memory yet; the first WRITE to each previously-untouched page traps as a (cheap) minor page fault, which the OS resolves by mapping in a fresh physical page on demand. The burst is exactly this "first touch" cost being paid once per page as the buffer is actually used, not a sign of memory pressure or swapping (which would instead show up as MAJOR faults).

Cache locality (co-01, co-03, co-17), not algorithmic complexity -- open addressing stores probe candidates contiguously in one backing array, so consecutive probes during a lookup tend to land in the same or an adjacent cache line; separate chaining follows a linked list of heap-allocated nodes, where each node hop is very likely a fresh, uncached memory address (a pointer chase). Identical average probe COUNTS can still produce very different wall-clock times because one access pattern is cache-friendly and the other isn't.

perf is Linux-kernel-only (co-25); on macOS the direct equivalents are Instruments' "CPU Counters" template (a GUI profiler) or dtrace (also privileged and not trivially scriptable in CI). For a comparable, CI-friendly signal without either, a before/after wall-clock timing comparison around a suspected layout fix (the same best-of-N clock_gettime methodology used throughout this topic) is a legitimate proxy -- it doesn't report a raw miss COUNT, but it directly measures the thing the miss count was a proxy for in the first place: elapsed time.

No (co-01, co-05, co-25) -- bytes-moved and wall-clock time are related but not identical quantities. The original workload wasn't purely memory-bound at every stage (allocation, accumulator arithmetic, and the machine's own memory-level parallelism/prefetching can already hide some of the AoS version's cost), and a large but finite reduction in wasted bytes fetched doesn't scale linearly into wall-clock time once other costs (that didn't change) become a larger share of the remaining total. A real, reproducible, correctly-attributed 3-4x speedup with unchanged results is a genuine win; the theoretical byte-count ratio is an upper bound on the win, not a prediction of the measured one.