Skip to content
AyoKoding

Overview

Prerequisites

  • Prior topics: 4 · Just Enough Python -- a general "reading code and running experiments" fluency this topic assumes; 19 · Computer Science Foundations -- number systems, two's complement, IEEE-754 floats, endianness, and the stack/heap survey this topic goes on to measure and exploit for real.
  • Tools & environment: a macOS/Linux terminal; a C toolchain (a recent stable clang/gcc); a profiler/perf-style tool to measure cache and cycle behavior (Instruments/dtrace on macOS, perf on Linux); optionally a disassembler to read emitted assembly; Neovim/VSCode with the C LSP.
  • Assumed knowledge: reading and running a small program (topic 4); binary/number representation and complexity intuition (topic 19); reading a typed script to drive experiments (topic 4).

Why this exists -- the big idea

The problem before the solution: reasoning about a flat, uniform memory and a CPU that runs one instruction at a time stopped predicting performance once caches, pipelines, and virtual memory arrived -- the same big-O algorithm now runs an order of magnitude apart depending on how it touches memory. The one idea worth keeping if you forget everything else: memory is a hierarchy and the CPU is fast only when it hits cache -- sequential, cache-friendly access to compact data beats a "clever" algorithm that chases pointers, because a cache miss costs hundreds of cycles.

Cross-cutting big ideas, taught here and then reused for the rest of this curriculum: layering-and-leaks -- this is the layer just under your language -- its cache, page, and word-size behavior leaks upward as performance you must explain; abstraction-and-its-cost -- the "flat memory, one instruction at a time" abstraction is convenient and wrong, and the cost it hides is exactly the 100x gap between a cache hit and a cache miss.

Confirm your toolchain

Every example in this topic is a self-contained C11 file, compiled directly with no build system:

$ clang --version
Apple clang version 17.0.0 (clang-1700.0.13.5)
Target: arm64-apple-darwin24.5.0
$ sysctl -n hw.cachelinesize hw.l1dcachesize hw.l2cachesize hw.ncpu
128
65536
4194304
12

Every example is a complete, self-contained, runnable C11 file colocated under learning/code/, actually compiled and run on this Apple Silicon dev machine to capture its documented output -- every printed value, byte pattern, and timing number on this topic's pages is a genuine, captured transcript, never a fabricated one. Where an example's natural tool is Linux-only (perf, numactl, hugepages), the Linux mechanism is named honestly in prose and the actual runnable verification on this machine uses the macOS equivalent (Instruments/dtrace) or a wall-clock-timing proxy consistent with this topic's own measurement methodology -- never a fabricated hardware- counter reading.

How this topic's examples are organized

  • Beginner (Examples 1-27) -- two's-complement integer bytes and signed vs. unsigned printing, signed-overflow wraparound (and the unsigned-underflow loop bug it causes), IEEE-754 float bits and the 0.1+0.2 != 0.3 comparison hazard, endianness detection and htonl/ntohl round-tripping, struct padding/alignment/packing, pointer arithmetic and row-major array layout, the memory-hierarchy latency survey, a real runtime cache-line-size probe (128 B on this machine, not the common 64 B), sequential-vs-random and small-vs-large working-set timing, and reading emitted assembly (including a genuine RISC-V vs. x86 ISA comparison).
  • Intermediate (Examples 28-57) -- a cache-miss stride sweep, matrix traversal order and AoS-vs-SoA hot loops, working-set cache cliffs, cache-blocked matrix multiply, false sharing and its cache-line-padding fix, prefetch hints, branch-predictable-vs-random data, branchless arithmetic, pipeline dependency chains, loop unrolling and multi-accumulator ILP, TLB pressure, page faults via mmap, virtual addresses, write-heavy cost, cache-associativity conflict strides, SIMD auto-vectorization and hand-written NEON intrinsics, aligned allocation, atomic vs. non-atomic increments, memory-barrier ordering, compiler strength reduction (div-to-shift), hot/cold struct splitting, and a cache-miss-count and CPI/IPC measurement pair.
  • Advanced (Examples 58-80) -- an end-to-end profile-fix-remeasure workflow, a blocked matrix transpose, a struct-of-arrays-plus-SIMD particle simulation, parallel histogram scaling (shared vs. per-thread bins), measured branch-mispredict cost and a lookup-table cure, NUMA and hugepage stories told honestly on a single-package, non-hugepage Apple Silicon dev machine, an integer-overflow allocation security bug and its checked-multiply fix, Kahan summation, the fast-inverse-square-root bit-hack, portable byte-order-explicit serialization, loop interchange, a roofline-style bandwidth-vs-compute comparison, a tuned prefetch distance, a Mermaid pipeline-hazard diagram cross-checked against a real measured stall, superscalar execution-port contention, atomic-vs-mutex throughput, a cache-friendly open-addressing hash map, a vectorized byte search, a profile-guided layout decision record, and a final benchmark harness asserting cache-friendly beats cache-hostile across every kernel in this topic at once.
  • Capstone -- a sensor-averaging kernel: an int/float representation and endianness-hazard toolkit (repr.c), the same averaging kernel built cache-hostile as array-of-structs (cache.c) and then restructured cache-friendly as struct-of-arrays (cache_soa.c), with a written explanation tying the ~3-4x measured, reproducible speedup to the memory hierarchy.

