Interlude

What the CPU does when your code reads memory

pgmesa · · 70 min read

On this page

  1. 1. A CPU is fast, memory is not
  2. 2. The cache levels
  3. 3. Cache lines and the prefetcher
  4. 4. Many loads at once, and bandwidth
    1. Reads that do not wait for each other
    2. What bandwidth is
    3. How the RAM sends bytes: wires, transfers and bursts
    4. From a line of code to a burst
    5. Bandwidth measured: the addition
    6. Memory-bound and compute-bound
  5. 5. Pages and the TLB
  6. 6. Reading with a stride
  7. 7. Lines that come back: reuse
  8. 8. Where a line can go: cache sets
  9. 9. SIMD: one instruction, several numbers
  10. 10. Inside a core: running ahead, and guessing branches
  11. 11. Cores and threads
  12. Key takeaways
  13. Further reading
Rebuilding PyTorch · interlude
Part of Rebuilding PyTorch (an interlude)
  1. Why I rebuilt PyTorch's core from scratch
  2. What a PyTorch tensor really is
  3. Interlude: What the CPU does when your code reads memory
  4. How PyTorch walks a tensor of any shape
  5. How PyTorch prepares the loop of every operation
  6. How a PyTorch kernel uses the vector registers of every CPU
  7. How PyTorch sums a tensor, and splits the work between threads
  8. How PyTorch computes gradients
  9. 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:

  1. A CPU is fast, memory is not.
  2. The cache levels.
  3. Cache lines and the prefetcher.
  4. Many loads at once, and bandwidth.
  5. Pages and the TLB.
  6. Reading with a stride.
  7. Lines that come back: reuse.
  8. Where a line can go: cache sets.
  9. SIMD: one instruction, several numbers.
  10. Inside a core: running ahead, and guessing branches.
  11. 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:

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:

The caches of the CPU used in the seriesEight cores side by side. Each one runs two hardware threads and has its own L1 data cache of 48 KiB and its own L2 of 1 MiB. Below them, one L3 of 32 MiB shared by the eight cores, and below it the memory, two channels of DDR5 behind a memory controller that all the cores share.Ryzen 7 9700X: what is private to a core and what is sharedLatency of one load, measured: L1 0.7 ns, L2 2.5 ns, L3 about 10 ns, memory about 100 ns.core 0TTL148 KiBL21 MiBcore 1TTL148 KiBL21 MiBcore 2TTL148 KiBL21 MiBcore 3TTL148 KiBL21 MiBcore 4TTL148 KiBL21 MiBcore 5TTL148 KiBL21 MiBcore 6TTL148 KiBL21 MiBcore 7TTL148 KiBL21 MiBL3, 32 MiB, shared by the 8 coresMemory controller and RAM: 32 GiB, DDR5, 2 channels, shared by everyoneT: a hardware thread. The two threads of a core share its L1, its L2 and its units.
The CPU of every measurement in the series. A program's thread runs on one hardware thread at a time, and it sees the L1 and L2 of the core that runs it; the L3 and the memory are the same for all of them.

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.

LevelSizeWho has oneWays (section 8)
L1 data48 KiBeach core12
L21 MiBeach core16
L332 MiBthe whole CPU16
RAM32 GiBthe 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:

