Modern Processors and Performance

From textbook pipeline to real core

The five-stage pipeline in the pipelining lesson is the right mental model to start with, but a modern laptop or server core looks very different. It fetches and decodes several instructions per cycle, breaks complex instructions into simpler micro-operations, renames registers, keeps a few hundred instructions in flight, executes them out of order on a dozen or so execution units, and retires them in order. It predicts branches with remarkable accuracy and prefetches data before you ask for it.

This lesson connects that machinery to the code you write. First you follow one instruction end to end through a modern core. Then you look at heterogeneous designs with performance and efficiency cores. The second half is practical: how to reason about performance as a programmer (cache misses, branch mispredictions, data layout), how to read the output of perf, and a worked optimisation of matrix multiplication with timings measured on a real machine.

Interviewers for systems, backend and performance-sensitive roles commonly ask: what happens when an instruction executes on a modern CPU, why sorted data can make a loop faster, what IPC means, what a branch misprediction costs, the difference between array-of-structs and struct-of-arrays, and how you would find and fix a hot loop.

The iron law of performance

Every performance argument eventually comes back to one equation:

CPU time = instruction count × CPI × clock period
         = instructions × (cycles / instruction) × (seconds / cycle)

• Instruction count depends on the algorithm, the compiler and the ISA.
• CPI (cycles per instruction), or its inverse IPC (instructions per cycle), depends on the microarchitecture and on how well your code uses it: cache misses, mispredictions and dependences raise CPI.
• Clock period depends on the chip and its current frequency.

Worked example: comparing two designs

A program executes 2 × 10^9 instructions at CPI 1.5 on a 3 GHz core: 2 × 10^9 × 1.5 ÷ (3 × 10^9) = 1.0 s.

Two alternatives for a different program:

• Machine A: 10^9 instructions, CPI 2.0, 4 GHz: 10^9 × 2.0 ÷ (4 × 10^9) = 0.50 s.
• Machine B: 1.2 × 10^9 instructions, CPI 1.2, 3 GHz: 1.2 × 10^9 × 1.2 ÷ (3 × 10^9) = 0.48 s.

B wins despite the lower clock and more instructions. No single factor (clock speed, instruction count) tells you the answer on its own.

How a modern core executes one instruction

Take a single x86-64 instruction that adds a value from memory to a register:

add rax, [rbx + 8]     ; rax = rax + memory[rbx + 8]

The same journey applies, with different names, to Arm and RISC-V cores. Here it is in order.

+---------------- FRONT END (in order) -----------------+
| branch predictor -> fetch (I-cache, I-TLB)            |
|   -> pre-decode / instruction queue                    |
|   -> decoders (or micro-op cache) -> micro-op queue    |
+--------------------------+----------------------------+
                           v
+------------- RENAME / ALLOCATE (in order) ------------+
| register alias table, free list, ROB entry,           |
| load/store queue entries                               |
+--------------------------+----------------------------+
                           v
+------------- BACK END (out of order) -----------------+
| scheduler(s) --> ports: ALU ALU ALU LOAD LOAD STORE    |
|                         BRANCH  VECTOR/FP ...          |
| load/store unit <--> L1 D-cache, D-TLB                 |
+--------------------------+----------------------------+
                           v
+--------------- RETIRE (in order) ---------------------+
| reorder buffer head: commit results, free old regs,    |
| release stores to the cache                            |
+-------------------------------------------------------+

1. Branch prediction and fetch

Before the core even knows what instruction is at the next address, the branch predictor guesses where the program will go. Each cycle it predicts the next fetch address, using a branch target buffer (BTB, a cache of branch locations and targets), direction predictors that learn patterns from branch history, and a return stack buffer that predicts function returns.

The fetch unit reads a block of bytes (for example 16 or 32 bytes) from the L1 instruction cache, translating the address through the I-TLB. On an I-cache miss, fetch stalls while the line comes from L2.

2. Decode into micro-ops

x86 instructions have variable length (1 to 15 bytes), so the core first finds instruction boundaries (pre-decode), then decoders translate each instruction into one or more micro-operations (micro-ops or µops): simple, fixed-format, RISC-like operations the back end executes. Our instruction becomes two:

add rax, [rbx + 8]
  -> uop1: load  tmp  <- [rbx + 8]
  -> uop2: add   rax  <- rax + tmp

(Many cores keep the pair "fused" through part of the pipeline to save bandwidth, then split them for execution.) Complex instructions are expanded by a microcode ROM into longer sequences.

