How PyTorch walks a tensor of any shape
pgmesa · · 35 min read
Part of Rebuilding PyTorch (3 of 8)
- 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
In the first article a tensor became a pointer, a shape and strides, and any view a new set of those numbers. That freedom has a price, and this article is about paying it. If a stride can be anything and the number of dimensions is only known at runtime, how do you write the loop that adds two tensors, and how do you make it as fast as adding two plain arrays?
The answer fits in two ideas, an odometer and a well-chosen inner loop, but it took me a long time to get there, and each step only makes sense once you have seen why the previous one fails. So this article goes slowly, one question at a time, in the order you meet them when you try to write this loop yourself. Every idea comes with the code that PyTorch runs and a measurement.
Before you start. This article builds on What a PyTorch tensor really is: strides, views and expanded tensors. Most of the code is C/C++ loops, and reading a
foris enough to follow it. Cache lines, SIMD and threads come up often; if they are new to you, the interlude on the hardware explains them, and this article links to its sections where they matter.
This is the path the article follows:
- The easy case: one flat loop.
- Why the flat loop stops working.
- First idea: one loop per dimension.
- Second idea: one flat loop that rebuilds the indices.
- The key observation: an odometer.
- Carrying the pointers or recomputing them.
- Not one element at a time: 2-D blocks.
- The second trap: the compiler.
- Threads, and the one division that remains.
But first, where this started for me: a broadcast that made my first tensor thirty times slower than NumPy. And at the end, the whole operation measured in the three libraries, what changes on a GPU, and the key takeaways.
Where this started for me
In 2024 I wrote my first tensor with strides, a small learning project in C/C++. Adding two tensors of the same shape was as fast as NumPy, which was very encouraging. As soon as one of them had to be broadcast, it was many times slower.
Here are the same two loops written cleanly in C/C++ and measured today, adding two 1000 x 1000 float32 tensors into an output that is already allocated, so that only the loop is timed:
a + b | C/C++ | NumPy |
|---|---|---|
| Same shape, a flat loop | 0.083 ms | 0.086 ms |
| Broadcasting a 1000 x 1 tensor, rebuilding each index | 2.56 ms | 0.089 ms |
The same speed as NumPy, until a dimension had to be repeated, and then thirty times slower. This is what finding an element in a broadcast tensor looked like:
// The flat index idx -> the position of that element in memory
int offset = 0;
for (int d = ndim - 1; d >= 0; d--) {
int coord = idx % shape[d];
idx /= shape[d];
offset += coord * strides[d];
}
A division and a modulo per dimension, for every element. I knew that this was the problem, and I did not know how to avoid it.
When I started Raxis, at first in Rust, I tried again and got a bit further. If two tensors have the same shape and are both contiguous, the number of dimensions does not matter: their elements are laid out in the same order, one after the other, so I could treat them as one long line and add them with a single loop. But as soon as one dimension was expanded, that trick was gone. The expanded dimension had to be repeated inside the loop, I was back to paying the modulo, and I did not see how to handle one, or several, broadcast dimensions in any position.
Looking back, two things looked like different problems: broadcasting, and handling any number of dimensions without writing that many nested loops. They are the same problem, because an expanded dimension is simply a stride of 0. If you can walk a tensor with arbitrary strides without dividing, you get both.
All the timings are from a Ryzen 7 9700X, on one thread, with 1000 x 1000 float32 tensors unless I say otherwise, measured in November 2026 with NumPy 2.5.4, PyTorch 2.14.1 and Raxis 0.5.0, and compiled with MSVC 19.44 on Windows 11 25H2. I also ran my loops with GCC 13.3 on Ubuntu 24.04 under WSL2, on the same machine: the numbers move a little, and the conclusions do not. The loops I wrote to measure each idea are in raxisadd_loops.cpp, and raxisadd_loops.py builds them and runs NumPy next to them.
1. The easy case: one flat loop
Start with the case that is easy. a and b have the same shape, both are contiguous, and the output is too. Then element number i of each tensor, counting in row-major order, is at position i of its memory, and the whole operation is this:
for (int64_t i = 0; i < numel; ++i)
out[i] = a[i] + b[i];
It does not matter whether the tensors have one dimension or six: if they are contiguous, the shape only tells you how to interpret the numbers, not where they are. This is the trick I used in Rust, and it is a good one. On a million floats this loop takes 0.083 ms, and NumPy’s np.add(a, b, out=out) takes 0.086 ms. You cannot do much better, and section 8 explains why.
Keep in mind two reasons why this loop is fast, because the rest of the article is about keeping them when the tensors are not this nice:
- It reads memory in order. The CPU does not read memory one number at a time, but in blocks called cache lines, of 64 bytes (16 floats) on most CPUs today. And when it sees that you read them one after another it fetches the next blocks before you ask for them (cache lines and the prefetcher, in the interlude).
- The compiler can turn it into vector instructions. Since
a[i],a[i + 1],a[i + 2], … are next to each other, it can load and add four or eight of them with one instruction. These instructions are called SIMD (single instruction, multiple data), and the compiler finding them on its own is called auto-vectorization. Section 8 looks at them in detail, because that is where the second trap is.
2. Why the flat loop stops working
The flat loop relies on one assumption: element number i is at position i. As we saw in the last article, the position of the element with indices is really
and for a contiguous tensor that sum happens to equal the flat index. For any other view it does not. Take the 3 x 4 tensor x from the last article, with the numbers 0 to 11, and three views of it:
| View | Shape | Strides | Positions, in the order you read the elements |
|---|---|---|---|
x | (3, 4) | (4, 1) | 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 |
x.t() | (4, 3) | (1, 4) | 0, 4, 8, 1, 5, 9, 2, 6, 10, 3, 7, 11 |
x[:, :1].expand(3, 4) | (3, 4) | (4, 0) | 0, 0, 0, 0, 4, 4, 4, 4, 8, 8, 8, 8 |
So x + x.t() cannot be a flat loop: the twelve numbers of x.t() are the same as those of x, in a different order. And x + x[:, :1].expand(3, 4) cannot either, because the second tensor only has three numbers, and each one has to be read four times.
You might think that this only happens with exotic views, but broadcasting produces them all the time. a + b with a of shape (1000, 1000) and b of shape (1000, 1) is computed as a + b.expand(1000, 1000), a tensor whose second stride is 0. Every bias added to a batch, every normalization by a mean, goes through this. So we need a loop that, for every element, knows its indices, or at least knows where it is in memory.
3. First idea: one loop per dimension
If you know how many dimensions there are, the loop writes itself. For two dimensions:
for (int64_t i = 0; i < shape[0]; ++i)
for (int64_t j = 0; j < shape[1]; ++j)
out[i * so0 + j * so1] = a[i * sa0 + j * sa1] + b[i * sb0 + j * sb1];
Each tensor has its own strides, so the same loop works for the transpose, for the expanded tensor and for any other view. There is no division anywhere: the indices are the loop variables, and the position is a multiplication and an addition per dimension, which a compiler can even turn into a pointer that it moves by a stride at every step.
The problem is that a library does not know how many dimensions it will get. a + b has to work for a vector, for a batch of images with four dimensions, and for whatever rank a user invents. You cannot write a variable number of nested fors. There are two obvious ways around that, and it is worth seeing why neither of them is what PyTorch does.
Write one version per rank. One function for one dimension, one for two, and so on up to some maximum, picked with a switch on the number of dimensions, or generated with templates. Some libraries do take the rank as a compile-time parameter: in Eigen’s Tensor module it is part of the type, Tensor<float, 3>. But PyTorch has hundreds of operators, each compiled for a dozen data types, and multiplying that by every rank multiplies the size of the binary. And, as we will see in a moment, it would buy nothing: the outer loops are not where the time goes.
Use recursion. One function that loops over dimension d and calls itself for dimension d + 1, until the last one, which runs a plain loop:
void recurse(size_t d, const float* a, const float* b, float* out) {
if (d == last) {
for (int64_t i = 0; i < shape[d]; ++i)
out[i * so[d]] = a[i * sa[d]] + b[i * sb[d]];
return;
}
for (int64_t i = 0; i < shape[d]; ++i) {
recurse(d + 1, a, b, out);
a += sa[d];
b += sb[d];
out += so[d];
}
}
This works for any number of dimensions and never divides. And it is fast: in the measurements of section 8 it takes 0.215 ms, the same as the solution PyTorch uses with the same inner loop. The function calls happen once per row, not once per element, so they cost nothing. So recursion is not slow. PyTorch does not use it for a different reason, which will only make sense in section 9, when the work has to be split between threads. Keep the question open until then.
4. Second idea: one flat loop that rebuilds the indices
The other way out is the one I took in 2024: keep a single flat loop over all the elements, from 0 to numel, and turn each flat index back into one index per dimension. It is the same as turning a number of seconds into hours, minutes and seconds: the remainder of dividing by 60 gives the seconds, the quotient carries on to the minutes, and so on. With x.t(), of shape (4, 3) and strides (1, 4), element number 7 is:
- last dimension:
7 % 3 = 1, and7 / 3 = 2carries on; - first dimension:
2 % 4 = 2; - indices (2, 1), so the position is
2 * 1 + 1 * 4 = 6.
And 6 is indeed the eighth number in the second row of the table above. In general, element number of a tensor with sizes is at
It is correct, and it is general. It is also very slow:
a + b, same shape | Time |
|---|---|
| Flat loop | 0.083 ms |
| Rebuilding the indices, 2 dimensions | 2.56 ms |
| Rebuilding the indices, 3 dimensions (100 x 100 x 100) | 3.83 ms |
Thirty times slower than the flat loop, and each extra dimension adds about 1.3 ns per element. That is the cost of one more integer division. A CPU can do several additions per cycle, but an integer division takes many cycles, and here every element needs one per dimension (on x86 the same instruction gives the quotient and the remainder, so % and / together cost one division). For comparison, the whole flat loop spends less than a tenth of a nanosecond per element.
You might wonder why the compiler does not make the division cheaper. It does when it can: a division by a constant, like n / 60, is turned into a multiplication and a shift, which is much faster. But here the divisor is shape[d], which is only known at runtime, so the compiler has to emit a real division. Remember this, because it comes back on the GPU at the end of the article.
The divisions are not the only problem. The positions that come out of this loop are not consecutive, even when the tensor is contiguous, as far as the compiler can tell. So it cannot vectorize the loop either, and we lose both reasons why the flat loop was fast.
5. The key observation: an odometer
Look at how the indices change from one element to the next, in x.t():
| Element | Indices | Position | What changed |
|---|---|---|---|
| 0 | (0, 0) | 0 | |
| 1 | (0, 1) | 4 | last index +1, so position +4 |
| 2 | (0, 2) | 8 | last index +1, so position +4 |
| 3 | (1, 0) | 1 | last index wraps to 0 (position back by 8, to 0), first index +1 (position +1) |
| 4 | (1, 1) | 5 | last index +1, so position +4 |
| 5 | (1, 2) | 9 | last index +1, so position +4 |
| 6 | (2, 0) | 2 | wrap, as in element 3 |
Almost always, only the last index moves, by one. Only when it reaches the size of its dimension does it go back to 0 and move the next one, and only rarely does that one overflow too. That is how the counter on a car’s dashboard that adds up the distance driven counts, the one with a row of digits that is called an odometer: when the last digit goes past 9 it goes back to 0 and the digit to its left moves by one. The indices of a tensor count the same way, except that each digit has its own limit instead of 10. In a 2 x 3 x 4 tensor the last index goes from 0 to 3, the middle one from 0 to 2 and the first one from 0 to 1. Mathematicians call a number like this, where each digit has its own base, a mixed-radix number. From here on I will call a counter like this the odometer.
So instead of rebuilding the indices from the flat position with divisions, keep them, and add one each time with a carry. And the position follows the same pattern with additions only:
- on a normal step, add the stride of the last dimension, ;
- when dimension wraps around, go back to its start, , and then add the stride of the dimension above it.
That subtracted term, the size times the stride, is constant, so it can be computed once per dimension before the loop. Step through it here. The widget has the three cases from section 2 on a 2 x 3 x 4 tensor: a contiguous one, a transposed view of one, and an expanded one, a (2, 1, 4) tensor with a stride of 0 in the middle:
- shape
- strides
- index
- offset
In the transposed view the positions jump around memory, and in the expanded one the counter reads each number three times. And it does not care: it never asks whether the tensor is contiguous or expanded, it only adds the strides it was given. That is broadcasting for free.
Now compare this with the first idea. The odometer’s indices are the variables of the nested loops from section 3, kept in an array instead of in the code. Adding one with a carry is exactly what nested loops do when the inner one ends and the outer one advances. So the odometer is the n nested loops, written as data, and that is why it works for any number of dimensions without dividing.
PyTorch’s version is DimCounter (pytorchTensorIterator.cpp, raxisdim_counter.cpp). It keeps the indices, one per dimension, in values, and its increment is exactly the carry:
// From DimCounter::increment, simplified: add `overflow` to the indices,
// starting at the fastest dimension, and carry while a dimension wraps
for (size_t i = 0; i < ndim && overflow > 0; i++) {
int64_t value = values[i] + overflow;
if (value >= shape[i]) {
overflow = 1;
value -= shape[i];
} else {
overflow = 0;
}
values[i] = value;
}
One detail before you go and read it: the dimensions are stored the other way round. values[0] is the fastest index, the one that changes on every step, which is the last dimension in the order you would write it in Python. The reason is in the next article: TensorIterator reorders the dimensions anyway, and putting the fastest one first makes “the inner dimension” always shape[0]. From here on, when I show PyTorch’s data, dimension 0 is the inner one.
Also note that increment does not add 1. It adds overflow, which can be a whole row or several rows at once. That is the subject of section 7.
6. Carrying the pointers or recomputing them
The widget keeps the position and updates it with additions and subtractions. DimCounter does not: it keeps only the indices. So where do the positions come from?
There are two ways to do it, and the two big libraries chose differently:
- NumPy carries the pointer. Its classic C iterator,
PyArray_ITER_NEXT, moves a pointer by the stride, and when a dimension wraps it subtracts what NumPy calls the “backstride”, , the distance back to the start of that dimension. That is what the widget does. - PyTorch recomputes the pointers from the indices, with a multiplication per dimension and per tensor (pytorch
TensorIteratorInternal.h, raxistensor_iterator.cpp):
// From get_data_ptrs: base pointer of every tensor + index times stride
std::copy(base.begin(), base.end(), ptrs);
for (size_t dim = 0; dim < ndim; dim++) {
int64_t value = counter[dim];
for (size_t arg = 0; arg < ntensors; arg++)
ptrs[arg] += value * strides[dim * ntensors + arg];
}
Multiplications, not divisions, so this is cheap. But it is still several multiplications per tensor, and doing that for every element would undo what we gained. It is fine because PyTorch does not do it for every element. That is the next question.
The indices are worth keeping anyway, because the counter needs them for two other things: to know how far it can go without a carry, in the next section, and to start in the middle of a tensor, in section 9. With the indices as the only state, the pointers are always derived from them, and there is nothing that can get out of sync.
7. Not one element at a time: 2-D blocks
Even with additions only, an odometer that advances one element at a time pays a few instructions and a branch per element just to keep count, on top of the addition we actually want. The fix is the same as in the recursive version: let the inner dimension be a plain loop, and run the counter only between rows. My first odometer did that, once per row. PyTorch goes one step further: it asks the counter how far it can go without a carry, and hands the whole stretch to the kernel at once.
That is max_2d_step (pytorchTensorIterator.cpp, raxisdim_counter.cpp):
// The rest of the current row, and if we are at the start of a row,
// as many whole rows of the next dimension as fit
int64_t step0 = std::min(shape[0] - values[0], range.end - offset);
int64_t step1 = 1;
if (step0 == shape[0])
step1 = std::min(shape[1] - values[1], (range.end - offset) / shape[0]);
return {step0, step1};
The answer is a 2-D block: step0 elements per row, step1 rows. And the loop that drives every elementwise operation in PyTorch is this (pytorchTensorIteratorInternal.h, raxistensor_iterator.cpp):
auto counter = DimCounter(shape, range);
while (!counter.is_done()) {
get_data_ptrs(ptrs, base_ptrs, strides, counter.values); // index times stride, per tensor
auto step = counter.max_2d_step(); // {row length, number of rows}
loop(ptrs, strides, step[0], step[1]); // the kernel does the rest
counter.increment(step);
}
The kernel, loop, receives a pointer to the first element of each tensor, the strides, and the size of the block. The strides come in one flat array, in bytes, first the inner stride of every tensor and then the outer stride of every tensor. It walks the block with two plain loops: inside a row it moves by the inner strides, and between rows by the outer ones.
Let us follow it on a real case: a + b with a of shape (1000, 1000) and b of shape (1000, 1). The tensors are the output, a and b, in that order, which is how PyTorch numbers them. In PyTorch’s order, with the inner dimension first, the iterator sees:
shape = [1000, 1000]
strides = [4, 4, 0, <- inner stride of out, a, b (bytes)
4000, 4000, 4] <- outer stride of out, a, b
b has a stride of 0 along the row, because the same value is added to the whole row, and 4 bytes between rows, because each row reads the next value of b. On one thread, the counter starts at indices [0, 0]:
max_2d_step: the rest of the row is the whole row, 1000, sostep1is the whole tensor, 1000 rows.- One call:
loop(ptrs, strides, 1000, 1000). incrementadds 1000 rows, the counter is done.
One call for the whole tensor. The counter, with its indices and pointers, ran once, against a million divisions in the version of section 4.
A 3-D case does not fit in one block. Take a + b with a of shape (100, 100, 100) and b of shape (100, 1, 100). In PyTorch’s order the shape is [100, 100, 100], and b’s strides are 4, 0 and 400 bytes. Each block can only span the two inner dimensions, so the loop makes 100 calls of 100 x 100 elements, and between calls the counter carries into the third dimension. That is 100 runs of get_data_ptrs, with 3 multiplications for each of the 3 tensors: 900 multiplications for a million elements.
There is one more step before any of this runs, and it is the subject of the next article: TensorIterator merges dimensions whenever their strides allow it. Adding two contiguous 1000 x 1000 tensors does not even reach the counter, because by then they are a single dimension of a million elements, and serial_for_each takes its one-dimensional shortcut (the ndim <= 1 branch). That is the generalization of my Rust trick, and it covers more cases than you might expect.
8. The second trap: the compiler
At this point I thought the problem was solved: an odometer that never divides, a plain loop for each row, and strides for any view. And yet that loop was not as fast as my flat loop. Here is the inner loop of each version:
// Flat: the compiler vectorizes it
for (int64_t i = 0; i < n; ++i)
out[i] = a[i] + b[i];
// Strides known only at runtime: it does not
for (int64_t i = 0; i < n; ++i) {
*out = *a + *b;
a += stride_a;
b += stride_b;
out += stride_out;
}
And here are all the versions so far, on two contiguous tensors of the same shape, with the output already allocated:
| Loop | Time |
|---|---|
NumPy, np.add(a, b, out=out) | 0.086 ms |
| Flat | 0.083 ms |
| Flat, with vectorization turned off | 0.204 ms |
| Odometer per row, strided inner loop | 0.213 ms |
| Recursion, strided inner loop | 0.215 ms |
| Rebuilding the indices per element | 2.56 ms |
Read the middle rows together. The odometer and the recursion take the same time, so with rows of 1000 elements, how you walk the outer dimensions does not matter. And both take the same time as the flat loop with vectorization turned off. So the whole difference with the flat loop is in the inner loop, and it has a name: vectorization.
Here is the detail promised in section 1. The SIMD instructions of a modern CPU work on several numbers at once: one instruction can load four consecutive floats into a register, another can add two registers of four floats, and another can store four floats. With AVX2 the registers hold eight floats. A compiler that sees the flat loop knows that a[i], a[i + 1], a[i + 2] and a[i + 3] are next to each other, so it loads them with one instruction and does four additions at a time. With vectorization turned off (#pragma loop(no_vector) in MSVC, #pragma GCC novector in GCC 14 and later) the same loop does them one by one, and takes 2.5 times longer. It is not 4 times because at this point the loop is limited by how fast the data can be moved, not by the additions.
Which SIMD instructions? Each CPU family has its own, from 4 floats per register (SSE2 on any x86-64, NEON on ARM64) to 16 (AVX-512); the table in the interlude lists them, with how to ask PyTorch and Raxis which ones they picked. The Ryzen 7 9700X of all the measurements here, a Zen 5, has AVX-512. My own loops in this article are compiled for the minimum, SSE2, which is what MSVC and GCC target by default on x86-64, so the vectorized ones work on 4 floats at a time.
/arch:AVX2in MSVC, or-mavx2in GCC and Clang, would let the compiler use AVX2, but then the program would not run on a CPU without it.
In the strided loop the compiler does not know the strides. The next element of a could be 4 bytes away or 4000, so it cannot load four of them with one instruction. It could check at runtime whether the stride is 1 and keep two versions of the loop, which compilers call loop versioning, or use a “gather” instruction that loads from scattered addresses, which is much slower (the interlude shows why). Some compilers sometimes do the first, but you cannot rely on it. Both compilers can tell you what they did with each loop, MSVC with /Qvec-report:2 and GCC with -fopt-info-vec-missed, and both report this one as not vectorized (MSVC 19.44 and GCC 13). So it runs one element at a time, even when the stride turns out to be 1.
If the compiler will not version the loop, the library can do it itself: look at the strides before the loop, and pick an inner loop that was written for that case. Which cases are worth it? Two:
- Every tensor contiguous along the row. Then it is the flat loop.
- Every tensor contiguous except one with stride 0, a broadcast operand. Then that operand is the same value along the whole row: load it once, copy it into all the lanes of a register, and use the flat loop for the rest.
My version that picks the loop like this gets 0.083 ms in the same-shape case, and 0.062 ms when b is broadcast (1000 x 1), against 0.089 ms for NumPy. The broadcast case is faster than the same-shape one because b is only a thousand numbers: there is a third less memory to read.
In my version the special loops are still plain C++ loops, out[i] = a[i] + b, and it is the compiler that turns them into SIMD instructions. That works for an addition, but it is still a bet: it depends on the compiler, on its version and on the flags, and on the operation being simple enough for it to see. Many are not. exp, tanh or erf call functions of the math library, one number at a time, and the compiler can only vectorize a loop around them if it has a vector version of that function, which depends again on the compiler and on the flags.
So PyTorch does not leave it to the compiler. Its kernels write the vector version themselves, with a small class, Vectorized<T>, that holds one SIMD register of Ts: eight floats with AVX2. Its operators are the CPU instructions, written by hand with intrinsics, the C++ functions that compile to exactly one instruction. This is its + for floats with AVX2 (pytorchvec256_float.h, raxisvec256_float.h):
inline Vectorized<float> operator+(const Vectorized<float>& a, const Vectorized<float>& b) {
return _mm256_add_ps(a, b); // one instruction: 8 additions
}
And an operator is written twice, once for one number and once for a whole register. This is Raxis’s add (raxisbinary_ops_kernel.cpp), and PyTorch’s kernels look the same:
cpu_kernel_vec(iter,
[](scalar_t a, scalar_t b) -> scalar_t { return a + b; }, // op
[](Vectorized<scalar_t> a, Vectorized<scalar_t> b) { return a + b; } // vop
);
The vector version is vectorized by construction, whatever the compiler does. And Vectorized<float> has its own exp, tanh or erf, which work on a whole register at once, written by hand or taken from SLEEF, a library of vectorized math functions. How Vectorized<T> is built, and how the same code gets compiled for SSE, AVX2 and AVX512, is the subject of the article on the kernels. For now it is enough to know that there are two functions, and that the loop decides which one to call.
That decision is made in the kernel that receives each 2-D block, VectorizedLoop2d (pytorchLoops.h, raxisloops.h):
// From VectorizedLoop2d::operator(), simplified
if (is_contiguous<traits>(strides)) { // every inner stride == sizeof(T)
for (int64_t i = 0; i < size1; i++) {
vectorized_loop(data, size0, 0, op, vop);
advance(data, outer_strides);
}
} else if (some input S has stride 0 and the rest are contiguous) {
for (int64_t i = 0; i < size1; i++) {
vectorized_loop(data, size0, S, op, vop);
advance(data, outer_strides);
}
} else {
for (int64_t i = 0; i < size1; i++) {
basic_loop(data, strides, 0, size0, op); // the plain strided loop
advance(data, outer_strides);
}
}
The checks run once per block, not per element. The two vectorized cases call vop; the strided one, basic_loop, calls op one element at a time and is back to depending on the compiler. Inside vectorized_loop (pytorchLoops.h, raxisloops.h) the stride-0 operand is loaded once as opt_scalar, a Vectorized with the same value in every lane, and the loop processes two vectors per iteration. The elements left at the end of the row, fewer than two vectors, go through basic_loop with op.
Back to the example of section 7. The inner strides were 4, 4 and 0 bytes: two contiguous tensors and one with stride 0. So the whole tensor goes through vectorized_loop, row by row, with b’s value of each row in a register.
Why not copy the broadcast operand?
There is another way to get a flat loop that you might think of: make b contiguous first, with b.expand(1000, 1000).contiguous(), and then add two contiguous tensors. Measured with NumPy, the copy alone takes 0.026 ms, and copy plus add takes 0.115 ms, against 0.089 ms without the copy and 0.062 ms for the stride-0 loop. And the time is not the worst part: b had 1000 numbers, and the copy has a million. Broadcasting exists so that you never have to materialize that.
The same idea does not help with the transpose either. np.add(a, c.T, out=out) takes 0.47 ms, and copying c.T to a contiguous tensor first and then adding takes 0.47 ms too: the copy has to read the transpose in the same scattered order, so it pays exactly what the addition was going to pay. The cost of a transpose is in the order in which memory is read, and no loop structure removes it. The next article shows what TensorIterator can do about the order.
9. Threads, and the one division that remains
On more than one thread, PyTorch splits the elements into ranges and gives one to each thread (pytorchTensorIterator.cpp, raxistensor_iterator.cpp):
// From TensorIteratorBase::for_each
if (numel < grain_size || get_num_threads() == 1) {
serial_for_each(loop, {0, numel});
} else {
parallel_for(0, numel, grain_size, [&](int64_t begin, int64_t end) {
serial_for_each(loop, {begin, end});
});
}
The ranges are flat: thread 1 gets elements 142,858 to 285,715, say, with no regard for where rows start or end. So each thread’s counter has to start at an arbitrary flat index, and it needs the indices of that first element. That is the one place where the division comes back: DimCounter’s constructor unravels the starting index with a division and a modulo per dimension, as in section 4 (pytorchTensorIterator.cpp, raxisdim_counter.cpp):
// From DimCounter's constructor: the indices of element range.begin
int64_t linear_offset = range.begin;
for (size_t dim = 0; dim < ndim; dim++) {
values[dim] = linear_offset % shape[dim];
linear_offset /= shape[dim];
}
Once per thread, not once per element. With 7 threads on our 1000 x 1000 example, each one gets 142,858 elements, and the second thread starts at element 142,858:
- constructor:
142858 % 1000 = 858and142858 / 1000 = 142, so the indices are [858, 142], in the middle of row 142; - first block: the rest of that row,
loop(ptrs, strides, 142, 1); - second block: the counter is at the start of a row, so whole rows,
loop(ptrs, strides, 1000, 142); - third block: the first 716 elements of the row where its range ends,
loop(ptrs, strides, 716, 1).
Three calls and two divisions for 142,858 elements.
Splitting has a cost, so it is not always worth it. Below 32,768 elements PyTorch does not split the work at all, and Raxis uses the same number (GRAIN_SIZE, pytorchTensorIterator.h, raxistensor_iterator.h): for less work than that, waking up the threads costs more than the work itself. How the threads share the work is in the article on reductions and threads.
And now we can close the question of section 3. Recursion was as fast as the odometer, so why does PyTorch use a counter? Because of this section. A thread’s range can start and end in the middle of a row, and the counter handles that naturally: it is built from the first element, it stops at the last, and max_2d_step produces the partial rows on its own. Starting a recursion in the middle of a tensor means computing the indices of the first element anyway, and then writing special first and last iterations at every level. A counter is also an object you can create, ask and advance from anywhere: the same DimCounter serves elementwise operations, reductions and copies, while recursion has to own the whole loop. The choice is about structure, not speed.
How fast is it now?
Here is the whole operation, a + b, single threaded, in the three libraries, each writing into an output allocated beforehand (np.add(a, b, out=out), torch.add(a, b, out=out) and raxis.add(a, b, out=out)), so that only the operation is timed. Without out= PyTorch and Raxis take the same time, because both reuse the memory of the previous result through their allocators.
a + b, into out | NumPy | PyTorch | Raxis |
|---|---|---|---|
| 1000 x 1000 + 1000 x 1000 | 0.070 ms | 0.072 ms | 0.072 ms |
| 1000 x 1000 + 1000 x 1 | 0.088 ms | 0.061 ms | 0.053 ms |
| 1000 x 1000 + 1 x 1000 | 0.099 ms | 0.060 ms | 0.057 ms |
| 100 x 100 x 100 + 100 x 1 x 100 | 0.11 ms | 0.13 ms | 0.089 ms |
| 1000 x 1000 + its transpose | 0.47 ms | 0.43 ms | 0.41 ms |
Same shape, all three run at the speed of memory. With broadcasting, PyTorch and Raxis are faster than NumPy: the stride-0 operand becomes a constant in a vectorized loop. And then there is the last row. The transpose costs six times more in all three libraries, and no odometer will fix that, because the problem is not counting the elements, it is the order in which they are read from memory.
Why the transpose costs so much
Remember the two reasons from section 1 why the flat loop is fast: it reads memory in order, in whole cache lines, and the compiler can vectorize it. The transpose loses both. A row of a is a column of c, 1000 floats 4000 bytes apart, so the vector loop is gone, and every read of c touches a different cache line.
Those lines are not wasted, though: the next 15 rows of a need the next 15 columns of c, which live in the same lines. So the question is whether a line is still in a cache when the loop comes back to it, and that depends on how much was read in between, one column of c. The interlude on the hardware works this out in Lines that come back: reuse: with n = 1000 a column is 62.5 KiB, more than the 48 KiB of the L1, so every read of c waits for the L2, and that is the factor of six. With n = 300 a column fits in the L1 and the transpose costs 2.5 to 4.6 times, and with n = 1024 it costs 30 times, for a reason of its own, cache sets.
None of this can be fixed in the inner loop, because it is about the order in which the elements are visited. That is where TensorIterator comes in, in the next article.
On the GPU it is different
A GPU does not walk a tensor with one counter: thousands of threads each handle their own element, and each one has to find it from its flat index, with no previous element to carry from. So on CUDA the division from section 4 comes back, per element. What PyTorch does there is make it cheap. Remember that a compiler turns a division by a constant into a multiplication and a shift, and cannot when the divisor is only known at runtime. PyTorch does that transformation itself, at runtime: when the iterator is built, it computes the “magic number” and the shift for each dimension’s size, once, and the kernels divide with a multiplication and a shift (pytorchIntegerDivider.cuh, raxisinteger_divider.cuh). The CUDA article shows how, with real numbers.
Key takeaways
- The flat loop is the fast one (section 1): it reads memory in order and the compiler vectorizes it. Views and broadcasting break it, because element
iis no longer at positioni. - Rebuilding the indices costs a division per dimension and per element (section 4), 30 times slower in the measurements here. An odometer advances them with a carry instead (section 5).
- The inner loop decides the speed (sections 7 and 8).
DimCounterhands the kernel 2-D blocks, and the kernel vectorizes the inner loop when its strides are contiguous or 0. - One division remains, where each thread’s range starts (section 9).
Further reading
- NumPy’s documentation on iterating over arrays, the same problem from the NumPy side.
- The TensorIterator episode of Edward Yang’s PyTorch Developer Podcast, a short tour of the whole machinery this article is the first piece of.
If something is not clear, or you think I got something wrong, leave a comment.