The chain experiment: a circle of cache lines and what the clock measuresFirst, a contiguous block split into 64-byte pieces, each one cache line, with the address of the next piece in its first 8 bytes. Second, the pieces linked into one circle, either in order, each pointing to its neighbour and the last back to the first, or shuffled into one single circle that jumps around the block. Third, the timeline: one lap without the clock, then three runs of 20 million steps of p = p->next; the fastest run divided by 20 million is the time per step.1. One contiguous block, one piece per cache line064128192256320384448nextpad...bytestruct alignas(64) Line { Line* next; char pad[56]; }: 8 bytes of address, 56 of filler,and every piece starts at a multiple of 64. A 256 MiB block is about 4 million pieces.2. Linked into one circleIn order12345678Each piece points to its neighbour, the last one back to the first. The number is the visit order.Shuffled15386274Each piece points anywhere in the block, but it is still one single circle through all of them.3. What the clock measuresone lap, no clockrun 1: 20 M stepsrun 2: 20 M stepsrun 3: 20 M stepsEvery step is p = p->next: the next address is inside the line being read.Result: the fastest run / 20 million = the time of one read, in ns.
The same steps run for every size from 16 KiB to 256 MiB, once in order and once shuffled. Eight pieces here; the real blocks have from 256 to about 4 million.

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 chainRandom orderWhere it lives
32 KiB0.72 nsL1
256 KiB2.53 nsL2
512 KiB2.53 nsL2
4 MiB9.0 nsL3
8 MiB10.5 nsL3
16 MiB19 nsL3, and the start of section 5
64 MiB81 nsRAM
256 MiB100 nsRAM

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 chainRandom orderIn order
32 KiB0.72 ns0.72 ns
256 KiB2.53 ns0.74 ns
4 MiB9.0 ns0.76 ns
256 MiB100 ns1.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 2262^{26} 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:

Reads in a chain against reads in flight at the same timeAbove, two reads from the RAM in a chain: the second starts only when the first one has arrived, so each costs the full 100 nanoseconds. Below, twelve independent reads: the core starts one every 4.2 nanoseconds without waiting, each one still takes 100 nanoseconds, but they overlap and the results arrive one every 4.2 nanoseconds.Reads that miss every cache: about 100 ns each, from the RAMEach bar is one read, from the moment the core asks for the line until the line arrives.In a chain: p = p->nextread 1read 2: its address is in read 12 readsThe next address is inside the line still on its way: 100 ns per read.Independent: out[i] = x[idx[i]]12 readsone every4.2 ns0 ns50 ns100 ns150 ns200 nsBelow, every read still waits 100 ns, but about 24 of them are on their wayat the same time, so one finishes every 4.2 ns: the 12 here take 146 ns, not 1200.
The first read of the chain gives the address of the second, so they cannot overlap. Inx[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 elementNumPyPyTorchRaxis
idx in order, 64 floats apart5.33.22.5
idx shuffled12.45.74.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:

8 bytes×4800 million per second=38.4 GB/s per channel,2×38.4=76.8 GB/s8 \text{ bytes} \times 4800 \text{ million per second} = 38.4 \text{ GB/s per channel}, \quad 2 \times 38.4 = 76.8 \text{ GB/s}

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.

From the core to the RAM: links, widths and bandwidthOn the left, the path of a read: the core, its L1 and L2, the shared L3, the memory controller and two DDR5 channels, one memory module each, every module split into two subchannels of 32 bits. On the right, one burst: sixteen transfers of 4 bytes on a subchannel are 64 bytes, one cache line; on DDR4, eight transfers of 8 bytes. At the bottom, the ceiling: 8 bytes per transfer times 4800 million transfers per second is 38.4 GB/s per channel, 76.8 GB/s for two.The path of a read, and how many bytes per second each part movesBandwidth measured with the a + b of this section; the RAM numbers are computed.Coreregisters and pointers of 64 bits (8 bytes)L1 and L2 of the corea + b from here: about 230 GB/sL3, shared by the 8 coresa + b from here: about 145 GB/sMemory controllerturns line requests into burstschannel 032 wires32 wires64 wires: 8 byteschannel 132 wires32 wires64 wires: 8 bytesOne cache line = one burstIn one transfer, every data wire carriesone bit; a burst is 16 transfers in a row.DDR5, one subchannel of 32 wires:16 transfers x 4 bytes = 64 bytesDDR4, one channel of 64 wires:8 transfers x 8 bytes = 64 bytesHow fast: DDR5-48004800 million transfers per second(two per tick of a 2400 MHz clock:double data rate, the DD of DDR).8 B x 4800 M/s = 38.4 GB/s per channel2 channels x 38.4 = 76.8 GB/sThe ceiling of the chips. a + b from the RAMreaches 56 GB/s of real traffic on one core.Three different sizes that are easy to mix up8 bytes a register or a pointer: what "64-bit CPU" means8 bytes one transfer of a channel: 64 wires, 1 bit each64 bytes a cache line: one burst, the unit the caches move
The machine of the series: two DDR5 modules, one per channel, at 4800 MT/s. A miss in the L3 becomes a request for one line, the controller sends it to one subchannel, and the line comes back as one burst. Four subchannels can each serve a different line at the same time.

Three sizes appear in the figure, and only one of them is about the CPU being “64-bit”:

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:

  1. Python and PyTorch. a + b ends, 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 at data_ptr + 4 * i.
  2. 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.
  3. 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).
  4. The L1. The core looks for the line that holds that address. Lines start at multiples of 64 bytes, and 64=2664 = 2^6, 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...a47 is byte 7 of the line that starts at 0x...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), so a[0] to a[15] share the first line, a[16] to a[31] the second, and the 4 MB of a are 62,500 lines.
  5. 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.
  6. 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.