Decoding x86 is power-hungry, so recent cores keep a micro-op cache (decoded instruction cache) of already-decoded micro-ops; hot loops are served from it, skipping the decoders. Arm and RISC-V cores also crack some instructions into micro-ops but have a much easier decode job because instructions are fixed length (or nearly so).

Micro-ops wait in a micro-op queue that decouples the front end from the back end.

3. Rename and allocate

Each cycle, a group of micro-ops (the "rename width", often 4 to 8 on recent cores) is:

• Renamed: architectural registers (rax, rbx, tmp) are mapped to physical registers via the register alias table. rax as a destination gets a fresh physical register from the free list. This removes false dependences, as covered in parallelism and multicore.
• Allocated: each micro-op gets a reorder buffer (ROB) entry, the load gets a load queue entry, a store would get a store queue entry.
• Dispatched to a scheduler (also called reservation station or issue queue).

Some operations finish right here. Register-to-register moves are often eliminated by just pointing two architectural names at the same physical register, and zeroing idioms like xor eax, eax are recognised as having no input dependence.

4. Schedule and execute

The scheduler holds micro-ops until their source operands are ready. Each cycle it wakes up micro-ops whose inputs have just been produced and selects the oldest ready ones for each execution port. A port connects to one or more execution units: integer ALUs, multipliers, branch units, vector and floating-point units, load units, store-address and store-data units.

For our example:

1. The load micro-op waits only for rbx. When rbx is ready, it issues to a load port. The address generation unit computes rbx + 8, the D-TLB translates it, and the L1 data cache is read. On an L1 hit the data arrives in about 4 or 5 cycles.
2. Meanwhile, the load is checked against the store queue: if an older store to the same address is still waiting, its data is forwarded directly (store-to-load forwarding). If older stores have unknown addresses, the core usually speculates that they do not overlap (memory disambiguation) and replays the load if it guessed wrong.
3. When the load's result is broadcast, the add micro-op wakes up and issues to an ALU on the next cycle or so; one cycle later its result is ready for any dependent micro-op.

If the load misses all the way to DRAM, the add waits hundreds of cycles, but independent micro-ops behind it keep executing, up to the limit of the ROB and scheduler sizes. That window (a few hundred micro-ops on recent big cores) is how a core finds independent work during a cache miss: memory-level parallelism, several outstanding misses at once.

5. Complete and retire

A finished micro-op marks its ROB entry complete. Retirement walks the ROB head in program order: once both micro-ops of our add are complete and every older instruction has retired, the instruction retires. The new physical register becomes the committed value of rax; the previous physical register for rax goes back to the free list. If anything faulted (a page fault on the load) the exception is raised precisely at this point, and everything younger is flushed. Stores are written to the L1 cache only after they retire, from the store buffer.

Branch prediction in a little more depth

The simplest useful predictor is a 2-bit saturating counter per branch: states strongly-not-taken, weakly-not-taken, weakly-taken, strongly-taken. One surprise does not flip a strong prediction, which handles loop exits well.

2-bit saturating counter

   taken        taken        taken
 +------+  -> +------+  -> +------+  -> +------+
 |  SN  |     |  WN  |     |  WT  |     |  ST  |
 +------+ <-  +------+ <-  +------+ <-  +------+
   not taken   not taken    not taken
 predict: not taken  <------|------>  taken

Modern predictors combine many such counters indexed by the branch address and by the recent history of branch outcomes, at several history lengths (the TAGE family is the best known design in the literature). On typical code they mispredict only a small fraction of branches. What they cannot predict is genuinely random data, as you will see shortly.

Heterogeneous cores: big.LITTLE, P-cores and E-cores

A big out-of-order core is fast but power-hungry; a small in-order or narrow out-of-order core does less per cycle but uses far less energy per instruction. Heterogeneous (asymmetric) multicore chips include both, so the system can run demanding work on big cores and background work on small ones.

• Arm big.LITTLE (later DynamIQ) introduced the idea in phones: clusters of "big" and "LITTLE" cores implementing the same ISA, so a thread can migrate between them.
• Apple silicon pairs performance cores with efficiency cores in the M-series and A-series chips.
• Intel has used P-cores (performance) and E-cores (efficiency) in client processors since Alder Lake (12th generation Core), with a hardware Thread Director that gives the OS scheduler feedback about which threads benefit from which core type.