The 25 concepts this topic covers

  • co-01 · Memory hierarchy -- registers -> L1/L2/L3 cache -> DRAM -> disk, each level trading capacity for a latency gap of roughly an order of magnitude.
  • co-02 · Cache lines and blocks -- memory moves between levels in fixed-size lines (typically 64 B; 128 B on Apple Silicon), so touching one byte pulls in its neighbors.
  • co-03 · Spatial locality -- accessing memory addresses near recently-used ones is fast because they already share a cached line.
  • co-04 · Temporal locality -- re-accessing the same address soon is fast because it is still resident in a cache level.
  • co-05 · Cache-miss cost -- a miss that must fetch from a lower level costs tens-to-hundreds of cycles, dwarfing the arithmetic it feeds.
  • co-06 · Cache associativity -- direct-mapped/set-associative/fully-associative placement decides which lines evict each other; power-of-two strides cause conflict misses.
  • co-07 · Write policies -- write-through vs. write-back and write-allocate govern when a store reaches the next level and what a write costs.
  • co-08 · Virtual memory and pages -- each process sees a private virtual address space mapped to physical RAM in fixed-size pages by the MMU.
  • co-09 · TLB -- the translation-lookaside buffer caches recent virtual-to-physical page translations; a TLB miss adds a page-table walk.
  • co-10 · Page faults and swapping -- touching an unmapped/paged-out page traps to the OS, which maps or swaps it in -- a minor fault is cheap, a major (disk) fault is not.
  • co-11 · Two's-complement integers -- signed integers in C use two's complement; the same bits read as signed or unsigned give different values.
  • co-12 · Integer overflow and wraparound -- unsigned overflow wraps modulo 2ⁿ (defined); signed overflow is undefined behavior in C -- a real correctness/security hazard.
  • co-13 · IEEE-754 in C -- float/double are sign/exponent/mantissa bit layouts; rounding error is structural, not a bug.
  • co-14 · Float-comparison hazards -- exact == on floats is unreliable; compare within an epsilon and beware precision loss when magnitudes differ.
  • co-15 · Endianness -- byte order (little- vs. big-endian) differs across machines and the wire; htonl/ntohl convert for portable serialization.
  • co-16 · Struct padding and alignment -- the compiler pads struct fields to their alignment, so field order changes sizeof and misaligned access is slow or faulting.
  • co-17 · Data layout: AoS vs. SoA -- array-of-structs vs. struct-of-arrays decides how a hot loop strides memory; layout beats micro-tuning.
  • co-18 · Instruction-set architecture -- the ISA (x86 / ARM / RISC-V) is the hardware/software contract; RISC vs. CISC is a design-philosophy split.
  • co-19 · Assembly basics -- registers, load/store, and reading emitted assembly reveal what the CPU actually does with your C.
  • co-20 · Pipelining -- the CPU overlaps fetch/decode/execute/memory/writeback stages; data and control hazards force stalls.
  • co-21 · Branch prediction -- the CPU guesses branch outcomes; a mispredict flushes the pipeline (tens of cycles), so predictable or branchless code wins.
  • co-22 · Superscalar and out-of-order -- modern cores issue several instructions per cycle and execute out of order (speculatively), exploiting instruction-level parallelism.
  • co-23 · SIMD vectorization -- SIMD units (SSE/AVX/NEON) apply one operation to a vector of values, the data-parallel path to throughput.
  • co-24 · Memory ordering and atomics -- cache coherence, atomic operations, and memory barriers make multi-core shared memory correct; false sharing silently kills scaling.
  • co-25 · Mechanical sympathy and profiling -- measure, don't guess: a profiler (perf on Linux, Instruments/dtrace on macOS) is the arbiter of every performance claim.

Examples by Level

Beginner (Examples 1–27)

Intermediate (Examples 28–57)

Advanced (Examples 58–80)

← Previous: Overview · Next: Beginner Examples →

Last updated July 16, 2026

Command Palette

Search for a command to run...