The path of one read, from a pointer to a registerOn the left, the virtual addresses of a program: the stack, which holds the local variable p, a pointer of 8 bytes; the heap, which holds the data of the tensor a, two cache lines of 64 bytes; and the code. Reading p[16] asks for the 4 bytes 64 bytes after p, at a virtual address. In the middle, on the border between the virtual and the physical side, the TLB or a page walk translates it to a physical address. On the right, the core looks for the line in its L1 and L2, then in the L3 and the RAM, and the line comes back up into the caches while the 4 bytes go into a register, which has no address.Virtual: what the program seesPhysical: the hardwarefloat* p = a.data_ptr(); // a[0]float x = p[16]; // 64 bytes after pthe program's addresses, high ones on topstacka pile: locals, freed on returnp = 0x7ff6a3c41a008 bytes... unused addresses ...heapmalloc / new: until it is freeda[0] ... a[15]a[16] ... a[31]0x7ff6a3c41a000x7ff6a3c41a40a cache line each, 64 bytescodethe instructions, bytes tooload 4 bytes at p + 64p + 64TLBor page walk0x38e5f2a40one coreregistersno address; 16 of 64 bits, 32 of 512xmm0 = a[16]L148 KiBL21 MiBL332 MiB, shared by the coresRAMphysical pages of 4 KiBthe line at 0x38e5f2a40,in the physical page 0x38e5f2misses go down1234
One read, 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 floatsThree arraysns per element12 bytes / time
1,00012 KB0.052231 GB/s
64,000768 KB0.054222 GB/s
250,0003 MB0.083145 GB/s
1,000,00012 MB0.082146 GB/s
4,000,00048 MB0.16274 GB/s
16,000,000192 MB0.28542 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:

The pages of two programs, mapped to physical pages of the RAMOn the left, program A sees a tensor x as five pages one after another in its virtual addresses. On the right, program B has three pages of its own. In the middle, the RAM is a row of physical pages. The pages of x are mapped to physical pages 7, 2, 9 and 4, in no particular order; the pages of B to 0, 5 and 10; the other physical pages are free. The fifth page of x has not been written yet and has no physical page: the first write to it is a page fault, and the operating system gives it a free one, here physical page 11.Program Aits virtual addressesRAMphysical pages of 4 KiBProgram Bits own virtual addresses01: free23: free456: free78: free91011: freex, page 0x, page 1x, page 2x, page 3x, page 4not written yet: no page.The first write is a pagefault, and the OS givesit a free one.page 0page 1page 2x is contiguous in A's addresses, so the program reads it in order, page after page.In the RAM its pages are wherever the OS found free ones; only inside a page is the order kept.Each program has its own map, its page table, so B has no address that reaches A's pages.
Twelve physical pages for the example; the RAM of this machine has about eight million. The mapping is decided by the operating system, page by page, when each page is first written.

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 4096=2124096 = 2^{12} 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.