Key points:

• Same ISA is essential. Because threads migrate freely, both core types must run the same instructions. On Alder Lake, the E-cores lacked AVX-512, so AVX-512 was disabled on the P-cores in shipping configurations.
• The OS scheduler matters. It has to place latency-critical, foreground threads on performance cores and background work on efficiency cores, using hints such as QoS classes (macOS) or thread priorities and hardware feedback (Windows, Linux).
• Benchmarks get trickier. A thread's speed depends on which core it lands on; pinning threads or measuring on a quiet system matters.

Reasoning about performance as a programmer

You cannot see micro-ops from your code, but you can predict their consequences. Most performance problems in ordinary code come from a short list.

Cache misses

From the cache memory lesson: an L1 hit costs a few cycles, a DRAM access a few hundred. A loop that misses to DRAM on every iteration is limited by memory, not by arithmetic. Signs and fixes:

• Pointer chasing (linked lists, trees of small nodes, hash maps with chaining): each load's address depends on the previous load, so the core cannot overlap misses. Prefer contiguous arrays, B-tree-like wide nodes, or open addressing.
• Large strides (column-wise access of row-major arrays, walking one field of large structs): wasted bytes in every line.
• Working set larger than the cache: restructure to process blocks that fit (tiling, below).
• TLB misses when touching many pages randomly: consider huge pages, covered in main memory and virtual memory hardware.

Branch mispredictions

A misprediction throws away all work after the branch, roughly 10 to 20 cycles on modern cores (the front-end depth plus refill).

Worked example: CPI cost of mispredictions. Suppose 20 percent of instructions are branches, 5 percent of those are mispredicted, and each misprediction costs 15 cycles:

extra CPI = 0.20 × 0.05 × 15 = 0.15

On a core that would otherwise run at CPI 0.5 (IPC 2), that is a 30 percent slowdown.

The classic demonstration sums the elements of an array that pass a threshold, first in random order and then after sorting:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N (1 << 24)

static double seconds(void) {
    struct timespec t;
    clock_gettime(CLOCK_MONOTONIC, &t);
    return t.tv_sec + t.tv_nsec / 1e9;
}

static int cmp(const void *a, const void *b) {
    return *(const int *)a - *(const int *)b;
}

static long sum_big(const int *v) {
    long sum = 0;
    for (int rep = 0; rep < 10; rep++)
        for (int i = 0; i < N; i++)
            if (v[i] >= 128)          /* unpredictable if v is random */
                sum += v[i];
    return sum;
}

int main(void) {
    int *v = malloc(sizeof(int) * N);
    srand(1);
    for (int i = 0; i < N; i++) v[i] = rand() % 256;

    double t0 = seconds();
    long s1 = sum_big(v);
    double t1 = seconds();
    qsort(v, N, sizeof(int), cmp);
    double t2 = seconds();
    long s2 = sum_big(v);
    double t3 = seconds();

    printf("random order: %.3f s (sum %ld)\n", t1 - t0, s1);
    printf("sorted order: %.3f s (sum %ld)\n", t3 - t2, s2);
    free(v);
    return 0;
}

Measured on an Apple M2 laptop with Apple clang:

gcc -O0:  random order: 0.81 - 0.83 s    sorted order: 0.22 s
gcc -O1:  random order: 0.055 s          sorted order: 0.055 s
gcc -O2:  random order: 0.013 s          sorted order: 0.013 s

At -O0 the if is a real branch. With random values it goes either way with 50 percent probability, so the predictor is wrong about half the time; after sorting, the branch is not-taken for the first half and taken for the second, and the predictor is almost always right. That made the same work about 3.8 times faster.

At -O1 and -O2 the difference disappears: the compiler replaced the branch with a branch-free conditional select (and at -O2 also vectorised the loop with SIMD), so there was nothing left to mispredict. That is the real lesson: an unpredictable branch on data is expensive, and the fixes are to make it predictable (sort or partition data), or to make it branch-free (conditional moves, arithmetic masks, SIMD), which optimising compilers often do for you in simple cases. Always measure the optimised build you actually ship.

Data-oriented design

Data-oriented design means laying out data according to how it is accessed, not how it is conceptually grouped. The best-known pattern is choosing struct of arrays (SoA) over array of structs (AoS) for hot loops that touch only a few fields.

Array of structs (AoS): one 64-byte particle per cache line
| x y z vx vy vz mass id name...... | x y z vx vy vz mass id name...... |
  ^       ^                            only 8 of 64 bytes are used

