How PyTorch prepares the loop of every operation
pgmesa · · 40 min read
Part of Rebuilding PyTorch (4 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 last article we wrote the loop: an odometer that walks any strides without dividing, and an inner loop that the compiler, or Vectorized<T>, turns into SIMD instructions. But that loop received everything already prepared: one shape, the strides of every tensor in bytes, the inner dimension first, an output to write to, and one type for all of them. Someone had to compute all that from a + b. That someone is TensorIterator, and this article is about everything it does before the loop starts.
It looks like bookkeeping, and some of it is. But in this bookkeeping are the decisions that make an operation fast or slow, and the ones that decide whether its result is right: which type it is computed in, in what order memory is read, whether two dimensions can be walked as one, and what happens when the output is also one of the inputs. The last one is the most interesting, because PyTorch does not solve it completely, and there is a good reason why.
It is also a long article, because there is a lot of machinery, and almost every operation in PyTorch goes through it. Each section is one step of that machinery, so it can be read a few sections at a time.
Before you start. This article builds on the previous two: What a PyTorch tensor really is (strides, views, contiguity, dtypes) and How PyTorch walks a tensor of any shape (the odometer, 2-D blocks and the vectorized inner loop). The costs of section 7 depend on the caches, which the interlude on the hardware explains. Some C/C++ will help, but most of the article is about the values that come in and out of each step, in tables.
This is the path the article follows:
- Hundreds of operations, one iterator.
- The operands, and which ones are written.
- The shape: broadcasting.
- The strides: a broadcast dimension is a stride of 0.
- The type: promotion, and what it costs on the CPU.
- When the output already exists:
out=. - The order: which dimension goes inside.
- Merging dimensions.
- When the output shares memory with an input.
- Back to the loop.
And at the end, the key takeaways.
All the timings are from a Ryzen 7 9700X, on one thread, with float32 tensors and outputs allocated beforehand (out= in NumPy, PyTorch and Raxis) unless I say otherwise. They come from raxistensoriterator.py, which runs every case in the three libraries, in November 2026, with NumPy 2.5.4, PyTorch 2.14.1 and Raxis 0.5.0, on Windows 11 25H2 (MSVC 19.44). I also ran it with GCC 13.3 on Ubuntu 24.04 under WSL2, on the same machine: the numbers move, and the conclusions hold, with one exception that I point out in section 8.
1. Hundreds of operations, one iterator
PyTorch has hundreds of operations that work element by element: add, mul, exp, where, the comparisons, the casts, copy_. Every one of them has to do the same work before computing anything: find the shape of the result, check that the tensors are on the same device, pick a type, allocate the output, and walk the elements. Writing that once per operation would be hundreds of copies of the same code, each with its own bugs.
So PyTorch writes it once, in TensorIterator, and an operation is reduced to two things: a description of its tensors, and the code for one element. This is how Raxis’s add describes its tensors (raxisbinary_ops.cpp):
auto iter = iterator::binary_op_config() // the rules that every binary op shares
.resize_outputs(true)
.add_output(out) // undefined for a + b, or the out= tensor
.add_input(a)
.add_input(b)
.build(); // all the work of this article
add_stub(iter.device_type(), iter); // the kernel for this device
PyTorch’s is the same, spread over a macro and a function (pytorchTensorIterator.cpp, pytorchBinaryOps.cpp). The configuration says which rules apply: promote the inputs to a common type, allow a CPU scalar next to GPU tensors, refuse to write a float result into an integer output. The kernel, the code for one element, is the lambda from the last article: a + b for one number and for one Vectorized.
binary_op_config is one of a handful of presets that operations share (pytorchTensorIterator.h, raxistensor_iterator.h). binary_op is for arithmetic, like add, mul or pow. binary_float_op is for the ones whose result is always floating point, like div and atan2. comparison_op is for eq, lt and the rest, which write bool. unary_op and unary_float_op are for neg or abs, and for exp or sqrt. nullary_op has an output and no inputs, for the random fills like uniform_. And reduce_op is for sum, max and the other reductions. Many operations build a configuration of their own instead: copy_ and every cast, fill_, where, indexing, gather and scatter. They all end up in the same build(). The examples of this article are binary and unary operations. Reductions are a variation, with an output that does not move along the reduced dimensions, and they get an article of their own, together with threads.
Everything in between is build(). Here it is in Raxis (raxistensor_iterator.cpp), and PyTorch’s has the same steps in the same order (pytorchTensorIterator.cpp):
populate_operands(config); // outputs first, then inputs
compute_mem_overlaps(config); // can the outputs be written safely?
compute_shape(config); // broadcasting
mark_resize_outputs(config); // an out= tensor of another shape
compute_types(config); // common dtype, device, temporaries
if (!fast_setup()) { // a shortcut for the common case
compute_strides(config); // strides in bytes, 0 where broadcast
reorder_dimensions(); // the order of the loop
allocate_outputs(); // with the layout of the inputs
coalesce_dimensions(); // merge dimensions where possible
}
The sections of this article follow these steps, with one example carried through all of them where it helps. The overlap checks come almost first in the code, but they make more sense at the end, once we know how the loop will run.
2. The operands, and which ones are written
TensorIterator calls the tensors its operands, and keeps them in one list: the outputs first, then the inputs. a + b has three operands, out, a and b, in that order, which is the order of the strides in the last article.
The output does not need to exist. For a + b it is undefined, and TensorIterator allocates it later, when it knows its shape, its type and its layout. With torch.add(a, b, out=c) it is c, and every decision of this article has to work around it.
There is a third case: an in-place operation. a.add_(b) is add with out=a, so a is both an output and an input. TensorIterator notices it and marks the output as is_read_write, in mark_outputs in PyTorch and in populate_operands in Raxis (pytorchTensorIterator.cpp, raxistensor_iterator.cpp). That flag matters twice: an in-place output cannot be resized, in section 6, and it is allowed to share memory with an input, in section 9.
3. The shape: broadcasting
The shape of the result comes from broadcasting the shapes of the operands, and the rule is the one NumPy made popular:
- Align the shapes on the right, and pretend that the shorter one has dimensions of size 1 on the left.
- In every position, the sizes must be equal, or one of them must be 1.
- The result takes the size that is not 1.
This is what it looks like with b of shape (3, 1) and c of shape (4,):
b + c with b of shape (3, 1) and c of shape (4,). Neither input is copied or expanded in memory: the repeated cells are what a stride of 0 reads.In the same way, (1000, 1000) and (1000,) give (1000, 1000), and (2, 3) and (4,) are an error, because 3 and 4 are different and neither is 1. NumPy’s guide to broadcasting explains the rule very well, with more examples and figures. In code it is a loop over the dimensions from the right (pytorchExpandUtils.cpp, raxisshape_utils.cpp), and compute_shape applies it to one operand after another (pytorchTensorIterator.cpp, raxistensor_iterator.cpp).
One detail: the result takes the size that is not 1, not the larger one. They are the same thing except for one case, a size 0 against a size 1, where the result is 0. Broadcasting an empty tensor gives an empty tensor.
The outputs are left out of this computation when they will be resized (section 6), so the shape of the result depends only on the inputs. An in-place output still takes part, as the input it also is.
4. The strides: a broadcast dimension is a stride of 0
Now every operand needs strides for that shape. The last article showed the trick: a dimension that is broadcast gets a stride of 0, so the loop reads the same element again and again without knowing that anything special is happening. compute_strides does exactly that, and converts the strides to bytes on the way, because the loop moves char* pointers and tensors of different types can meet in the same loop (pytorchTensorIterator.cpp, raxistensor_iterator.cpp):
// From compute_strides: align on the right, 0 where the operand has size 1
// and the result does not, the stride in bytes everywhere else
for (int i = 0; i < original_ndim; ++i) {
int ti = offset + i; // the missing dimensions on the left stay 0
if (original_shape[i] == 1 && shape_[ti] != 1)
stride_bytes[ti] = 0;
else
stride_bytes[ti] = original_stride[i] * itemsize;
}
Take the b and c of the figure, both contiguous float32: b + c has shape (3, 4).
| Operand | Shape | Strides (elements) | Strides after broadcasting (bytes) |
|---|---|---|---|
| out | (3, 4) | not allocated yet | not known yet |
b | (3, 1) | (1, 1) | (4, 0) |
c | (4,) | (1,) | (0, 4) |
The stride of b along its size 1 dimension was 1, and it becomes 0. Its stride of 1 element in the first dimension becomes 4 bytes. c has no first dimension at all: it is the one padded on the left, and it gets a stride of 0 too. Neither tensor was copied or expanded: these are new numbers in TensorIterator, and the tensors are as they were.
5. The type: promotion, and what it costs on the CPU
int_tensor + float_tensor cannot be computed in two types at once, so before the loop there has to be one type for the operation, what PyTorch calls the common dtype. Its rules are in the documentation of torch.dtype, and they are more subtle than “the larger type wins”.
The types are grouped in categories, ordered bool < integer < floating point < complex. For any two types, a table says which type holds both: int32 and int64 give int64, uint8 and int8 give int16, int64 and float32 give float32 (pytorchScalarType.cpp). But the operands do not all have the same weight. PyTorch splits them in three groups:
- Tensors with dimensions, like a (1000, 1000) tensor.
- Zero-dimensional tensors, like
torch.tensor(5.0). - Python numbers, like the
2.5inx + 2.5. PyTorch turns them into zero-dimensional tensors marked as “wrapped numbers”, and a Python float counts as the default float type,float32, not as thefloat64it is.
Each group gets its own type with the table, and then the groups are combined: the tensors with dimensions decide, unless a group with fewer dimensions has a higher category, and then the type of that group wins (pytorchTypeProperties.cpp, raxistype_promotion.cpp). It is easier to see with examples, all run in both libraries:
| Operation | Result | Why |
|---|---|---|
float32 tensor + float64 tensor | float64 | Two tensors with dimensions: the table |
float32 tensor + float64 0-d tensor | float32 | Same category, the tensor with dimensions decides |
int32 tensor + int64 0-d tensor | int32 | The same |
int32 tensor + float64 0-d tensor | float64 | The 0-d tensor has a higher category |
int32 tensor + 2.5 | float32 | Higher category, and a Python float counts as float32 |
uint8 tensor + 300 | uint8, and 1 + 300 gives 45 | Same category, the tensor decides, and 301 wraps around 256 |
The reason for this design is that a number written in the code should not change the type of a big tensor. x * 0.5 on a float32 tensor stays float32, instead of becoming a float64 tensor of twice the size, which is what a strict “larger type wins” would do. The last row is the price: the scalar does not widen anything, so the result overflows silently.
What it costs
The common dtype is one type, and the tensors may still be of another. On the CPU, TensorIterator solves it in the simplest way: it converts every input of another type into a temporary tensor of the common type, before the loop (pytorchTensorIterator.cpp, raxistensor_iterator.cpp):
// From compute_types: on the CPU, an input of another type becomes a copy
if (config.promote_inputs_to_common_dtype_ && !op.is_output &&
op.current_dtype != common_dtype_) {
op.exchange_tensor(MaybeOwned<Tensor>::owned(op.tensor().to(common_dtype_)));
op.current_dtype = common_dtype_;
}
Why not convert each element inside the loop? Because the fast loop is the one from the last article, with Vectorized<T>: one register of Ts for every operand, and that needs every operand to be a T. A kernel that loads a float and a double and converts one of them would need a vector version for every pair of types. The temporary keeps a single typed loop, at the price of one extra pass over memory:
Into a float64 output | NumPy | PyTorch | Raxis |
|---|---|---|---|
float64 + float64 | 0.143 ms | 0.145 ms | 0.145 ms |
float32 + float64 | 0.336 ms | 0.360 ms | 0.345 ms |
The conversion of the float32 input reads 4 MB and writes a temporary of 8 MB, and then the addition reads it again. NumPy pays the same, in its own way: its loops also work on one type, and it converts in buffers.
On the GPU it is different. An elementwise GPU kernel is usually limited by memory, not by instructions, so converting while loading costs almost nothing, and PyTorch’s CUDA kernels do just that: they load each input with its own type and convert it in registers, with no temporary (it calls it dynamic casting). Raxis’s CUDA kernels do the same (raxistensor_iterator.cpp). The CUDA article comes back to it.
6. When the output already exists: out=
So far the output was created by TensorIterator. With out=, or in place, it already exists, with its own shape, type and layout, and each of the three needs a decision.
The shape. If out has another shape and is not also an input, it is resized to the shape of the result. If it had elements, PyTorch warns, because it plans to stop doing this:
UserWarning: An output with one or more elements was resized since it
had shape [5], which does not match the required output shape [2, 3].
This behavior is deprecated, and in a future PyTorch release outputs
will not be resized unless they have zero elements. ...
An output with zero elements is resized without a warning, reusing its memory when it is large enough, which is what the warning suggests: t.resize_(0), and then out=t in every call. Raxis already does what PyTorch plans: an output with elements and another shape is an error, and only one with zero elements is resized. Either way, the decision is mark_resize_outputs, which sets a flag, will_resize, so that the steps that follow treat that output as if it did not exist yet (pytorchTensorIterator.cpp, raxistensor_iterator.cpp). If the output is also an input, it cannot be resized, because the input would change under the operation, and a shape that does not match is an error. Section 9 shows why this matters more than it seems.
The type. The common dtype is computed from the inputs only, and the output does not change it. If the output is of another type, two things happen. First a check, that the result can be converted to it without changing category downwards: float into int64 is an error, int64 into int32 is allowed, and truncates.
>>> torch.add(torch.ones(2), torch.ones(2), out=torch.empty(2, dtype=torch.int64))
RuntimeError: result type Float can't be cast to the desired output type Long
And then, on the CPU, the same trick as with the inputs, the other way round: the loop writes into a temporary of the common type, and at the end cast_outputs copies it into the real output, converting (pytorchTensorIterator.cpp, pytorchTensorIterator.cpp, raxistensor_iterator.cpp, raxistensor_iterator.cpp). You can see it in the result, because the operation is computed in the common type, not in the type of the output:
>>> out = torch.empty(1, dtype=torch.float64)
>>> torch.add(torch.tensor([1], dtype=torch.int32), 0.1, out=out)
>>> out.item()
1.100000023841858
The common type is float32 (an int32 tensor and a Python float), so 1.1 is computed in float32 and then widened. A float64 output does not buy precision. And it costs:
a + b, float32 inputs | NumPy | PyTorch | Raxis |
|---|---|---|---|
into a float32 output | 0.076 ms | 0.074 ms | 0.076 ms |
into a float64 output | 0.267 ms | 0.274 ms | 0.274 ms |
The layout. An output that is not resized keeps its strides. torch.add(a, b, out=c.t()) writes into the transpose of c, as you asked, and the result is still c.t(). That looks harmless, and it is not: the output is operand 0, and in the next section operand 0 is the one that decides the order of the loop.
7. The order: which dimension goes inside
Back to the case that the last article left open. a + c.t() took six times longer than a + c, and no loop structure could fix it, because the problem was the order in which memory is read (the interlude on the hardware explains why that order costs so much). But there is a related case that does have a solution: a.t() + c.t(). Both tensors are transposes, so their elements are in memory in the order of their columns. If the loop walked them in their logical order, row by row, it would jump 1000 elements between consecutive reads in both tensors. But nothing forces the loop to walk the elements in that order. Elementwise, the result is the same in any order, so the loop can just as well walk the columns, and then both tensors are read contiguously.
Choosing that order is reorder_dimensions (pytorchTensorIterator.cpp, raxistensor_iterator.cpp). It computes a permutation of the dimensions, perm, sorted so that the dimension with the smallest strides goes first, which in TensorIterator’s order is the inner one. This is where the reversed order in the last article comes from: perm starts as the dimensions from the last to the first, so for a contiguous tensor nothing moves.
The sort is an insertion sort with a comparison of two dimensions, should_swap, that looks at the operands one by one, outputs first (pytorchTensorIterator.cpp, raxistensor_iterator.cpp):
// From should_swap, simplified: should dim0 go after dim1?
for (each operand) {
if (stride0 == 0 || stride1 == 0) continue; // broadcast: ask the next one
if (stride0 < stride1) return -1; // dim0 goes first
if (stride0 > stride1) return 1; // swap them
// equal strides: a tie-break by size, or the next operand
}
return 0; // nobody knows: keep the order
The first operand with an opinion decides. An operand whose stride is 0 in one of the two dimensions has none, because a broadcast dimension says nothing about memory.
Follow a.t() + c.t(), with both of shape (1000, 1000), and an output that does not exist yet:
- Strides in bytes, in the logical order of the dimensions:
a.t()andc.t()have (4, 4000). permstarts as [1, 0], the last dimension inside: in that order the strides are [4000, 4].should_swap(1, 0): the output does not exist, so it asksa.t(). Its stride in dimension 1 is 4000 bytes, and in dimension 0 it is 4: 4000 > 4, swap.permis [0, 1]: dimension 0 goes inside, and both tensors have a stride of 4 bytes there.
The output takes the layout of the inputs
When the output does not exist, it is allocated now, after the order is known, and with that order (pytorchTensorIterator.cpp, raxistensor_iterator.cpp). TensorIterator computes contiguous strides in its own order, the inner dimension first, and puts them back in the logical order of the dimensions with the inverse permutation. So for a.t() + c.t() the output gets strides (1, 1000): it is a transpose too.
>>> (a.t() + c.t()).stride()
(1, 1000)
That is what you want, for two reasons. The loop writes the output contiguously as well. And the next operation with that result will find it laid out as its other operands, and will have the same choice. A permuted input gives a permuted output, in PyTorch and in Raxis: x.permute(2, 0, 1) + 1 has the strides of x.permute(2, 0, 1).
When the operands disagree
With a + c.t() there is no order that suits both: a wants its rows inside and c.t() its columns. Then the first operand with an opinion wins. The output does not exist, so it is a, and c.t() is read with a stride of 4000 bytes. That is the case that costs six times more, in every library.
And here comes back the warning of section 6. With out=, the output exists, it is operand 0, and it is asked first:
| NumPy | PyTorch | Raxis | |
|---|---|---|---|
a + c | 0.070 ms | 0.074 ms | 0.076 ms |
a.t() + c.t(), into out.t() | 0.073 ms | 0.075 ms | 0.080 ms |
a + c.t(), into out | 0.475 ms | 0.427 ms | 0.410 ms |
a + c, into out.t() | 0.472 ms | 0.761 ms | 0.729 ms |
The second row is the reordering at work: two transposes cost the same as two contiguous tensors. The last row is the rule of the first operand: the output decides that the loop goes along its columns, and now both inputs are read with a stride of 4000 bytes, not one. NumPy asks all the operands, and when they disagree it keeps the logical order, so here it takes the same 0.47 ms in the last two rows. That does not make its rule better, only different: when the operands disagree it follows none of them, and the next case is one where that loses.
a + b is not b + a
The rule of the first operand has a curious consequence: the order in which you write an addition can change its speed. With a of shape (300, 300, 300) and b a tensor of the same shape permuted with permute(2, 0, 1), and outputs allocated by the operation:
a + b vs b + a | NumPy | PyTorch | Raxis |
|---|---|---|---|
300 x 300 x 300, a + b | 36.8 ms | 20.7 ms | 20.5 ms |
300 x 300 x 300, b + a | 37.2 ms | 14.7 ms | 12.8 ms |
256 x 256 x 256, a + b | 68.2 ms | 51.4 ms | 53.3 ms |
256 x 256 x 256, b + a | 67.9 ms | 26.5 ms | 27.1 ms |
a + b follows the layout of a, and b + a that of b. In both orders the output is written in order and one input is read with a stride: in a + b it is b, jumping 300 floats, and in b + a it is a, jumping 90,000. The longer jump is the faster one. Remember reuse from the interlude on the hardware: what matters is not how far a read jumps, but how soon a cache line is used again, and whether the lines read in between fit in a cache. A line of the strided input holds 16 neighbours along one dimension. In b + a that dimension is the middle loop, so the line is needed again after 300 reads, 19 KB of lines, which stay in L1. In a + b it is the outer loop, so the line is needed again only after a whole plane of 90,000 reads, 5.8 MB of lines, which do not fit in L2 and come from the third level every time. NumPy keeps the logical order, which here is the order of a, in both cases: the same pattern as a + b, and with that pattern its loop is slower than PyTorch’s.
Here is the same thing on a model small enough to watch, and then with the real sizes against the caches of this CPU:
b + a uses them before they leave, a + b does not, and has to load the same lines of b again.a + b and b + a with a of shape (300, 300, 300) and b a permuted tensor of the same shape. Each read of the strided input touches a new cache line; the bars are how many bytes of lines pass before the loop needs the same line again, on a log scale against the cache sizes of this CPU.With 256 both orders get slower, because a row is 1 KiB and a plane 256 KiB, and the cache-set problem from the interlude comes back. How much each order suffers then depends on the geometry of each CPU’s caches, so the faster order can change from one machine to another. Away from those sizes the order holds: on an Intel laptop (an i5-12450H), at every size from 160 to 360 without powers of two, b + a was 2 to 5x faster.
The rule itself comes from pytorch#28615, in 2019: the first operand decides so that the output is written in order, and when the output is new, it also gets the layout of the first operand.
8. Merging dimensions
After the reordering, the operands are in the order that suits them best, and the last step can try to make the loop simpler: merge two dimensions into one whenever the strides allow it. coalesce_dimensions walks the dimensions from the inner one, and merges each one with the previous when, for every operand, the outer stride is exactly the inner one times the size of the inner dimension (pytorchTensorIterator.cpp, raxistensor_iterator.cpp):
// From can_coalesce: dims 0 (inner) and 1 can be walked as one
if (shape[0] == 1 || shape[1] == 1)
return true; // a dimension of size 1 never moves
for (each operand)
if (shape[0] * stride[0] != stride[1])
return false; // a row does not end where the next begins
return true;
The condition says that, after the last element of a row, the next row starts exactly where the next element would be, for every operand. Then the two dimensions are the same as one dimension with the inner stride, and shape[0] * shape[1] elements.
The rule is about strides, not about contiguity, and that makes it cover more cases than you might expect. These are real values of Raxis’s iterator for a + b, the strides in bytes of the output, a and b, the inner dimension first, after the reordering and the merge (a small debugging helper, raxis._C._binary_iterator_state, prints them):
a + b | Loop shape | out | a | b |
|---|---|---|---|---|
| (1000, 1000) + (1000, 1000) | [1000000] | [4] | [4] | [4] |
| (1000, 1000) + (1000, 1) | [1000, 1000] | [4, 4000] | [4, 4000] | [0, 4] |
| (1000, 1000) + expanded (1, 1) | [1000000] | [4] | [4] | [0] |
x[:, ::2] + y[:, ::2], 10 columns | [30] | [4] | [8] | [8] |
x[:, ::2] + y[:, ::2], 5 columns | [3, 6] | [4, 12] | [8, 20] | [8, 20] |
a.t() + c.t() | [1000000] | [4] | [4] | [4] |
a + c.t() | [1000, 1000] | [4, 4000] | [4, 4000] | [4000, 4] |
And two 3-D cases, with (100, 100, 100) tensors and a broadcast b:
b | Loop shape | out and a | b |
|---|---|---|---|
| (100, 1, 100) | [100, 100, 100] | [4, 400, 40000] | [4, 0, 400] |
| (1, 100, 100) | [10000, 100] | [4, 40000] | [4, 0] |
Row by row:
- Two contiguous tensors: one dimension of a million elements, which is the flat loop from the last article. This is the generalization of the trick I used in Rust.
- A column, (1000, 1):
bhas strides [0, 4]. The rule asks whether 1000 times 0 is 4, and it is not, so the loop stays 2-D: the stride 0 ofbrestarts on every row. This is the case of the last article, one call with 1000 rows. - An expanded scalar: strides [0, 0], and 1000 times 0 is 0. A broadcast does not always prevent the merge.
- Every other column:
x[:, ::2]is not contiguous, and with 10 columns it still merges. Its strides are 8 bytes inside a row and 40 between rows, and 5 elements times 8 bytes is 40: after the last element of a row, the next one is two elements further, as within the row. One dimension of 30, with a stride of 8 bytes. With 5 columns, the rows have 3 elements, at 0, 2 and 4, and the next row starts at 5, one element further, not two: 3 times 8 is not 20, and it stays 2-D. - Two transposes: the reordering puts their columns inside, and then they merge into one contiguous dimension. Reorder first, then merge.
- A tensor and a transpose: no order suits both, so nothing merges either.
- 3-D, the middle dimension broadcast: nothing can be merged, the loop stays 3-D, and the odometer from the last article carries into the third dimension 100 times.
- 3-D, the first dimension broadcast: the two inner dimensions merge, because
bis contiguous in both, and the broadcast dimension stays outside, alone.
x[:, ::2] over two rows of x, positions in elements. The rows merge when the jump from the end of one row to the start of the next is the jump inside a row, which is the ruleshape[0] * stride[0] == stride[1] (here 5 x 8 bytes == 40, and 3 x 8 != 20).What cannot be merged does not cost a division: the odometer walks it, and the 2-D blocks from the last article take the two inner dimensions in each call.
Why it matters
Merging does not change the work per element. It changes the work per row: every row is a new block, with its pointers, its checks of which inner loop to use, and its tail of elements that do not fill a vector register. That is invisible with rows of 1000 elements, and it is everything with short rows. The same million elements, in rows of 1000 and of 4:
| A million elements | NumPy | PyTorch | Raxis |
|---|---|---|---|
| (1000, 1000) + (1000, 1): rows of 1000 | 0.095 ms | 0.062 ms | 0.054 ms |
| (250000, 4) + (250000, 1): rows of 4 | 0.978 ms | 1.913 ms | 0.977 ms |
| (250000, 4) + (1, 1): merged into one row | 0.050 ms | 0.055 ms | 0.054 ms |
Rows of 4 cost 18 times more than rows of 1000, with the same data. The third row is the same shape, with a single number broadcast, which merges into one dimension and runs at the speed of memory. This is the exception I mentioned at the start: on Linux, rows of 4 take between 0.33 and 0.40 ms in the three libraries, about 6 times more than rows of 1000 instead of 18, and PyTorch is not slower than the others there. So the 1.9 ms seems to come from PyTorch’s Windows build, and I have not looked further into it. Either way, short rows are expensive.
And where it does not matter: x[:, ::2] + y[:, ::2] takes the same time with an even and an odd number of columns (0.36 ms in PyTorch, 0.24 ms in Raxis, with a million elements), because one long row and a thousand rows of about 1000 elements both run the strided inner loop, and the rows are long either way.
A shortcut for the common case
The most common case of all is the first row of the table: every tensor contiguous and of the same shape. For it, the reordering and the merge always give the same answer, one dimension with the size of an element as the stride, so fast_setup skips them and goes straight to that answer (pytorchTensorIterator.cpp, raxistensor_iterator.cpp). PyTorch’s shortcut also covers tensors that are all channels_last, or all laid out with the same permutation of a contiguous layout (pytorchTensorIterator.cpp). Raxis only takes it for contiguous tensors, and leaves the other cases to the general path, which reaches the same result.
9. When the output shares memory with an input
Back to the steps of section 1, to the one I skipped: compute_mem_overlaps. The loop from the last article reads and writes element by element, in the order that the iterator chose. That is only correct if writing an element of the output cannot change an input element that has not been read yet. When the output and an input are different tensors in different memory, that is obvious. Views make it anything but obvious.
The case that is fine: in place
a.add_(b) writes into a while reading a. It is correct because every element of the output is computed from the same element of the input, at the same position: a[i] = a[i] + b[i] reads a[i] right before overwriting it, and no other element ever needs the old a[i]. It does not matter in what order the loop goes. PyTorch calls this full overlap, and allows it.
An input that is broadcast cannot be the output
What if the broadcast operand is the output? With a of shape (3, 4) and b of shape (3, 1), a.add_(b) is fine: it adds the column b to every column of a. But b.add_(a) asks for something that cannot be written: the result has shape (3, 4), and b only has room for (3, 1).
>>> b.add_(a)
RuntimeError: output with shape [3, 1] doesn't match the broadcast shape [3, 4]
And torch.add(a, b, out=b) gives the same error, because b is also an input, so it cannot be resized either (section 6). It is worth seeing what would happen without that check, because it is exactly what Raxis did until I wrote this article. With the strides from section 4, b as an output would have a stride of 0 along the rows. The loop would then write the four sums of a row into the same element, one after the other, and keep the last one: no error, no crash, a wrong result. Raxis’s mark_resize_outputs now has PyTorch’s check (raxistensor_iterator.cpp).
An output that repeats elements
The same stride 0 can come from the user:
>>> x = torch.zeros(3)
>>> x.expand(4, 3).add_(1)
RuntimeError: unsupported operation: more than one element of the written-to
tensor refers to a single memory location. Please clone() the tensor before
performing the operation.
The expanded tensor has 12 elements and 3 memory positions, so each position would be written four times, each time reading what the previous write left. PyTorch calls this internal overlap.
An output that overlaps an input, shifted
The interesting case is two different views of the same memory:
>>> x = torch.arange(6.0)
>>> x[1:].add_(x[:-1])
RuntimeError: unsupported operation: some elements of the input tensor and the
written-to tensor refer to a single memory location. Please clone() the tensor
before performing the operation.
The intended result is x[i] = x[i] + x[i - 1] with the old values: [0, 1, 3, 5, 7, 9]. But a loop going forward writes x[1] before reading it as the input of x[2], so each element adds the new value of the previous one, and the result is a running sum, [0, 1, 3, 6, 10, 15]. A loop going backwards would give the intended result. And the iterator chooses the order, splits the work between threads, and vectorizes it, so the result would depend on all that. PyTorch calls this partial overlap, and refuses it. NumPy does not refuse it: x[1:] += x[:-1] gives [0, 1, 3, 5, 7, 9], because NumPy makes a temporary copy of the input when it detects the overlap.
a.add_(a.t()) on a square matrix is partial overlap too, although both tensors cover exactly the same memory: element (0, 1) of the output is computed from element (1, 0) of the input, which the loop may already have overwritten. PyTorch refuses it, and NumPy, again, copies and gives the right result.
How PyTorch checks it
The checks are short (pytorchMemoryOverlap.cpp, raxismemory_overlap.cpp). For the output alone:
- If it is non-overlapping and dense, its strides are a permutation of the strides of a contiguous tensor, so it cannot repeat elements: no overlap.
- If a dimension of size greater than 1 has a stride of 0: overlap, the error above.
- Otherwise: “too hard”.
And for the output against each input:
- The same tensor: full overlap, allowed.
- If either of them is not dense: “too hard”.
- If both are dense, each one occupies one block of memory with no holes, from its first byte to its last. Different storages, or blocks that do not touch: no overlap. The same block with the same strides: full. The same block with other strides, or blocks that intersect: partial, the error above.
Only the answers “overlap” and “partial” are errors. “Too hard” lets the operation through, without a check and without a copy. And it is easy to land there, with any slice that skips elements:
>>> x = torch.arange(10.0)
>>> torch.add(x[:-2:2], 0, out=x[2::2]) # x[2::2] = x[0:8:2], a copy shifted by 2
>>> x[2::2]
tensor([0., 0., 0., 0.])
The intended result is [0, 2, 4, 6], and NumPy gives it. In PyTorch, and in Raxis, which has the same check, the loop copies x[0] into x[2], then the new x[2] into x[4], and so on: zeros everywhere, without an error. Neither view is dense, they skip every other element, so the check does not even try.
Why not solve it exactly?
You might wonder why PyTorch does not just check whether the two views have an element in common. It is harder than it looks. A view reaches each of its elements by taking some number of steps along each dimension, each step as long as that dimension’s stride, and never more steps than the dimension’s size. Two views meet if some choice of steps in one lands on the same address as some choice of steps in the other. Written down, that is a Diophantine equation: an equation whose unknowns, here the numbers of steps, must be whole numbers, each one within its limit. Without the limits on the number of steps, a little arithmetic settles it: x[::2] and x[1::2] both move in steps of 2 and start one element apart, so they can never meet. With the limits, it becomes a classic hard problem. A view with two elements in every dimension reaches exactly the sums of some of its strides, so asking whether it reaches an address is asking whether some numbers of a list add up to a given total: the subset sum problem. That problem is NP-complete: no known algorithm solves every case quickly, and the work can grow exponentially with the number of dimensions.
NumPy has the exact solver anyway. np.shares_memory solves it, and its documentation warns that “checking whether two arrays share memory is NP-complete, and runtime may increase exponentially in the number of dimensions”, with a max_work parameter to cap the effort. For its ufuncs, NumPy uses a heuristic and, when it cannot prove that there is no dependency, makes a temporary copy: “may in rare cases result in needless temporary copies”.
PyTorch’s developers weighed exactly this in 2018 (pytorch#8212): an exact check like NumPy’s takes exponential time in the worst case and is hard to write without integer overflows, so they settled on a few cheap checks for the common cases. The year before, an issue about the same problem had been closed as expected behavior, with a note that NumPy had only just fixed it “after a humungous effort” (pytorch#906).
So the two libraries make opposite trade-offs. NumPy always gives the result as if there were no overlap, and pays for it with an analysis and, sometimes, with copies you did not ask for. PyTorch’s check costs a few comparisons per operation, and it never copies behind your back, which matters with tensors of gigabytes and on the GPU. In exchange, it catches the common mistakes, the ones with dense views, gives up on the rest, and leaves them to you. That is what its error message means by “Please clone() the tensor before performing the operation”, and it is the right thing to do with two views that might meet.
10. Back to the loop
After build(), TensorIterator holds everything the loop of the last article needed: the loop shape, with as few dimensions as possible, the inner one first, and for every operand a data pointer and its strides in bytes, all of the common type. The kernel calls cpu_kernel_vec(iter, op, vop), which calls iter.for_each with the 2-D loop, and from there it is the last article: threads, DimCounter, max_2d_step and VectorizedLoop2d. And, at the end, if an output was exchanged for a temporary, cast_outputs copies it into the real one.
Back to the example of the last article, a + b with a of shape (1000, 1000) and b of shape (1000, 1): this article is where its numbers came from. Broadcasting gave (1000, 1000). The common type was float32, with no temporaries. The strides were [4, 4000] for the output and a, and [0, 4] for b. The reordering kept the order, because a wanted it. And the merge failed, because 1000 times 0 is not 4, which is why the loop received 1000 rows of 1000.
build(). The muted steps decide nothing for it; with an out= tensor or a shared input they would.The same iterator serves the GPU, with three differences that the CUDA article covers in its sections 6 and 7: the conversion of types inside the kernel instead of temporaries, the division from the last article back for every element (made cheap with magic numbers), and a split of the iterator in pieces when the offsets do not fit in 32 bits. Reductions use the same machinery too, with outputs that have a stride of 0 along the reduced dimensions, and they come in the article after the next one, together with threads. The next one is about the kernels, and ends by following this same a + b down to the registers.
Key takeaways
- One iterator does everything before the loop (section 1): shape, strides, type, output and order. An operation only writes the code for one element.
- A broadcast dimension is a stride of 0 (section 4), and a Python number does not widen a tensor’s type (section 5).
- On the CPU, mixed types cost one more pass over memory (section 5): inputs of another type become temporaries, so that the loop stays a single typed loop.
- Most operations end up as one flat loop (sections 7 and 8): the smallest strides go inside and dimensions merge. The first operand with an opinion decides the order, so
a + bandb + acan differ by 2x or more. - Overlap is checked cheaply, not exactly (section 9), because the exact question is NP-complete.
Further reading
- How to use TensorIterator, on the PyTorch wiki: the configuration flags from the side of someone writing an operator.
- The TensorIterator episode of Edward Yang’s PyTorch Developer Podcast.
- The type promotion rules, in the documentation of
torch.dtype. - NumPy’s documentation of
shares_memoryand of overlap in ufuncs, the other side of section 9.
If something is not clear, or you think I got something wrong, leave a comment.