How a virtual address becomes a physical oneThe virtual address the program uses, 0x7ff6a3c41a40 in the example, has 64 bits: bits 48 to 63 are copies of bit 47, zeros here, and the rest is split in two: the number of the page, bits 12 and up, and the position inside the page, bits 0 to 11, of which bits 6 to 11 pick the L1 set and bits 0 to 5 the byte in the line. Only the number of the page is translated: the TLB gives it if it has the translation (a first level of 96 entries is looked up first, then a second of 4096), and otherwise a page walk reads up to four levels of the page table; if the page has no physical memory yet, that is a page fault, and the operating system takes a page and fills it with zeros. The position inside the page is copied unchanged into the physical address.Virtual address, the one the program usesbits 48-63copy bit 470000number of the pagebits 12-477ff6a3c41bits 6-11L1 setbits 0-5byte in the line101001000000position in the 4 KiB page: a40translatedTLBL1: 96checked firstL2: 4096if L1 misseshit0 or a few cyclesmissPage walkup to 4 reads of the page tableno page yet: a page fault,the OS gives one, zeroedcopied as is:the same in bothnumber of the physical page38e5f2bits 6-11bits 0-5101001000000Physical address, where the line is in the RAM4096 entries x 4 KiB pages: 16 MiB without a page walk.With 2 MiB pages, one entry covers 512 times more: 8 GiB.
Only the number of the page is translated: the low 12 bits, the position inside the page, are the same in both addresses. That is why the L1 can pick its set before it knows the physical address (section 8).

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, msNumPyPyTorchRaxis
1000 x 1000 (4 MB), Windows, new output0.570.070.07
1000 x 1000, Windows, out=0.080.070.08
4000 x 4000 (64 MB), Linux, new output7.0412.604.69
4000 x 4000, Linux, out=4.624.624.63

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 elementNumPyPyTorchRaxis
stride 1 (4 bytes)0.0740.0750.075
stride 2 (8 bytes)0.210.350.20
stride 8 (32 bytes)1.000.680.68
stride 16 (64 bytes)1.631.041.04
stride 64 (256 bytes)2.011.731.75
stride 1000 (4000 bytes)3.272.082.09
Floats used per cache line with a strideTwo cache lines of 16 floats each. With stride 1 all 32 floats are used; with stride 2, 16; with stride 8, 4; with stride 16, one per line. The whole line comes from memory in every case.x[::s]: the floats used from each 64-byte lineTwo lines of x, 16 floats each. Filled: read by the loop. Empty: brought from memory anyway.stride 116 of 16 floats per line used, and the prefetcher brings the next line earlystride 28 of 16 floats per line usedstride 82 of 16 floats per line usedstride 161 of 16 floats per line used: a whole line for one float
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.

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 + cNumPyPyTorchRaxis
n = 3004.4x4.6x2.5x
n = 10005.9x5.9x5.3x
n = 40002.9x2.2x2.3x

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 + cNumPyPyTorchRaxis
n = 10005.9x5.9x5.3x
n = 102429x32x33x

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.

Where the lines of a column land in L2The 1024 sets of the L2 cache drawn as a 32 by 32 grid. With rows of 4000 bytes, the 1000 lines of a column spread over almost every set, one or two each. With rows of 4096 bytes, the 1024 lines fall into 16 sets, 64 lines for 16 slots each, so most of them are evicted before they are used again.One column of c in L2: 1024 sets, 16 lines eachEach square is a set. A line goes to the set given by bits 6 to 15 of its address.n = 1000: rows of 4000 bytes606 sets used, at most 2 lines per setfits: the next columns reuse the linesn = 1024: rows of 4096 bytes16 sets used, at most 64 lines per set64 lines for 16 slots: evicted before reuse
The L2 sets that the 1000 or 1024 lines of one column of 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:

InstructionsWhere you find themBitsFloats
SSE2every x86-64 CPU (the minimum)1284
AVX2most x86 CPUs since 2013-20152568
AVX-512Intel Xeon, AMD Zen 4 and 551216
NEONevery ARM64 CPU: Apple M, Raspberry Pi 3+, phones1284
SVEsome ARM servers (AWS Graviton3: 256 bits)128-20484-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.