Struct of arrays (SoA): each field contiguous
x : | x0 x1 x2 x3 x4 ... x15 | x16 ...   every byte in each line is used
vx: | vx0 vx1 vx2 ... vx15   | ...

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 4000000

/* Array of structs: 64 bytes per particle, but the loop needs only x and vx. */
struct particle {
    float x, y, z;
    float vx, vy, vz;
    float mass;
    int id;
    char name[32];
};

/* Struct of arrays: each field in its own contiguous array.
   Only the two fields this demo uses are allocated. */
struct particles {
    float *x, *vx;
};

static double seconds(void) {
    struct timespec t;
    clock_gettime(CLOCK_MONOTONIC, &t);
    return t.tv_sec + t.tv_nsec / 1e9;
}

int main(void) {
    struct particle *a = calloc(N, sizeof *a);
    struct particles s;
    s.x = calloc(N, sizeof(float));
    s.vx = calloc(N, sizeof(float));
    for (int i = 0; i < N; i++) a[i].vx = s.vx[i] = 1.0f;

    double t0 = seconds();
    for (int step = 0; step < 20; step++)
        for (int i = 0; i < N; i++) a[i].x += a[i].vx * 0.01f;
    double t1 = seconds();
    for (int step = 0; step < 20; step++)
        for (int i = 0; i < N; i++) s.x[i] += s.vx[i] * 0.01f;
    double t2 = seconds();

    printf("sizeof(struct particle) = %zu bytes\n", sizeof(struct particle));
    printf("array of structs: %.3f s\n", t1 - t0);
    printf("struct of arrays: %.3f s\n", t2 - t1);
    printf("check %.1f %.1f\n", a[N - 1].x, s.x[N - 1]);
    return 0;
}

Measured on the same M2 with gcc -O2, three runs:

sizeof(struct particle) = 64 bytes
array of structs: 0.130 - 0.133 s
struct of arrays: 0.013 - 0.014 s

About 10 times faster for the same arithmetic. In AoS, each particle's x and vx sit in a 64-byte struct, so the loop drags 256 MB through the memory system per step to use 32 MB. In SoA, every byte fetched is used, and the contiguous float arrays vectorise cleanly. AoS is still the right choice when code typically uses most fields of one object together; the point is to choose the layout for the hot path. Related techniques: splitting hot and cold fields, using smaller types, and storing indexes instead of pointers.

Other habits that matter

• Avoid needless dependences. Summing into one accumulator creates a chain where each add waits for the previous one. Using several independent accumulators (or letting the compiler vectorise) lets the out-of-order core run them in parallel.
• Keep hot code small. Huge inlined functions and scattered hot paths cause I-cache and micro-op-cache misses.
• Be careful with sharing across threads. False sharing (see parallelism and multicore) and contended atomics turn into coherence traffic.
• Measure first. Intuition about where time goes is often wrong; profilers are not.

Measuring with perf

On Linux, perf reads the processor's hardware performance counters: registers that count events like cycles, instructions retired, branch mispredictions and cache misses with very little overhead. (On macOS, Instruments with its CPU Counters template plays the same role; Intel VTune and AMD uProf are vendor tools.)

The two most common commands:

perf stat ./program            # count events for the whole run
perf record -g ./program       # sample where time is spent (with call graphs)
perf report                    # browse the samples by function
perf annotate                  # see hot instructions inside a function

Reading perf stat output

The output below is illustrative: it shows the format and plausible, internally consistent numbers for the naive matrix multiply from the next section on a hypothetical 3 GHz x86 Linux machine. It was not captured on a real run (the measurements in this lesson were made on macOS, where perf does not exist), so treat the values as a teaching example, not a benchmark.

 Performance counter stats for './matmul_naive':

          1,302.45 msec task-clock            #    0.999 CPUs utilized
                 3      context-switches      #    2.303 /sec
                 0      cpu-migrations        #    0.000 /sec
             6,213      page-faults           #    4.770 K/sec
     3,907,350,000      cycles                #    3.000 GHz
     4,316,000,000      instructions          #    1.10  insn per cycle
     1,076,500,000      branches              #  826.5 M/sec
         1,120,000      branch-misses         #    0.10% of all branches
     2,150,000,000      L1-dcache-loads       #    1.651 G/sec
     1,080,000,000      L1-dcache-load-misses #   50.23% of all L1-dcache accesses

       1.303812000 seconds time elapsed

