Interlude
What the CPU does when your code reads memory
pgmesa · · 70 min read
Part of Rebuilding PyTorch (an interlude)
- Why I rebuilt PyTorch's core from scratch
- What a PyTorch tensor really is
- Interlude: What the CPU does when your code reads memory
- How PyTorch walks a tensor of any shape
- How PyTorch prepares the loop of every operation
- How a PyTorch kernel uses the vector registers of every CPU
- How PyTorch sums a tensor, and splits the work between threads
- How PyTorch computes gradients
- How PyTorch runs the same operations on a GPU
Hi everyone! This article is a bit different from the rest of the series. It does not rebuild any piece of PyTorch. It is the hardware background that the other articles need: what a cache is, why reading memory in order is so much faster than jumping around, what a SIMD register is, and what a thread really gets when it runs on a core. The other articles link to its sections whenever a result depends on one of these things, so they do not have to explain the theory again every time.
While I was writing the other articles, I kept finding myself explaining theory along the way, just so that a conclusion or a measurement would make sense. It felt like it needed one central place, where I could explain it in more detail without bloating the articles or repeating myself, and that the rest of the series could point to. Often the conclusion was something like “the transpose is six times slower because a column no longer fits in L1”, and I felt that the version of me from three and a half years ago would have read it, nodded, and then gone off to search the internet for what it meant, because he would not really have understood it. This article is that place: the basic computer architecture the series relies on, to save that search and make the rest easier to follow. There are much better references, dedicated to these topics, that explain each section here in more detail and with more rigor (some are listed at the end); this one only tries to give what the series needs, measured on the same machine as everything else. I hope it saves someone as curious as I was then some time and some questions. And it was good for me too: until you sit down to explain something, you do not know whether you really understand it XD
You do not need to read it in one go, or now. Each section stands on its own: read the ones that interest you, or skip the whole article and come back when another one links here and something does not add up. If you already know what an L2 miss or an AVX2 register is, you can go straight to the next article.
Before you start. This article only assumes What a PyTorch tensor really is: shapes, strides and views. A little C/C++ helps in a few experiments, and everything else is tables.
This is the path the article follows:
- A CPU is fast, memory is not.
- The cache levels.
- Cache lines and the prefetcher.
- Many loads at once, and bandwidth.
- Pages and the TLB.
- Reading with a stride.
- Lines that come back: reuse.
- Where a line can go: cache sets.
- SIMD: one instruction, several numbers.
- Inside a core: running ahead, and guessing branches.
- Cores and threads.
And at the end, the key takeaways.
All the measurements are from the machine of the whole series: a Ryzen 7 9700X, a Zen 5 with 8 cores, and 32 GiB of DDR5 running at 4800 MT/s in two channels. The C++ experiments are in raxismemory_levels.cpp, and raxismemory.py builds them and runs the tensor experiments with NumPy, PyTorch and Raxis. I ran them in November 2026, with NumPy 2.5.4, PyTorch 2.14.1 and Raxis 0.5.0, on Windows 11 25H2 (MSVC 19.44) and Ubuntu 24.04 under WSL2 (GCC 13.3), on the same machine, and the numbers are the same within a few percent, except where I say otherwise.
A note on units. Sizes that the hardware builds in powers of two, the caches, the pages, the RAM and the blocks of the C++ experiments, are written in KiB, MiB and GiB: 1 KiB is 1024 bytes, 1 MiB is 1024 KiB. Sizes of tensors and arrays, and bandwidths, are written in KB, MB and GB, powers of ten: a million floats are 4,000,000 bytes, 4 MB, and 1 GB/s is a billion bytes per second.
1. A CPU is fast, memory is not
A core of this CPU runs at up to 5.5 GHz, so one cycle takes less than 0.2 ns, and in each cycle it can start several instructions. One of them can add eight floats at once. A float in main memory, the RAM, is about 100 ns away: around 500 cycles in which the core could have done thousands of additions.
If every read went to the RAM, nothing would be fast. Almost everything in this article is a way the hardware avoids that wait:
- It keeps copies of recently used data in small, fast memories next to the core, the caches (section 2).
- It moves memory in blocks, not number by number, and it guesses which blocks you will want next (section 3).
- It does not wait for one read before starting the next (section 4).
- It works on several numbers per instruction, and on several cores at once (sections 9 and 11).
And the rest of the article is about the cases where these tricks stop working, because those are the cases the other articles keep running into.
2. The cache levels
A cache is a small memory, much faster than the RAM, that keeps copies of the data the core used recently. When the core reads an address, it looks first in the smallest and fastest cache, the L1. If the data is not there, which is called a miss, it looks in the next one, the L2, then in the L3, and only then in the RAM. Each level is larger and slower than the one before:
These are the sizes of this CPU. On Linux, lscpu -C prints them; on macOS, sysctl hw.l1dcachesize hw.l2cachesize hw.cachelinesize; on Windows, the CPU page of the Task Manager shows the totals.
| Level | Size | Who has one | Ways (section 8) |
|---|---|---|---|
| L1 data | 48 KiB | each core | 12 |
| L2 | 1 MiB | each core | 16 |
| L3 | 32 MiB | the whole CPU | 16 |
| RAM | 32 GiB | the whole machine |
A cache is also full almost all the time, so every line that comes in has to take the place of one that was there. Which one leaves is decided by the hardware, not by the program, and the rule is close to “the line that has gone unused the longest” (least recently used, LRU). It is only close: tracking the exact order would cost too much on every access, so real caches approximate it with a few bits per line, and the exact rule is rarely documented (AMD does not publish Zen 5’s). For this article the approximation is enough: a line used again soon stays, and a line used again only after many other lines have passed through the level is almost always gone. Section 8 shows that a line cannot go just anywhere in the cache either.
How slow is each level? To measure it, the experiment needs reads that cannot be helped by any of the tricks of the next sections. The code is in C++, in raxismemory_levels.cpp, and it builds a chain: a block of memory split into 64-byte pieces, one per cache line, each holding the address of the next piece. The figure shows its three steps with a block of eight pieces:
Two details of the steps matter. The shuffle is Sattolo’s algorithm, which always gives one single circle through every piece; an ordinary shuffle can close several small circles, and the loop could keep going around one that fits in the L1, whatever the size of the block. And the lap without the clock leaves the block in a cache if it fits, so the runs measure that cache and not the first trip from the RAM. Of the three runs the fastest counts, because noise, an interrupt or another program, can only make a run slower.
The point of the chain is that the address of each read is the value returned by the read before it. The core cannot even ask for the next piece until the current one has arrived, so there is never more than one read on its way, and the time per step is exactly how long one line takes to arrive from wherever it lives. With the random order, the CPU cannot guess the next piece either. Growing the block from 16 KiB to 256 MiB, each level shows up as a step:
| Size of the chain | Random order | Where it lives |
|---|---|---|
| 32 KiB | 0.72 ns | L1 |
| 256 KiB | 2.53 ns | L2 |
| 512 KiB | 2.53 ns | L2 |
| 4 MiB | 9.0 ns | L3 |
| 8 MiB | 10.5 ns | L3 |
| 16 MiB | 19 ns | L3, and the start of section 5 |
| 64 MiB | 81 ns | RAM |
| 256 MiB | 100 ns | RAM |
At 5.5 GHz that is about 4 cycles for the L1, 14 for the L2, 50 for the L3 and more than 500 for the RAM. On Linux the RAM row is 109 ns, and the rest is the same. Between the steps the numbers mix two levels: a 16 MiB chain still fits in the L3, but it already pays for something else that section 5 explains, the translation of addresses.
Why does a block larger than a level get nothing from that level, if the level always holds the lines read last? Because of the order in which the chain comes back to them. In a circle, a piece is read again only after every other piece of the block has been read, so when a 256 MiB chain comes back to a line, 256 MiB of other lines have gone through the caches since, and the line was pushed out long before. That is true of the in-order chain of section 3 too: the circle is the same, only the order of the jumps changes. A real cache is not an exact LRU, and some caches keep part of a block that does not fit instead of replacing all of it, which is probably part of why 64 MiB, twice the L3, costs 81 ns and not the 100 of 256 MiB.
The rule of thumb to keep: each level is around 3 to 10 times slower than the one before, and the RAM is about a hundred times slower than the L1.
3. Cache lines and the prefetcher
The pieces of the chain were 64 bytes for a reason. The caches do not hold single numbers: they hold cache lines, blocks of 64 bytes aligned to a multiple of 64. When you read one float, the whole line that contains it comes in: the 64-byte block from the multiple of 64 just below its address, so it can bring bytes before the float as well as after it. That is 16 floats, and if the code reads them in order, the next 15 reads of that line are free. 64 bytes is the line size of almost every x86 and ARM CPU today; Apple’s M chips report 128 (sysctl hw.cachelinesize).
Where each line starts is fixed by the hardware, but where a tensor starts is not, and PyTorch and Raxis choose it on purpose: their CPU allocators only return addresses that are multiples of 64 (pytorchalignment.h, raxiscpu_allocator.cpp). This is called an aligned allocation: aligned_alloc in C, _aligned_malloc on Windows, alignas(64) for a C++ type. The main reason is SIMD (section 9): a load of 16 floats, 64 bytes, from an element whose index is a multiple of 16 never straddles two lines, and a load that does touches two lines and costs more (and two pages, if it crosses into the next one). Two side effects help too: the first line holds only the tensor’s own bytes, and no other object shares a line with the tensor, so two threads writing to two different tensors never compete for the same line. The cost is small, at most 63 bytes of padding per tensor. And it only holds where the memory starts: a view like x[3:] starts 12 bytes later, so the kernels never count on it, and use the unaligned load instructions, which on today’s CPUs cost the same as the aligned ones when the address happens to be aligned.
The second trick is to guess. The hardware prefetcher watches the lines a core asks for, and when it sees a pattern, one line after another, or a fixed jump between them, it asks for the next lines before the code does. Run the same chain of the last section, but with the pieces in order:
| Size of the chain | Random order | In order |
|---|---|---|
| 32 KiB | 0.72 ns | 0.72 ns |
| 256 KiB | 2.53 ns | 0.74 ns |
| 4 MiB | 9.0 ns | 0.76 ns |
| 256 MiB | 100 ns | 1.19 ns |
In order, the chain runs at almost L1 speed even from the RAM. Every read still depends on the previous one, but the line it needs is already in the L1, because the prefetcher brought it while the core was busy with the ones before.
This is the first reason why the flat loop of the next article is so fast: it reads memory in order, so every line is used in full and arrives before it is needed.
4. Many loads at once, and bandwidth
Reads that do not wait for each other
The chain of section 2 is the worst case on purpose. Each piece holds the address of the next one, so the core cannot even ask for the next piece until the current one has arrived: every read waits the whole latency of wherever its line lives, one after another. Most loops do not look like that. In out[i] = a[i] + b[i], the address of a[i + 1] does not depend on the value of a[i]: the core can compute it before a[i] has arrived.
And a modern core does exactly that. It does not run the instructions strictly one after another: it looks ahead, a few hundred instructions past the one it is waiting for, and it starts every instruction whose inputs are ready. A load whose address is known can start right away, even while earlier loads are still waiting for their data. This is called out-of-order execution.
A word about “miss” before going on, because it can be misleading. A miss only means that the line was not in that cache at the moment the core asked for it, so the request has to go one level further down: to the L2, then to the L3, and then to the RAM. It has nothing to do with a failed guess. The prefetcher of section 3 is the part that guesses, and when it guesses right the line is already in the cache and there is no miss at all. Out-of-order execution does not avoid the misses: it lets many of them be on their way at the same time. Each core keeps a small table of the lines it has asked for and not yet received, a few tens of entries across its levels, and while those requests travel, it keeps starting new ones. The lines arrive one after another, and each instruction that was waiting for one goes on as soon as its line is there.
To see this with a tensor, the experiment indexes x with a tensor of positions: x[idx], where idx holds a million positions, is one single call that returns a tensor of a million floats. Inside that call there is one loop, out[i] = x[idx[i]] for every i. x has floats (64 x 1024 x 1024), 256 MiB, so it never fits in the caches, and the positions are chosen so that every read touches a different line: either in order but 64 floats apart (256 bytes, four lines), or shuffled. The address of each read comes from idx[i], which the loop reads in order, so that read is cheap and the prefetcher brings it early. Nothing in read i + 1 depends on the result of read i, the opposite of the chain:
x[idx] each address comes from idx, which is read in order and is already in the cache, so the core can ask for the next line before the previous one arrives. 4.2 ns is Raxis's time per element in the shuffled row of the table below.These are the times per element, on one thread. The three libraries write into an output allocated in advance (np.take(x, idx, out=...) in NumPy, index_select(x, 0, idx, out=...) in PyTorch and Raxis), so the time is the loop and its reads, not a new allocation:
x[idx] with x of 256 MiB, ns per element | NumPy | PyTorch | Raxis |
|---|---|---|---|
idx in order, 64 floats apart | 5.3 | 3.2 | 2.5 |
idx shuffled | 12.4 | 5.7 | 4.2 |
Every element is a line that comes from the RAM, and a read from the RAM takes about 100 ns. Yet the cost per element is between 2.5 and 12.4 ns. The only way that adds up is that many reads are on their way at the same time: with Raxis, 100 / 4.2 is about 24 in the shuffled case and 100 / 2.5 is 40 in order. In order is faster because the prefetcher sees the fixed jump of 256 bytes and asks for lines before the loop does. Shuffled, there is no pattern to follow, and almost every read also falls in a different page of memory, which costs an extra step that section 5 explains.
The difference between the libraries comes from their loops, not from the memory, which is the same for all three. A loop that does more work per element, extra checks or conversions, reaches the next read later, so it keeps fewer reads on their way, and each element costs more of the latency.
What bandwidth is
Once the reads overlap, the latency stops deciding the time of a loop, and a second number takes its place: the bandwidth, how many bytes per second a link can deliver. The two are different things. The latency is how long one request takes to come back. The bandwidth is how many bytes can come through per second when many requests are on their way at once. If you think of a road, the latency is how long one car takes to drive from one end to the other, and the bandwidth is how many cars per second can arrive, which depends on the number of lanes and on how fast they move.
Every link of the path has its own bandwidth: between the core and its L1, between the L2 and the L3, between the CPU and the RAM. And everything that goes through a link shares it. “Using bandwidth” means filling that link with bytes, the ones the loop reads and the ones it writes, and every byte moved for one thing is a byte that cannot move for another in that second. Two consequences come back later in the article: the bytes of a line that a loop does not use also travel, and also count (section 6), and the cores of the CPU share the link to the RAM (section 11).
How the RAM sends bytes: wires, transfers and bursts
For the RAM, the bandwidth comes straight from how the memory is connected to the CPU, and it is worth building it up from the bottom, because the numbers that appear on the way are easy to confuse with others.
Wires, one bit each. The memory modules are connected to the CPU’s memory controller by wires on the motherboard: copper traces on the board and pins on the module. A group of them that carries data together is called a bus, and the picture of lanes fits it well, with one important detail: each lane is one wire, and one wire carries one bit at a time. Data moves in transfers: at every transfer, every data wire of the bus carries one bit at the same time. A bus of 64 data wires therefore moves 64 bits, 8 bytes, per transfer. Next to the data wires there are others that carry the commands and the addresses (which row and column of the chips to read), but they do not carry data, so they do not count for the bandwidth.
Channels. A channel is one such set of wires between the controller and a memory module, and the controller can use each channel independently of the others. On DDR4 a channel has 64 data wires, 8 bytes per transfer. DDR5 keeps 64 wires per module, but splits them into two subchannels of 32 wires, 4 bytes per transfer each, that work independently: one module can be serving two different requests at the same time. Modules with ECC, common in servers, add a few wires per channel for the error-correcting bits, which are not data either. This machine has two channels, with one module in each.
Transfers per second. The speed of the memory is given in transfers per second per wire. The modules here run at 4800 MT/s: 4800 million transfers per second, so each wire carries 4800 million bits per second. The memory’s clock runs at half of that, 2400 MHz, and DDR, double data rate, means that a transfer happens on each edge of the clock, twice per tick. The kit is sold as DDR5-6000, but it runs at 4800 unless its faster profile (EXPO on AMD, XMP on Intel) is turned on in the BIOS, and this machine runs at the default.
Bursts and cache lines. The controller never asks for a single transfer. It asks for a burst: a series of consecutive transfers from the same place in the chips. On DDR4 a burst is 8 transfers of 8 bytes, and on DDR5 it is 16 transfers of 4 bytes on one subchannel: 64 bytes in both cases, exactly one cache line. This is not a coincidence: the caches and the memory are designed together so that a cache miss becomes exactly one burst, and the line size of section 3 is the amount of data one burst brings.
The ceiling. Putting it together, one channel moves 8 bytes per transfer, 4800 million times per second, and there are two channels:
That is the most the memory can deliver; the real rate is always lower, because the chips also spend time refreshing their cells, opening new rows and switching the wires between reading and writing.
Capacity is a different thing. The 32 GiB of this machine is how much the memory stores, not how fast it delivers it. A second module in the same channel would double the capacity and add nothing to the bandwidth, because it would share the same wires. More bandwidth comes from more channels (servers have 8 or 12), wider ones, or more transfers per second.
On Linux, sudo dmidecode -t memory shows the speed and size of each module; on Windows, the memory page of the Task Manager shows the speed and the slots used; on macOS, the memory of Apple’s chips sits inside the chip package, on a wider bus than a PC’s, and its bandwidth is in Apple’s specifications.
Three sizes appear in the figure, and only one of them is about the CPU being “64-bit”:
- A 64-bit CPU has registers of 64 bits, 8 bytes, and pointers of 8 bytes. Memory is numbered byte by byte: an address is the number of one byte, and a pointer is a variable that holds such a number. The 64 bits decide how big a number one instruction works with, and how many addresses a program can name ( in theory; today’s CPUs use 48 bits of the address, or 57 on some servers). It does not decide how many bytes travel from the RAM at a time.
- A memory channel has 64 data wires, so it carries 8 bytes per transfer (DDR5 splits them into two subchannels of 4 bytes). That it is also “64” is a coincidence of history, not the same thing as the 64-bit CPU.
- A cache line is 64 bytes, the unit the caches move: one burst of the memory.
Why 64 bytes per line, and not more or less, is a trade-off. A larger line brings more neighbours with every miss, which pays when the code reads in order, and the caches need fewer tags to record which address each line holds. A smaller line wastes less when the code uses only one number of each line, the case of section 6, and fills the caches with fewer bytes nobody reads. 64 is where almost every x86 and ARM CPU lands; Apple’s M chips use 128.
From a line of code to a burst
All of this is hardware, and none of it appears in the code. It helps to follow one read from the tensor down to the memory, to see where the software ends and the hardware takes over. Take a + b on two float32 tensors of 1000 x 1000, 4 MB each:
- Python and PyTorch.
a + bends, after the machinery of the next articles, in a C++ loop over raw pointers,out[i] = a[i] + b[i]. As the first article showed, the address of an element is the tensor’s data pointer plus its offset times 4 bytes:a[i]lives atdata_ptr + 4 * i. - The compiler.
a[i]becomes one load instruction: “read 4 bytes at this address into a register” (or 32 bytes, eight floats at once, with the SIMD registers of section 9). That is everything the program ever tells the hardware: an address and a size. Nothing in Python or C++ names a cache, a line or a channel. - The address. The address the program uses is virtual; the hardware first translates it to the physical address in the RAM (section 5 explains how, and what it costs).
- The L1. The core looks for the line that holds that address. Lines start at multiples of 64 bytes, and , so the last 6 bits of an address are the position of the byte inside its line (0 to 63), and the rest of the address says which line it is: the address
0x...a47is byte 7 of the line that starts at0x...a40, the same address with its last 6 bits set to zero. It is the decimal trick of blocks of 100, where 1234 is position 34 of the block that starts at 1200. PyTorch and Raxis allocate tensors at addresses that are multiples of 64 (section 3), soa[0]toa[15]share the first line,a[16]toa[31]the second, and the 4 MB ofaare 62,500 lines. - The misses. If the line is not in the L1, the request goes to the L2 and to the L3. If it is not in any of them, the memory controller picks a channel and a subchannel from bits of the physical address, and the line comes back as one burst of 16 transfers. It is copied into the L2 and the L1, and the 4 bytes go into the register. On AMD’s Zen it does not stop in the L3: there the L3 is a victim cache, filled with the lines the L2 evicts, so the line reaches it later, when the L2 needs its place for another one. Many Intel CPUs keep a copy in the L3 from the start.
- Meanwhile. The core has not stopped: it has already started the loads of the next elements, so their lines are on their way too, as in the timeline above.
float x = p[16], on this machine. (1) The program asks for the 4 bytes 64 bytes afterp, a virtual address in the heap. (2) The TLB, or a page walk, gives the physical address (section 5). (3) The core looks for the line in its L1 and L2, then in the L3 and the RAM. (4) The line comes back up into the caches, and the 4 bytes into a register. p is drawn in the stack, where a local lives when the compiler does not keep it in a register.Registers. The path ends in a register, the one place in the figure without an address. Registers are storage inside each core, and the only data instructions compute with directly: an addition takes its numbers from registers and leaves its result in one, and loads and stores are what move data between them and memory. x86-64 has 16 general registers of 64 bits, for integers and addresses, and 16 vector registers for floats and SIMD (32 with AVX-512, as on this CPU); ARM64 has 31 and 32. That is about 2 KiB here, all a program can name. (Inside, a core has a few hundred more, which it uses to run independent instructions at the same time, but the program never sees them.) Registers cannot overflow: when a function needs more values at once than there are registers, the compiler keeps some of them in the stack, a spill, and reads them back with ordinary loads, which find their lines in the L1. A pointer like p usually stays in a register the whole loop; what travels the whole path is the data it points to.
So the software controls only two things: which addresses it reads, and in what order. Everything else, the lines, the prefetcher, the bursts and how many reads are on their way, is the hardware’s answer to those two choices. That is why the rest of the article, and the series, keeps coming back to the order of the reads and to the strides: a loop that reads contiguous addresses in order uses every byte of every line and burst it pays for, keeps many reads on their way, and lets the prefetcher run ahead. A loop that jumps around pays a whole line for each number it uses (section 6).
Bandwidth measured: the addition
Here is the addition itself, in C++, for three arrays of growing size. Each call is repeated over the same arrays, as an operation inside a training loop would be, so after the first call the arrays are wherever they fit. Each element reads 4 bytes of a, 4 bytes of b, and writes 4 bytes of out: 12 bytes. So the bandwidth is 12 bytes divided by the time per element; for the first row, 12 / 0.052 ns = 231 GB/s:
out[i] = a[i] + b[i], n floats | Three arrays | ns per element | 12 bytes / time |
|---|---|---|---|
| 1,000 | 12 KB | 0.052 | 231 GB/s |
| 64,000 | 768 KB | 0.054 | 222 GB/s |
| 250,000 | 3 MB | 0.083 | 145 GB/s |
| 1,000,000 | 12 MB | 0.082 | 146 GB/s |
| 4,000,000 | 48 MB | 0.162 | 74 GB/s |
| 16,000,000 | 192 MB | 0.285 | 42 GB/s |
The same three steps as the latency table of section 2, but now measured in bytes per second instead of nanoseconds of waiting: up to about 230 GB/s while the three arrays fit in the L1 and L2 of the core, about 145 GB/s once they need the L3, and 42 GB/s once they only fit in the RAM. On Linux with GCC the numbers are the same. The 1000 x 1000 tensors of the series, 12 MB for the three of them, live in the L3 when an operation repeats, and that is why a + b takes 0.07 ms there in every library.
Is 42 GB/s all this RAM can give, against the 76.8 of the ceiling? Not quite, because 42 counts only the 12 bytes the loop asks for, and the hardware moves more. The caches only hold whole lines, so to write 4 bytes of out the core first needs the line that holds them: it reads it from the RAM, a read for ownership, even though the loop is about to overwrite all of it. The new values stay in the cache, and the line is marked dirty: its copy in the cache is newer than the one in the RAM. Nothing goes to the RAM yet. A dirty line moves down one level only when it is evicted, from the L1 to the L2 and from the L2 to the L3, and it is written to the RAM when the last level evicts it, as a whole line, one burst, like a read. Caches that work like this are called write-back: a line written many times while it stays in the cache costs one write to the RAM. The memory controller keeps those writes in a queue and sends them in groups, because switching the wires between reading and writing costs time, and no instruction is waiting for a write to finish. The output therefore travels twice, once in and once out, and the real traffic is 16 bytes per element: 16 / 0.285 ns = 56 GB/s, about three quarters of the ceiling. One core alone gets close to everything the memory can deliver, and section 11 shows what that means for threads.
There are store instructions that skip the read for ownership: non-temporal stores (vmovntps on x86) write whole lines towards the RAM without bringing them into the caches, so the output travels once. They also leave the output out of the caches, which is a loss when the next operation reads it, and that is the usual case in a chain of tensor operations; memcpy uses them only for very large copies.
Memory-bound and compute-bound
This gives a name that the series uses a lot. Compare the two limits of the addition on this machine. On the side of the instructions, a core can do at least two vector additions of eight floats per cycle, and at 5.5 GHz that is 88 billion additions per second: 0.011 ns per element, if the numbers were already in registers. On the side of the memory, each element needs 16 bytes of real traffic, and at the ceiling of 76.8 GB/s that alone takes 16 / 76.8 = 0.21 ns per element; the measured time was 0.285 ns. The bytes take about 25 times longer than the additions, so the core spends most of the loop waiting for lines, and making the addition faster would not change the time at all. Even from the L1, at 0.052 ns, the limit is moving the 12 bytes in and out of the registers, not adding them. An operation like this, whose speed is set by the memory, is called memory-bound. An operation like exp or sigmoid runs dozens of instructions for every element it reads, and its speed is set by those instructions: it is compute-bound. Making the instructions faster, with wider registers or a better polynomial, only helps the second kind. The kernels article measures exactly that.
5. Pages and the TLB
Every address so far was the number the program uses, and section 4 said in passing that it is not the real position in the RAM. Turning one into the other has costs of its own, and they show up in several sections of this article, so here is the whole story.
Virtual addresses and pages. The operating system gives each program its own addresses, called virtual, and maps them to physical memory, the real positions in the RAM. It does not map byte by byte, but in blocks called pages. A page is a run of consecutive addresses that starts at a multiple of its size, 4 KiB (4096 bytes) on x86 by default, 16 KiB on Apple’s M chips, and the RAM is cut into physical pages of the same size. Each virtual page is mapped as a whole to one physical page, anywhere in the RAM:
How an address names a byte. Every byte is then a page plus a position inside that page, and an address is written exactly that way. It is a number of 64 bits, but today’s x86-64 CPUs use only the low 48 (section 4): the 16 above must be copies of bit 47, which is 0 in a program’s addresses (the kernel’s, in the upper half, have it at 1), so in practice they are zeros. Hexadecimal leaves those leading zeros out, so 0x7ff6a3c41a40 is 0x00007ff6a3c41a40. Since a page of 4 KiB holds bytes, 12 bits are enough to number the position of a byte inside its page, and they are the lowest ones, bits 0 to 11. The 36 bits above them, 12 to 47, are the number of the page, its name in the program. In hexadecimal each digit is 4 bits, so the position is the last three digits: 0x7ff6a3c41a40 is byte 0xa40 of the virtual page 0x7ff6a3c41. A physical address is built the same way, a physical page and a position, and translating an address only replaces the number of the page: if the page table maps 0x7ff6a3c41 to the physical page 0x38e5f2, the address becomes 0x38e5f2a40, with the same a40 at the end. Section 8 shows that the L1 counts on that. A program never sees the physical address.
The map from virtual pages to physical ones, the page table, is kept by the operating system in memory, as a tree of four levels on x86-64. A translation from scratch, a page walk, is therefore up to four reads of memory before the read the program asked for. Why not let programs use physical addresses directly? Because this indirection is what gives everything else: a program can only name its own pages, since the operating system writes the table, so no program can read another’s memory; a tensor of gigabytes is contiguous in virtual addresses while its pages lie anywhere in the RAM, so the RAM never needs a free run of gigabytes; a page gets physical memory only when it is used, as the last part of this section shows; and the code of a library that several programs load sits in the RAM once, mapped into each of them.
The TLB. A page walk per read would make every read several times slower, so the CPU keeps the recent translations in a small cache of its own, the TLB (translation lookaside buffer). Each core of this CPU has a first TLB of 96 entries and a second one of 4096 (from AMD’s presentation of Zen 5 at Hot Chips 2024). With pages of 4 KiB, 4096 entries cover 16 MiB. A program that reads in order needs one translation for every 1024 floats. A program that jumps around in more than 16 MiB misses the TLB on most reads, and each miss is a page walk, whose reads usually hit the caches but still cost time. That is the row of 16 MiB in section 2: the chain still fits in the L3 of 32 MiB, and costs twice as much as the one of 8 MiB, because from there most of its steps also miss the TLB. Section 6 shows the same cost with a stride.
Huge pages. x86 also has pages of 2 MiB, and of 1 GiB. With pages of 2 MiB one TLB entry covers 512 times more memory, and 4096 entries cover 8 GiB. Linux can give them by itself, as transparent huge pages, either to the memory a program asks for with madvise(MADV_HUGEPAGE) or to all memory; cat /sys/kernel/mm/transparent_hugepage/enabled shows the mode, and on this WSL it is madvise. Windows gives large pages only to programs that have a special privilege, so in practice a normal program does not get them.
What a program starts with. A program does not start with a block of RAM. It starts with a space of virtual addresses of 128 TiB on x86-64, almost all of it empty. The operating system records which ranges are valid and what each one holds: the code of the program and of its libraries, read from their files the first time each page is touched, a stack, a heap. An address outside every valid range has no page to give, and touching it ends the program, with a segmentation fault on Linux and an access violation on Windows. A variable is just bytes at some address in one of those ranges: the stack’s top pages are in use all the time, and the caches neither know nor care whether a line comes from the stack, the heap or the code.
The stack and the heap. Both are ordinary pages, and reading a byte costs the same in either; what differs is how memory is taken and given back. The stack is a pile. Each call to a function takes a block on top of it for its local variables, just by moving one register, the stack pointer, and returning gives the block back by moving it again. So the locals disappear by themselves when the function ends, nothing has to free them, and the next call reuses the same bytes, still in the L1. It is also why a function must not return a pointer to one of its locals: the block it points to is overwritten by the next call. The stack is small, 1 MiB per thread by default on Windows and 8 MiB on Linux, and a recursion that goes too deep, or a large local array, overflows it: the stack overflow. The heap is what malloc and new give: a block of any size, decided while the program runs, that lives until the program frees it, and can grow to all the memory the operating system is willing to give. Taking a block means finding a free one of the right size, which costs tens of nanoseconds at best, and new memory brings the page faults of the end of this section. The data of a tensor is always in the heap, because its size is known only while the program runs, it can take gigabytes, and it must outlive the function that created it. Small things that would cost a malloc each, such as the sizes and strides of a tensor, PyTorch and Raxis keep inside the object itself for up to 5 dimensions (PyTorch’s SizesAndStrides, a SmallVector in Raxis).
Contiguous is only virtual. A tensor is contiguous in the program’s addresses, and that is all the code needs: every instruction, a SIMD load included, works with virtual addresses. A vector load that crosses from one page into the next is translated twice and costs a little more, and with allocations aligned to 64 bytes (section 3) an aligned load never crosses one, because 4096 is a multiple of 64. The one place where the hardware notices is the prefetcher: it works with physical addresses and does not know which physical page comes next, so it stops at the end of each 4 KiB page, one more advantage of huge pages.
The first write to a page. When a program asks for memory, the operating system only reserves the addresses: no physical page is behind them yet. A small malloc does not even ask the operating system: the allocator cuts it from a larger range it reserved before, and asks for more only when that range runs out. The first time each page is touched, the CPU finds no translation and raises a page fault. The operating system stops the program, takes a free physical page, fills it with zeros (so no program can see what another one left there), writes the translation, and lets the program go on. That is about half a microsecond per page here, more than writing the page’s 4 KiB.
This reaches tensors through the allocator. An operation that returns a new tensor needs new memory, and whether that memory faults depends on where the allocator gets it: from memory freed earlier, which is still mapped, or from the operating system, which maps it again. a + b with a new output and with out=, on one thread:
a + b, ms | NumPy | PyTorch | Raxis |
|---|---|---|---|
| 1000 x 1000 (4 MB), Windows, new output | 0.57 | 0.07 | 0.07 |
1000 x 1000, Windows, out= | 0.08 | 0.07 | 0.08 |
| 4000 x 4000 (64 MB), Linux, new output | 7.04 | 12.60 | 4.69 |
4000 x 4000, Linux, out= | 4.62 | 4.62 | 4.63 |
- NumPy on Windows gets large arrays from the system’s heap, which gives large blocks back to the operating system when they are freed. Every new output faults all of its 977 pages: 0.49 ms, six times the addition itself. At 4000 x 4000 it is 8.1 ms against 4.6.
- PyTorch and Raxis on Windows use mimalloc, an allocator that keeps freed memory for a while and hands it out again: the output of the last call is still mapped, and nothing faults.
- PyTorch on Linux uses the C library’s
malloc, which keeps freed blocks only up to 32 MiB and maps larger ones fresh every time: 15,625 faults, 8 ms on top of the 4.6 of the addition. It has an opt-in variable,THP_MEM_ALLOC_ENABLE=1, that asks for huge pages for buffers of 2 MiB or more (pytorchalloc_cpu.cpp); with it this row took 6.7 ms in my runs. - NumPy on Linux asks for huge pages for its large arrays, so the 64 MB fault in 31 pieces of 2 MiB, and what remains, 2.4 ms, is mostly the zeroing of the 64 MB.
- Raxis on Linux uses mimalloc there too, and reuses the memory.
That is one more reason why the tables of this article write into an output allocated in advance (section 4): otherwise part of what they measure is the allocator and the operating system, not the loop. In training it matters less than it seems, because every step creates tensors of the same sizes, and an allocator that keeps memory hands the same blocks out again. The GPU makes it a rule: PyTorch’s CUDA allocator never gives memory back unless asked, and the CUDA article comes back to pages, because copying to the GPU needs pages that the operating system promises not to move.
Swap and fork. Two more things the page table makes possible show up when Python and PyTorch run for a long time. When the RAM runs out, the operating system writes the contents of pages that have not been used for a while to the disk, the swap (the pagefile on Windows), frees their physical pages and marks the virtual ones as absent; touching one again is a page fault that reads its contents back into any free physical page, usually not the one it had. The program does not notice, except that a read from the disk costs tens of microseconds or more instead of about a hundred nanoseconds. Pinned (page-locked) memory never goes there. The other is fork, on Linux and macOS: it starts a new process as a copy of the running one without copying its memory. Both share the same physical pages, marked read-only, and the first write to one of them gives the writer a private copy of that page, which is called copy-on-write. That is how the workers of a DataLoader started with fork, for a long time the default on Linux, get the dataset of the main process for free. It is also why they can slowly grow to a full copy each: if the dataset is a list of Python objects, reading an object writes its reference count, and every page that holds one gets copied, while the same data in one NumPy array or tensor stays shared. spawn, the default on Windows and macOS, starts a new interpreter instead, which imports everything again and shares only the code of the libraries, mapped from the same files.
6. Reading with a stride
Now the case the series meets first: a tensor read with a stride, like x[::s]. You can see each cost separately by adding x[::s] to a contiguous y, for a growing stride s. With a million elements, x is much larger than the caches, so every line comes from the RAM:
x[::s] + y, ns per element | NumPy | PyTorch | Raxis |
|---|---|---|---|
| stride 1 (4 bytes) | 0.074 | 0.075 | 0.075 |
| stride 2 (8 bytes) | 0.21 | 0.35 | 0.20 |
| stride 8 (32 bytes) | 1.00 | 0.68 | 0.68 |
| stride 16 (64 bytes) | 1.63 | 1.04 | 1.04 |
| stride 64 (256 bytes) | 2.01 | 1.73 | 1.75 |
| stride 1000 (4000 bytes) | 3.27 | 2.08 | 2.09 |
x[::s] over float32 memory. From a stride of 16 floats (64 bytes) on, every element costs a whole line, and the loop moves sixteen times more memory than it uses.- Stride 2 already costs about three times more, even though it only reads twice as much memory: half of every line of
xis still used. The rest is the vector loop. The elements ofxare no longer next to each other, so the kernel cannot load eight of them with one instruction, and it adds them one at a time (section 9 explains why). - From 32 bytes on, the cache lines come in. With a stride of 32 bytes only 2 of the 16 floats of each line are used, and from 64 bytes on only one: the loop pays for sixteen times more memory than it uses.
- Beyond 64 bytes every element is still one line, and the cost keeps growing. Part of it is the prefetcher, which follows a fixed jump less well the longer it is. The other part is the translation of addresses (section 5). Reading in order, one translation serves 1024 floats. With a stride of 4000 bytes, every read lands in a different page of 4 KiB and needs a translation of its own, and a million reads cover 4 GB of addresses, far more than the 16 MiB the TLB can translate without a page walk.
7. Lines that come back: reuse
So does a transpose read sixteen times more memory than it uses? Not always. Look at a + c.t(), with a and c of shape (1000, 1000), float32. The loop walks a row of a, which is a column of c: 1000 floats 4000 bytes apart, 1000 different lines. But the next row of a needs the next column of c, which lives in the same 1000 lines, and so do the 14 after it. While those lines stay in a cache, each one comes from the RAM only once and ends up fully used, just not in one go.
This is the idea of reuse. A line is used, then many other lines are read, and then the loop needs the first line again. Whether it is still in a cache depends on how many bytes of other lines came in between: if they fit in a level, the line is still there. Here the lines in between are one column of c, so how much the transpose costs depends on which level holds a column. This is how many times longer a + c.t() takes than a + c, for square tensors of size n:
a + c.t(), times slower than a + c | NumPy | PyTorch | Raxis |
|---|---|---|---|
| n = 300 | 4.4x | 4.6x | 2.5x |
| n = 1000 | 5.9x | 5.9x | 5.3x |
| n = 4000 | 2.9x | 2.2x | 2.3x |
- n = 300: a column is 300 floats in 300 different lines, and what a cache has to keep is the lines: 300 x 64 bytes, about 19 KiB, which fits in the L1 (48 KiB). Every read of
chits the L1, and the remaining cost is the lost vector loop. - n = 1000: a column is 1000 lines, 62.5 KiB, too much for the L1, so every read of
cgoes to the L2, about three and a half times slower (section 2). That is the factor of six of the series’ transpose. - n = 4000: a column, 4000 lines or 250 KiB, still fits in the L2, but now the contiguous
a + cis slow too, because three tensors of 64 MB come from the RAM (section 4), and the gap shrinks.
The TensorIterator article uses the same idea to explain why a + b and b + a can take different times with the same tensors: the order of the loop decides how soon a line is needed again.
8. Where a line can go: cache sets
One size is missing from the last table, and it is the one most of us would pick for a test:
a + c.t(), times slower than a + c | NumPy | PyTorch | Raxis |
|---|---|---|---|
| n = 1000 | 5.9x | 5.9x | 5.3x |
| n = 1024 | 29x | 32x | 33x |
A cache is not one big pool where any line can go. To find a line fast, the CPU uses a few bits of its address to pick a small group of slots, a set, and the line can only go into one of the slots of that set, which are called ways. The L1 of this CPU has 64 sets of 12 ways (64 x 12 x 64 bytes = 48 KiB), and the L2 1024 sets of 16 ways. The set of a line is its address divided by 64, modulo the number of sets: bits 6 to 11 of the address for the L1, bits 6 to 15 for the L2.
How does the cache know which line a way holds? Next to the 64 bytes of the line, each way stores the rest of its address, called the tag: for the L1, the bits from 12 up. Bits 0 to 5 only say which byte of the line, and bits 6 to 11 are known from the set the line is in, so neither needs storing. To look for an address, the cache takes the set from bits 6 to 11 and compares the address’s tag with the 12 tags of that set at once, with 12 comparators side by side; if one matches, it is a hit. Every two lines whose addresses share bits 6 to 11 compete for the same set, and when a line comes into a full set, one of the 12 has to leave, by the rule of section 2.
Why does the L1 have only 64 sets, when the L2 has 1024? Because of the pages of section 5. Bits 6 to 11 lie inside the position within a 4 KiB page, which the translation does not change, so the L1 can pick the set from the virtual address while the TLB translates it, and only the comparison of the tags waits for the physical address. That hides the translation on every load, but it limits the L1 to 64 sets of 64 bytes, 4 KiB per way: to grow, the L1 can only add ways, 12 on this CPU, and every way is one more comparator working on every load. The L2 is not in such a hurry: it waits for the physical address, and takes part of its set from above the page.
With n = 1024 a row is exactly 4096 bytes. Addresses 4096 bytes apart have the same bits 6 to 11, so the 1024 lines of a column all fall into the same L1 set, and compete for its 12 ways. In the L2 the bits 12 to 15 can still differ, but the pages of section 5 decide those bits, and there are only 16 combinations: 16 sets, 256 slots for 1024 lines. By the time the next column needs a line, it has been evicted, and every read goes to the L3 or the RAM.
c fall into, for a + c.t()with n x n float32 tensors. Addresses 4096 bytes apart share bits 6 to 11, and with 4 KiB pages only 4 more bits of the set number can change, so a column with rows of 4096 bytes reaches only 16 sets.Only the exact power of two is the trap: with n = 1008 or 1032 the transpose costs the same as with 1000, while n = 4096 takes 4.8 ns per element, seven times more than n = 4000. That is also why 1024 looks so much worse than 4000: at 4000 a column, 250 KiB, spreads over the sets and stays in the L2, every read of c is an L2 hit (0.65 ns per element), and the ratio is small because the contiguous addition is already limited by the RAM.
On Linux with GCC the numbers are similar, n = 1024 included. They come from raxisstrides.py. Keep this one in mind when you benchmark anything: a power-of-two size can measure the cache sets instead of your code.
9. SIMD: one instruction, several numbers
Back to the first bullet of section 6, the one that was not about memory. The CPU has registers wider than a number, and instructions that work on all the numbers of a register at once: SIMD, single instruction, multiple data. With AVX2 a register holds eight floats, so one instruction loads eight floats, another adds two registers, eight additions, and another stores eight results.
Each CPU family has its own SIMD instructions, and newer CPUs add wider registers. The width decides how many numbers one instruction works on:
| Instructions | Where you find them | Bits | Floats |
|---|---|---|---|
| SSE2 | every x86-64 CPU (the minimum) | 128 | 4 |
| AVX2 | most x86 CPUs since 2013-2015 | 256 | 8 |
| AVX-512 | Intel Xeon, AMD Zen 4 and 5 | 512 | 16 |
| NEON | every ARM64 CPU: Apple M, Raspberry Pi 3+, phones | 128 | 4 |
| SVE | some ARM servers (AWS Graviton3: 256 bits) | 128-2048 | 4-64 |
Microcontrollers often have none, or narrow ones, and RISC-V has its own vector extension. A program compiled for the minimum runs everywhere and leaves the wider registers unused, so PyTorch compiles its CPU kernels several times, for DEFAULT (the minimum), AVX2 and AVX512 on x86, and DEFAULT (which includes NEON) and SVE on ARM, and picks one when it starts. The kernels article shows how. You can ask which one it picked, in PyTorch and in Raxis:
>>> torch.backends.cpu.get_cpu_capability()
'AVX512'
>>> raxis.backends.cpu.get_cpu_capability()
'AVX512'
So why did x[::2] lose the vector loop? The usual vector load, _mm256_loadu_ps in C++, the instruction vmovups, reads 32 consecutive bytes from one address: eight floats that are next to each other. There is no version with a stride.
With x[::2] the eight floats you want are spread over 64 bytes, and a plain load would bring four of them and four that are not yours. It is not an error, it is just the wrong numbers. There are two ways around it:
- A gather. AVX2 and AVX-512 have instructions that load each lane from its own address,
vgatherdps. They exist, but inside they still do about one load per lane, and on many CPUs they cost about as much as the separate loads (on Intel’s even more since the 2023 microcode fix for the Downfall vulnerability). - Load contiguous, then shuffle. For a stride of 2, load sixteen floats and keep the even ones with a permute instruction. It works, but every small stride needs its own code.
And the gain would be small, because beyond 64 bytes the cost is the memory, not the additions (section 6). So PyTorch only uses its vector loop when every inner stride is the size of an element, or 0 for a broadcast tensor, and any other stride goes through a plain loop, one element at a time. The next article shows that choice, and what the compiler does when nobody makes it.
10. Inside a core: running ahead, and guessing branches
So far the core has been a box that runs what the code says. Before the last trick, threads, it is worth opening it, because two things it does explain results of the earlier sections, and a third is a cost the other articles keep meeting: branches. First, the whole picture. This figure puts every piece of this article in its place, from the instructions of one core down to the RAM, with the section that explains each one:
What the code decides is the instructions, and through them which addresses are read and in what order. Everything else is decided by the hardware, from what the code does: when each instruction runs, how many reads are on their way, which lines come early, which lines stay in each cache.
Running ahead. The front end of the core reads instructions and decodes them, up to eight per cycle on this CPU, and puts them into a window of several hundred. Each instruction in the window runs as soon as its inputs are ready, even if an older one is still waiting, and the results are made final in the order of the program, so the program cannot tell. That is where the reads in flight of section 4 come from: a load that misses waits in the window, and the loads behind it that do not need its result run in the meantime. In the chain of section 2, the next load needs it, so it waits too.
Guessing the branches. To run ahead, the front end has to know which instructions come next, and a branch hides that. An if, or the end of a loop, is a jump whose direction depends on a comparison, and the comparison may not be computed yet, for instance because it waits for a load. Waiting for it would leave the window empty. So the branch predictor, a part of the front end, guesses the direction from what that branch did the previous times, and the core keeps going along the guessed path. If the guess was right, the branch cost almost nothing. If it was wrong, everything done after it is thrown away, and the front end starts again from the right path:
To measure what a wrong guess costs, the experiment (raxisbranches.cpp) keeps the elements of an array that are below a threshold, what x[x < t] does with a tensor, written in two ways:
// With a branch
if (x[i] < t) {
out[k++] = x[i];
}
// Without a branch: always write, then move the end of out by 0 or 1
out[k] = x[i];
k += x[i] < t;
In the second version the comparison is a number, 0 or 1, that is added, not a jump, so there is nothing to guess. x holds a million random numbers from 0 to 99, read in order, and t decides how many are kept. Nanoseconds per element, on one thread:
| Kept | With a branch | Without |
|---|---|---|
| none | 0.19 | 0.27 |
| 10% | 0.70 | 0.26 |
| 25% | 1.46 | 0.26 |
| half | 2.54 | 0.26 |
| 75% | 1.51 | 0.27 |
| 90% | 0.74 | 0.27 |
| all | 0.19 | 0.28 |
half, with x sorted | 0.19 | 0.27 |
- When the branch always goes the same way, none or all kept, the predictor is always right, and the branch is the fastest version: it skips the work the other one always does.
- With random data the predictor can only bet on the more frequent side, and it is wrong for the rest. Wrong 10% of the time adds 0.5 ns per element, wrong half of the time adds 2.35: about 5 ns, some 26 cycles, per wrong guess. The table is symmetric because keeping 10% and keeping 90% are wrong equally often.
- Sorted, the same half is kept, but the branch goes one way for the first half of the array and the other way for the rest. The predictor is wrong only around the switch, and the branch costs nothing again. The data is the same; only its order changed.
- Without the branch the time does not depend on the data at all: about 0.26 ns, whatever is kept.
With GCC on Linux the numbers are the same within a few percent.
The predictor does more than bet on the more frequent side: it remembers the recent history of the branches, and finds patterns in it. I found out how much while measuring. With a random array of 4,096 or 16,384 numbers, run again and again, the branch version took 0.19 ns at half kept, as if the data were sorted: the predictor had learned the whole random sequence. With 65,536 numbers it learned a part of it (1.9 ns), and from 262,144 nothing (2.5). With GCC’s build of the same loop it learned less, 1.2 ns already at 4,096, so how much it learns depends on the exact code too. That is a trap like the power-of-two sizes of section 8: a benchmark that runs a small input in a loop can measure a predictor that knows the input by heart. It is why the table above uses a million numbers.
A branch in a tensor library. Integer division is a real case. Python’s // rounds down and C++‘s / rounds toward zero, so when the operands have different signs and there is a remainder, the result has to be one less than what / gives. PyTorch does that with a branch on the signs (pytorchgeneric_math.h), and NumPy’s times say it does too. Raxis does it with the comparisons as numbers (raxisbinary_ops_kernel.cpp):
const scalar_t quot = a / b;
const scalar_t rem = a % b;
return quot - ((rem != 0) & signs_differ(rem, b)); // 1 or 0, never a jump
A million int64 divided by numbers from 1 to 49, in milliseconds, with the dividends all positive or with random signs:
| NumPy | PyTorch | Raxis | |
|---|---|---|---|
//, positive | 1.27 | 1.28 | 1.30 |
//, mixed signs | 3.43 | 3.22 | 1.30 |
%, positive | 1.27 | 1.86 | 1.34 |
%, mixed signs | 3.30 | 4.95 | 1.34 |
With positive numbers the signs never differ, the branch always goes the same way, and the division itself takes the time. With mixed signs half the guesses fail, and that costs more than the division. On Linux the picture changes in one place, and it shows something important: GCC compiled PyTorch’s % without a jump on its own, so there it takes 1.9 ms with either kind of sign, while its // still loses (2.7 ms with mixed signs, NumPy 4.2). Whether an if in the source becomes a jump in the binary is the compiler’s decision: it can turn a short if into a conditional move, an instruction that picks one of two values with no jump, and it can also turn code without an if back into a jump. That happened to Raxis’s %: its first version, with the comparison turned into a mask, became a jump in GCC’s build, and only a version built from sign bits alone stayed without one on both compilers.
Branches and SIMD. A vector instruction works on 8 lanes at once, and the lanes cannot take different paths, because there is no jump per lane. So vector code has no branches by force: comparisons give masks, and a blend keeps, lane by lane, one of two results, as the kernels article shows. That is the second reason to remove a branch: without one, the compiler can often vectorize the loop.
When a branch is better. Without a branch, the code always does the work of both paths. Most branches are predictable: the end of a loop, an error check that never fails, a test that gives the same answer for a whole tensor. There, as the first and last rows of the table show, the branch is the cheaper one. Removing a branch pays when the data decides the direction, and the data is random.
11. Cores and threads
The last trick is to split the work. Look again at the figure of section 2: this CPU has 8 cores. Three words get mixed up here, so first what each one is.
- A core is the hardware that does the work: the units that fetch instructions, decode them and execute them (additions, multiplications, loads from memory), plus its L1 and L2. A core does not run one instruction per cycle: it can start several in the same cycle, as long as they do not depend on each other (section 10), and it has several units of each kind for that.
- A hardware thread is not hardware that executes anything. It is the state of one running program kept inside a core: its registers and the address of its next instruction. With Simultaneous Multithreading (SMT, which Intel calls Hyper-Threading), each core of this CPU keeps two of those states, so the operating system sees 16 logical processors, 16 places where it can put a software thread. The core takes instructions from both of them and executes them in the same cycles, mixed together in the same units: it does not take turns between them, and nothing has to be saved or loaded to go from one to the other, because both states live in the core all the time.
- A software thread, what a program creates and what the word “thread” usually means, belongs to the operating system: its registers saved in memory, its stack, its state. There can be thousands of them. The operating system puts one on each logical processor, and every few milliseconds, or sooner when a thread has to wait for something, it takes one off and puts another on: it saves the registers of the old one in memory and loads those of the new one into the hardware thread. It can also move a thread to another core.
So there are two levels of sharing at very different speeds. The operating system shares the 16 logical processors among the threads of every program, every few milliseconds. Each core shares its units between the two threads loaded on it, in every cycle.
How are the units shared? Each unit can start one operation per cycle. In every cycle, the core looks at the operations of both threads that are ready, the ones whose inputs have already arrived, and hands them to the units that are free. If both threads need the same kind of unit, they split it: when both only do vector additions and the core has two units for them, one thread alone uses both, and two threads get one each, so each runs at half speed and together they do the same work as one.
Why have two hardware threads per core, then? Because one thread alone rarely keeps all the units busy: it waits hundreds of cycles for a line from the RAM, or its next instruction needs the result of the one before, as in the chain of section 2, or it uses one kind of unit and leaves the others idle. The second thread fills the units the first one leaves idle in those cycles. That gain depends on the program, and it is always well below twice as fast. Besides the units, the two threads also share the queues inside the core that hold the instructions on their way (AMD’s Zen cores split several of them in half when both threads are active), the L1 and the L2, and the link to the RAM. So if one thread already keeps the units busy, or both wait for the same memory, the second one adds little or nothing, and the tables below show both cases.
So which caches does a thread have? None of its own. It uses the L1 and L2 of the core it is running on, and the L3 and the RAM that everyone shares. If it is moved to another core, its data stays in the caches of the old one, and it starts cold. And two threads on the same core share everything that core has: its L1, its L2, its units for additions and loads.
PyTorch uses one thread per physical core by default, 8 here (torch.get_num_threads()), and Raxis does the same. This is a + c and a + c.t() with more and more threads, placed one per core first, in PyTorch (Raxis gives the same numbers, within a few percent):
| PyTorch, ms | 1 thread | 2 | 4 | 8 | 16 |
|---|---|---|---|---|---|
1000 x 1000, a + c | 0.077 | 0.044 | 0.026 | 0.020 | 0.013 |
1000 x 1000, a + c.t() | 0.469 | 0.242 | 0.131 | 0.071 | 0.072 |
4000 x 4000, a + c | 4.54 | 4.36 | 4.43 | 4.71 | 4.86 |
4000 x 4000, a + c.t() | 10.7 | 6.04 | 4.92 | 4.93 | 5.07 |
- 1000 x 1000 scales well. The 12 MB are in the L3, and each core gets its own L1 and L2 for its part, so 8 threads are 4 to 7 times faster. The 16 threads, two per core, still help the contiguous case a little and not the transpose.
- 4000 x 4000
a + cdoes not scale at all. The 192 MB come from the RAM, and section 4 showed that one core already takes most of what the memory can deliver. More cores only queue at the same memory. - The 4000 x 4000 transpose gains twice, and then stops at the time of the contiguous addition: its extra cost was waiting for lines from the L2 and the L3 (section 7), and that waiting is split between the cores, but the RAM limit is the same as for
a + c.
Where the threads are placed matters too. Put the same threads two per core, filling both hardware threads of a core before using the next:
| PyTorch, ms, two per core | 1 thread | 2 | 4 | 8 | 16 |
|---|---|---|---|---|---|
1000 x 1000, a + c | 0.079 | 0.080 | 0.045 | 0.025 | 0.017 |
4000 x 4000, a + c.t() | 10.6 | 20.4 | 10.4 | 6.07 | 5.33 |
Two threads on one core are no faster than one: they share the same units and caches. And for the 4000 x 4000 transpose they are twice as slow. Each thread needs its column of c, 250 KiB, to stay in the L2 until the next columns use it, and with two threads, plus the rows of a and out passing through, a shared 1 MiB L2 no longer holds them: every read of c goes back to the L3. It is a capacity problem, not a set conflict like section 8: with n = 3000 (two columns of 188 KiB) two threads on a core do not lose, and the loss grows from n = 3250 to 4000, also for sizes that are not powers of two.
Normally the operating system decides where threads go, and the result can change from one run to the next: I first saw the 20 ms by accident. The standard OpenMP variables fix the placement, OMP_PLACES=cores OMP_PROC_BIND=spread for the first table and OMP_PLACES=threads OMP_PROC_BIND=close for the second, and the script runs each table in its own process with them.
Threads are not free either: waking them and splitting the work costs time. That is why PyTorch does not split an operation with fewer than 32,768 elements, as the next article shows, and the threads article goes into how the work is split.
So more threads is not always better: they help while each core has its own data and its own caches to work with, and stop helping, or hurt, when they all wait for the same memory or share the same core.
Key takeaways
- The RAM is about a hundred times slower than the L1 (section 2), and the caches keep recent data close. On this CPU, about 0.7, 2.5 and 10 ns for the L1, the L2 and the L3, against 100 ns for the RAM.
- Reading in order is what the hardware is built for (sections 3 and 4). Memory moves in lines of 64 bytes, the prefetcher brings the next ones early, and many reads travel at once, so a loop that streams memory is limited by the bandwidth, not by the latency: it is memory-bound.
- Strides, pages and unlucky sizes each take part of that away (sections 5, 6 and 8): bytes of every line that nobody uses, address translations, and with rows of exactly 4096 bytes, a transpose thirty times slower here.
- A line is still in a cache only if what was read in between fits there (section 7). That is why a transpose costs 2.5 times or 6 depending on its size.
- SIMD wants neighbours, and no branches (sections 9 and 10). One instruction works on 4 to 16 floats that are next to each other in memory, and a wrong branch guess costs about 26 cycles here.
- Threads help while each one has its own core (section 11), and stop helping when they all wait for the RAM.
Further reading
- Ulrich Drepper, “What Every Programmer Should Know About Memory” (2007), the long and thorough version of sections 2 to 8.
- Igor Ostrovsky, “Gallery of Processor Cache Effects”, short experiments in the same spirit as these, with the same surprises.
- Randal Bryant and David O’Hallaron, “Computer Systems: A Programmer’s Perspective”, chapter 6, the memory hierarchy as a textbook explains it.
- Agner Fog’s optimization manuals, especially the microarchitecture guide, for how each CPU family does all of this, branch prediction included.
- Dan Luu, “Branch prediction”, how predictors work, from the simplest to the ones in today’s CPUs.
- The Stack Overflow question “Why is processing a sorted array faster than processing an unsorted array?”, the most famous version of the sorted row of section 10.
If something is not clear, or you think I got something wrong, leave a comment.