A vector load needs consecutive floatsAbove, the first eight floats of x go into the eight lanes of an AVX2 register with one load. Below, the floats of x[::2] are every other one, so they come from sixteen positions and cannot be loaded with one plain instruction.Memory to an AVX2 register: 8 floats, 32 bytesTop row: memory of x, one float per box. Bottom row: the eight lanes of the register.x[0:8]: one load, vmovups012345678910111213141501234567registereight lanes, one instructionx[::2]: the floats are 8 bytes apart012345678910111213141502468101214registerone load per lane, or a gather, which costs about the same
A plain vector load reads 32 consecutive bytes from one address. With a stride there is no such block, so PyTorch adds those rows one element at a time.

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:

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:

The pieces of one core and the memory below it, with the section that explains eachInside one core, from top to bottom: two hardware threads, the front end with the branch predictor, the out-of-order window, the execution units (integer, vector, loads and stores with the TLB), the L1 with the slots for reads in flight and a prefetcher, and the L2 with another prefetcher. Below the core: the L3 shared by the eight cores, the memory controller and the RAM. On the right, what the code decides (the instructions, and through them which addresses are read and in what order) and what the hardware decides (everything else), and what the operating system decides (where each thread runs, and where each page is).One core (8 in this CPU)Two hardware threadssec. 11thread 0thread 1Front endsec. 10reads and decodes; the branch predictor guesses the pathOut-of-order windowsec. 4, 10hundreds of instructions, each runs when its inputs are readyExecution unitssec. 5, 6, 9integervector (SIMD)load/store + TLBL1, 48 KiBsec. 2, 3, 4, 8slots for the reads in flight; a prefetcherL2, 1 MiBsec. 2, 3, 7, 8another prefetcherL3, 32 MiBsec. 2, 7shared by the 8 coresMemory controllersec. 4turns line requests into burstsRAM, 32 GiBsec. 4two channels, 76.8 GB/s at mostYour code decideswhich instructions run,and through them whichaddresses are read, andin what order (sec. 6, 7).The hardware decideswhen each instruction runs,which path to guess,how many reads are in flight,which lines come early,which lines stay in eachcache and which leave.The operating systemdecides which softwarethread runs on eachhardware thread (sec. 11),and maps the pages (sec. 5).
Each arrow points one level further from the instructions. A load starts in the execution units and goes down only as far as it has to: to the first level that has its line.

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:

A branch guessed right against a branch guessed wrongAbove, the predictor guessed right: the core keeps running the instructions after the jump while the comparison waits for its input, and nothing is lost. Below, it guessed wrong: when the comparison is finally known, everything done along the guessed path is thrown away, and the core starts again from the right path, about 26 cycles later than with a right guess.if (x[i] < t): the core does not wait for the answerIt guesses the path and keeps going; the guess is checked when the comparison is known.Guessed rightifguessed path: the next instructions, and the next iterationsGuessed wrongifwrong pathright path, from the startthe comparison is knownthrown away, and the front end restartsabout 26 cycles (5 ns) lost per wrong guess on this CPU
The comparison waits for its input, here a load, and the core does not stop meanwhile. With a right guess that time was useful; with a wrong one it was wasted, and the right path only starts once the guess is found to be wrong.

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:

KeptWith a branchWithout
none0.190.27
10%0.700.26
25%1.460.26
half2.540.26
75%1.510.27
90%0.740.27
all0.190.28
half, with x sorted0.190.27

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:

NumPyPyTorchRaxis
//, positive1.271.281.30
//, mixed signs3.433.221.30
%, positive1.271.861.34
%, mixed signs3.304.951.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.

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, ms1 thread24816
1000 x 1000, a + c0.0770.0440.0260.0200.013
1000 x 1000, a + c.t()0.4690.2420.1310.0710.072
4000 x 4000, a + c4.544.364.434.714.86
4000 x 4000, a + c.t()10.76.044.924.935.07

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 core1 thread24816
1000 x 1000, a + c0.0790.0800.0450.0250.017
4000 x 4000, a + c.t()10.620.410.46.075.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

Further reading

If something is not clear, or you think I got something wrong, leave a comment.