How to read it, line by line:

• task-clock and CPUs utilized: CPU time used; about 1.0 means a single busy thread.
• context-switches, cpu-migrations: near zero means the OS did not disturb the run.
• page-faults: first touches of the program's memory (mostly minor faults as pages are allocated); 6,213 pages × 4 KiB is roughly the 24 MB of the three matrices.
• cycles and the derived GHz: 3,907,350,000 cycles in 1.302 s = 3.0 GHz.
• instructions and insn per cycle: 4,316,000,000 ÷ 3,907,350,000 = 1.10 IPC. A core that can retire 4 or more per cycle is mostly waiting.
• branches and branch-misses: 0.10 percent, so branches are not the problem (a loop branch is highly predictable).
• L1-dcache-load-misses: 50 percent of loads miss L1. That is the smoking gun: one of the two loads in the inner loop (B[k][j], walking down a column) misses on nearly every iteration.

The diagnosis is "memory-bound because of the access pattern", which points straight at the fix. On the optimised versions you would expect IPC to rise well above 2 and the L1 miss rate to drop to a few percent. Exact event names vary by CPU; perf list shows what your machine supports. Many teams also use the top-down method (perf stat --topdown on supported Intel CPUs), which splits pipeline slots into front-end bound, back-end bound (memory or core), bad speculation and retiring.

Worked optimisation: matrix multiplication

Matrix multiplication, C = A × B for N × N matrices, performs 2N^3 floating-point operations (N^3 multiplies and N^3 adds) on only 3N^2 numbers. That ratio means it could reuse each loaded value many times, but only if the loop order and data layout let the caches see that reuse. It is the standard example for loop optimisation.

The full program below contains three versions: the textbook loop, a reordered loop and a tiled (blocked) loop. Each prints its time, its rate in GFLOP/s (billions of floating-point operations per second) and a checksum so you can confirm all three compute the same result.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define N 1024
#define B 64   /* tile size: three 64x64 double tiles = 96 KiB */

static double A[N][N], Bm[N][N], C[N][N];

static double seconds(void) {
    struct timespec t;
    clock_gettime(CLOCK_MONOTONIC, &t);
    return t.tv_sec + t.tv_nsec / 1e9;
}

static double checksum(void) {
    double s = 0;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++) s += C[i][j];
    return s;
}

/* Version 1: textbook i-j-k. The inner loop walks Bm down a column. */
static void naive_ijk(void) {
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++) {
            double sum = 0;
            for (int k = 0; k < N; k++) sum += A[i][k] * Bm[k][j];
            C[i][j] = sum;
        }
}

/* Version 2: i-k-j. The inner loop walks Bm and C along rows. */
static void reordered_ikj(void) {
    memset(C, 0, sizeof C);
    for (int i = 0; i < N; i++)
        for (int k = 0; k < N; k++) {
            double a = A[i][k];
            for (int j = 0; j < N; j++) C[i][j] += a * Bm[k][j];
        }
}

/* Version 3: i-k-j on B x B tiles so the working set stays in cache. */
static void tiled(void) {
    memset(C, 0, sizeof C);
    for (int ii = 0; ii < N; ii += B)
        for (int kk = 0; kk < N; kk += B)
            for (int jj = 0; jj < N; jj += B)
                for (int i = ii; i < ii + B; i++)
                    for (int k = kk; k < kk + B; k++) {
                        double a = A[i][k];
                        for (int j = jj; j < jj + B; j++) C[i][j] += a * Bm[k][j];
                    }
}

static void run(const char *name, void (*f)(void)) {
    double t0 = seconds();
    f();
    double t = seconds() - t0;
    printf("%-14s %6.3f s  %5.2f GFLOP/s  checksum %.0f\n",
           name, t, 2.0 * N * N * N / t / 1e9, checksum());
}

int main(void) {
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++) {
            A[i][j] = (i + j) % 7;
            Bm[i][j] = (i * j) % 5;
        }
    run("naive i-j-k", naive_ijk);
    run("reordered i-k-j", reordered_ikj);
    run("tiled i-k-j", tiled);
    return 0;
}

The tiled code assumes N is a multiple of B; production code handles the leftover edges.

Step 1: understand why the naive loop is slow

In the i-j-k order, the innermost loop varies k:

• A[i][k] walks along row i: consecutive addresses, good spatial locality.
• Bm[k][j] walks down column j: each step jumps N × 8 = 8 KB (for N = 1024), so every access touches a new cache line, and only 8 bytes of each line are used before it is evicted.
• sum stays in a register.

So roughly one of every two loads misses L1, which is exactly what the illustrative perf output showed. The column stride is also a power of two, so the lines all map to a small number of cache sets (conflict misses, from the cache memory lesson) and each touches a different 4 KiB page, stressing the TLB.

Step 2: reorder the loops (i-k-j)

Swapping the two inner loops changes nothing about the arithmetic but everything about memory access. Now the innermost loop varies j:

• C[i][j] and Bm[k][j] both walk along rows: consecutive addresses.
• A[i][k] is fixed for the inner loop and kept in a register.

Every cache line fetched is fully used, the hardware prefetcher sees two clean sequential streams, and the inner loop vectorises with SIMD.

Step 3: tile (block) the loops

For large N, even the reordered version has a capacity problem: for each i, the inner loops stream through all of Bm (8 MB for N = 1024), which does not stay in the L1 or L2 cache, so Bm is reloaded from farther away for every row of C.

Tiling (loop blocking) splits the matrices into B × B tiles and does all the work on a small group of tiles while they are in cache.

C (tile ii,jj) += A (tile ii,kk) × B (tile kk,jj)

      kk                    jj                    jj
    +----+----+         +----+----+          +----+----+
 ii |####|    |      kk |####|    |       ii |####|    |
    +----+----+    x    +----+----+    ->    +----+----+
    |    |    |         |    |    |          |    |    |
    +----+----+         +----+----+          +----+----+
   A: one tile row     B: one tile column    C: one tile

With B = 64 and 8-byte doubles, one tile is 64 × 64 × 8 = 32 KiB, so the three tiles in use total 96 KiB, small enough to stay in a typical L2 cache (and largely in a large L1). Each element loaded into cache is reused B times before it is evicted, instead of once.

Step 4: measure

All three versions were compiled with gcc -O2 (Apple clang 21) and run on an Apple M2 laptop. Two runs at N = 1024:

And one run at N = 2048 (eight times the work):

All versions printed identical checksums, so they compute the same result.

Step 5: interpret the numbers

1. Loop order dominated. Simply swapping two loops gave 8 times at N = 1024 and 22 times at N = 2048. The naive version got worse per operation as N grew (1.7 down to 0.59 GFLOP/s), because at N = 2048 the 16 KB column stride defeats the caches and TLB even more thoroughly.
2. Tiling added a further 10 to 18 percent here. On this machine the gain over the reordered loop is modest because the M2 has large caches and aggressive prefetching, so the streaming i-k-j loop was already doing well. On processors with smaller caches, or with code that is otherwise more compute-efficient (where memory becomes the limit), tiling typically matters more.
3. Tile size matters. B = 64 was best; B = 128 (three 128 KiB tiles, 384 KiB in use) was slower than no tiling at all, because the working set no longer fit in the faster cache level, and B = 32 added loop overhead without enough reuse benefit. The best tile size depends on the cache sizes, so it is chosen by measurement (or automatically, by libraries).
4. Still far from peak. Fifteen GFLOP/s is a fraction of what this chip can do. Optimised BLAS libraries (Apple Accelerate, OpenBLAS, Intel MKL) add multi-level tiling for registers, L1 and L2, explicit SIMD, matrix packing and multithreading, and are typically many times faster again. The practical advice: understand why tiling works, then call a library.

Interview questions

Q1. What is the iron law of processor performance?

CPU time = instruction count × CPI × clock period. Instruction count depends on the algorithm, compiler and ISA; CPI on the microarchitecture and how well the code uses caches and predictors; clock period on the hardware. Improving one factor often worsens another, so you must compare the product.

Q2. What are micro-ops, and why do x86 processors use them?

Micro-ops are simple, fixed-format internal operations that the execution core actually runs. x86 instructions are variable-length and can combine memory access with arithmetic, so the decoder translates each into one or more micro-ops, letting the back end be a RISC-like out-of-order engine. A micro-op cache stores decoded micro-ops so hot loops skip the expensive decode step.

Q3. Walk through what happens to add rax, [rbx+8] in a modern core.

The branch predictor and fetch unit bring the bytes from the I-cache; the decoder splits it into a load micro-op and an add micro-op. Rename maps rax to a new physical register and allocates ROB and load-queue entries. The load issues when rbx is ready, computes the address, translates it in the D-TLB and reads L1 (or gets forwarded data from an older store). The add then issues to an ALU, and both retire in order from the ROB, committing the new rax.

Q4. What does IPC tell you, and what is a "good" IPC?

IPC is instructions retired per cycle, the inverse of CPI. A wide modern core can retire four or more instructions per cycle, so an IPC near 1 or below on a hot loop usually means it is stalled, often on memory or mispredictions, while IPC above 2 or 3 suggests the core is busy. What is good depends on the workload; compare against the same code after a change.

Q5. Why can processing a sorted array be faster than an unsorted one?

If a loop contains a data-dependent branch such as if (v[i] >= 128), random data makes the branch unpredictable and causes frequent mispredictions, each costing 10 to 20 cycles. Sorted data makes the branch outcome change only once, so the predictor is almost always right. Compilers can sometimes remove the branch with conditional moves or SIMD, in which case the order stops mattering.

Q6. What does a branch misprediction cost, and how do you estimate its effect on CPI?

The core discards all work after the branch and refetches from the correct path, typically 10 to 20 cycles. Extra CPI = branch fraction × misprediction rate × penalty; for example 0.2 × 0.05 × 15 = 0.15 cycles per instruction.

Q7. Array of structs versus struct of arrays?

AoS stores each object's fields together; SoA stores each field in its own contiguous array. When a hot loop uses only a few fields across many objects, SoA wastes no cache-line bytes and vectorises easily; in the measured example it was about ten times faster. AoS is better when code uses most fields of one object together.

Q8. What are P-cores and E-cores, and what problem do they create for software?

They are performance cores (large, fast, power-hungry) and efficiency cores (small, energy-efficient) implementing the same ISA on one chip. The OS scheduler must decide which threads go where, using priorities, QoS hints and hardware feedback. They make performance less predictable and require identical instruction support on both core types.

Q9. What is loop tiling and why does it help?

Tiling breaks loops over large arrays into blocks whose data fits in a cache level, and finishes all the work on those blocks before moving on. Each loaded element is reused many times while still cached, cutting capacity misses. For matrix multiply, the tile size is chosen so three tiles fit in L1 or L2.

Q10. Why is the i-j-k matrix multiply slower than i-k-j in C?

In i-j-k, the inner loop reads B[k][j] down a column, so each access is a row apart in memory and lands in a different cache line and often a different page. In i-k-j, the inner loop reads B[k][j] and writes C[i][j] along rows, so accesses are contiguous, every fetched byte is used, prefetching works and the loop vectorises.

Q11. What do you look at first in perf stat output?

Instructions and cycles to get IPC, then branch-misses as a percentage of branches, then cache misses (L1 and last-level). Low IPC with high cache-miss rates suggests memory-bound code; low IPC with a high branch-miss rate suggests unpredictable control flow. Then use perf record and perf report to find which functions and instructions are responsible.

Q12. What is memory-level parallelism?

It is having several cache misses outstanding at the same time. Out-of-order cores keep executing independent instructions after a miss, issuing further independent loads, so their latencies overlap. Pointer chasing destroys it because each address depends on the previous load.

Q13. What is store-to-load forwarding?

When a load reads an address that an older, not-yet-committed store in the store buffer has written, the core forwards the store's data directly to the load instead of waiting for the store to reach the cache. If the core guessed that a load did not depend on an older store with an unknown address and was wrong, it replays the load.

Key takeaways

• CPU time = instructions × CPI × clock period; compare the product, never one factor.
• A modern core: predict, fetch, decode into micro-ops (or hit the micro-op cache), rename, schedule out of order onto execution ports, and retire in order from the ROB.
• Loads use the D-TLB, L1, the store queue (forwarding) and speculation about older stores; out-of-order windows hide latency and overlap misses.
• Heterogeneous chips pair performance and efficiency cores with the same ISA; the scheduler decides placement.
• Unpredictable data-dependent branches cost about 10 to 20 cycles per miss; sort data or go branch-free, and check what the compiler already did.
• Lay out data for the hot loop: SoA was about 10 times faster than AoS in the measured test.
• Use perf stat for IPC, branch and cache-miss rates, and perf record/report to find the hot code.
• For matrix multiply, loop interchange gave 8 to 22 times and tiling a further 10 to 18 percent on an Apple M2; tile size must match the caches, and tuned libraries go much further.

Next lesson

Continue with COA interview questions.