How PyTorch prepares the loop of every operation

pgmesa · · 40 min read

On this page

  1. 1. Hundreds of operations, one iterator
  2. 2. The operands, and which ones are written
  3. 3. The shape: broadcasting
  4. 4. The strides: a broadcast dimension is a stride of 0
  5. 5. The type: promotion, and what it costs on the CPU
    1. What it costs
  6. 6. When the output already exists: out=
  7. 7. The order: which dimension goes inside
    1. The output takes the layout of the inputs
    2. When the operands disagree
    3. a + b is not b + a
  8. 8. Merging dimensions
    1. Why it matters
    2. A shortcut for the common case
  9. 9. When the output shares memory with an input
    1. The case that is fine: in place
    2. An input that is broadcast cannot be the output
    3. An output that repeats elements
    4. An output that overlaps an input, shifted
    5. How PyTorch checks it
    6. Why not solve it exactly?
  10. 10. Back to the loop
  11. Key takeaways
  12. Further reading
Rebuilding PyTorch · 4 of 8
Part of Rebuilding PyTorch (4 of 8)
  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

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:

  1. Hundreds of operations, one iterator.
  2. The operands, and which ones are written.
  3. The shape: broadcasting.
  4. The strides: a broadcast dimension is a stride of 0.
  5. The type: promotion, and what it costs on the CPU.
  6. When the output already exists: out=.
  7. The order: which dimension goes inside.
  8. Merging dimensions.
  9. When the output shares memory with an input.
  10. 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:

This is what it looks like with b of shape (3, 1) and c of shape (4,):

Broadcasting (3, 1) with (4,)The shapes (3, 1) and (4,) are aligned on the right, so (4,) is read as (1, 4), and the result has shape (3, 4). The column of b is repeated along the columns and the row of c along the rows; the repeated cells are not in memory.1. Align on the right, pad with 1s on the leftb (3, 1)c (4,) read as (1, 4)b + c (3, 4)2. Stretch every size 1Dashed cells are not in memory: theloop reads the same number again,with a stride of 0.b, (3, 1)00001010101020202020+c, (4,)012301230123=b + c, (3, 4)012310111213202122233 numbers in memory4 numbers in memory12 numbers, a new tensor
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).

OperandShapeStrides (elements)Strides after broadcasting (bytes)
out(3, 4)not allocated yetnot 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:

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:

OperationResultWhy
float32 tensor + float64 tensorfloat64Two tensors with dimensions: the table
float32 tensor + float64 0-d tensorfloat32Same category, the tensor with dimensions decides
int32 tensor + int64 0-d tensorint32The same
int32 tensor + float64 0-d tensorfloat64The 0-d tensor has a higher category
int32 tensor + 2.5float32Higher category, and a Python float counts as float32
uint8 tensor + 300uint8, and 1 + 300 gives 45Same 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 outputNumPyPyTorchRaxis
float64 + float640.143 ms0.145 ms0.145 ms
float32 + float640.336 ms0.360 ms0.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 inputsNumPyPyTorchRaxis
into a float32 output0.076 ms0.074 ms0.076 ms
into a float64 output0.267 ms0.274 ms0.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.

The order in which the loop reads memoryEach 4 x 4 grid is a tensor in its logical order, and each cell holds its position in memory. A transpose walked row by row reads positions 0, 4, 8, 12; walked column by column it reads 0, 1, 2, 3. With a + c.t(), walking the rows of a reads c.t() with jumps, and walking its columns would do the same to a.1. a.t() + c.t(): both are transposesEach cell holds its position in memory. reorder_dimensions turns the walk around.->2. a + c.t(): the operands disagreeBoth are walked in the same order, so one of them always jumps.+c.t(), walked row by row0481215913261014371115reads 0, 4, 8, 12, 1, 5, ...jumps 4 elements per readc.t(), walked column by column0481215913261014371115reads 0, 1, 2, 3, 4, 5, ...contiguous, vector loadsa, walked row by row0123456789101112131415reads 0, 1, 2, 3, 4, 5, ...contiguous, vector loadsc.t(), walked row by row0481215913261014371115reads 0, 4, 8, 12, 1, 5, ...jumps 4 elements per read
The loop over a 4 x 4 tensor, drawn over its logical grid: each cell holds its position in memory, the arrows follow the reads, and the dashed lines are the jumps to the next row or column. With 1000 x 1000 tensors the jump is 1000 elements, 4000 bytes.

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:

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:

NumPyPyTorchRaxis
a + c0.070 ms0.074 ms0.076 ms
a.t() + c.t(), into out.t()0.073 ms0.075 ms0.080 ms
a + c.t(), into out0.475 ms0.427 ms0.410 ms
a + c, into out.t()0.472 ms0.761 ms0.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 + aNumPyPyTorchRaxis
300 x 300 x 300, a + b36.8 ms20.7 ms20.5 ms
300 x 300 x 300, b + a37.2 ms14.7 ms12.8 ms
256 x 256 x 256, a + b68.2 ms51.4 ms53.3 ms
256 x 256 x 256, b + a67.9 ms26.5 ms27.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:

a + b and b + a walking memory through a small cacheAn animation of a scaled model. Both orders add the same two 4 x 4 x 4 tensors through a cache of six lines. In a + b each line of b is evicted before most of its values are used, so it is loaded four times; in b + a every line is loaded once, and the addition finishes in half the time.being addedline arriving from memoryin the cache, not used yetalready addedScaled model: each row is one cache line of 4 floats, the cache holds 6 lines, a load costs 4 ticks.a + b, the order of afor i: for j: for k: out[i,j,k] = a[i,j,k] + b[i,j,k]a: planes i, rows j, columns ki = 0i = 1i = 2i = 3b: planes j, rows k, columns ij = 0j = 1j = 2j = 380 line loads (48 again), 384 ticksA line of b holds 4 values of i, the outer loop: it is gone before they are used.b + a, the order of bfor j: for k: for i: out[i,j,k] = b[i,j,k] + a[i,j,k]a: planes i, rows j, columns ki = 0i = 1i = 2i = 3b: planes j, rows k, columns ij = 0j = 1j = 2j = 332 line loads (0 again), 192 ticksA line of a holds 4 values of k, the middle loop: it comes back after 4 reads.
The same addition in both orders, as a loop. Each tensor is drawn in memory order, plane after plane, and each row is one cache line. When a load brings a line, the values next to the one being added come with it (light blue); b + a uses them before they leave, a + b does not, and has to load the same lines of b again.
How soon a cache line is used againWith 300 x 300 x 300 floats, a + b reads b with a jump of 300 floats and needs each of its cache lines again after 90,000 reads, 5.8 MB of other lines, more than the L2 holds. b + a reads a with a jump of 90,000 floats, but needs each line again after only 300 reads, 19 KB, which stays in L1.The longer jump wins: what matters is how soon a line is needed againa + b, the order of afor i0: a line of b holds 16 values of i0 for i1: for i2: b jumps 300 floatsThe line of b is needed again at the next i0, after 300 x 300 reads.b + a, the order of bfor i1: for i2: a line of a holds 16 values of i2 for i0: a jumps 90,000 floatsThe line of a is needed again at the next i2, after 300 reads.Lines read before the line is needed againL1 48 KBL2 1 MBL3 32 MBa + b5.8 MB: only L3b + a19 KB: fits in L11 KB16 KB256 KB4 MB64 MB
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 + bLoop shapeoutab
(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:

bLoop shapeout and ab
(100, 1, 100)[100, 100, 100][4, 400, 40000][4, 0, 400]
(1, 100, 100)[10000, 100][4, 40000][4, 0]

Row by row:

When two dimensions mergeTwo rows of x in memory, with the elements of x[:, ::2] filled. With 10 columns every jump is 2 elements, also from one row to the next, so the two dimensions are one. With 5 columns the jump between rows is 1 and inside a row it is 2, so they stay two dimensions.Can the rows be walked as one long row?Memory of x, row 0 then row 1. Filled cells are the elements of the view.x with 10 columns: x[:, ::2] has rows of 5012345678910111213141516171819+2inside a row every jump is +2; between rows it is +2rows of 5, stride 2: 5 x 2 == 10, the row stride: mergedx with 5 columns: x[:, ::2] has rows of 30123456789+1inside a row every jump is +2; between rows it is +1rows of 3, stride 2: 3 x 2 = 6 != 5, the row stride: two dimensions
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 elementsNumPyPyTorchRaxis
(1000, 1000) + (1000, 1): rows of 10000.095 ms0.062 ms0.054 ms
(250000, 4) + (250000, 1): rows of 40.978 ms1.913 ms0.977 ms
(250000, 4) + (1, 1): merged into one row0.050 ms0.055 ms0.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:

And for the output against each input:

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.

A loop going forward over overlapping viewsx[1:].add_(x[:-1]) on 0 to 5, step by step: from the second step on, each element reads a value that the loop has already overwritten, and the result is a running sum instead of 0, 1, 3, 5, 7, 9. Below, copying x[0:8:2] into x[2::2] propagates the first zero to every even position.1. x[1:].add_(x[:-1]): partial overlap, PyTorch refuses itx[i] = x[i] + x[i - 1], going forward. Marked: a value read after it was overwritten.x012345x[1] += x[0]012345x[2] += x[1]013345x[3] += x[2]013645x[4] += x[3]0136105x[5] += x[4]01361015got 0, 1, 3, 6, 10, 15wanted 0, 1, 3, 5, 7, 92. torch.add(x[:-2:2], 0, out=x[2::2]): "too hard", no checkx[i + 2] = x[i] for every other i. The first 0 travels to every even position.x0123456789x[2] = x[0]0103456789x[4] = x[2]0103056789x[6] = x[4]0103050789x[8] = x[6]0103050709got x[2::2] = 0, 0, 0, 0wanted 0, 2, 4, 6
A loop going forward when the output overlaps an input, shifted. Filled: the element written in each step. Marked: an element read after the loop overwrote it. PyTorch refuses the first case, and lets the second through because neither view is dense; NumPy copies the input and gives the intended result in both.

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.

The steps of build() for a + bFor a of shape (1000, 1000) plus b of shape (1000, 1), float32, with a new output: the shape is (1000, 1000), the type float32 with no temporaries, the strides in bytes [4, 4000] for out and a and [0, 4] for b, the order is kept, the output is contiguous, and the merge fails, so the loop gets 1000 rows of 1000.build() for a (1000, 1000) + b (1000, 1), float32Strides in brackets are in the loop's order, the inner dimension first.populate_operandsout (not allocated yet), a, bcompute_mem_overlapsout is new: nothing to checkcompute_shape(1000, 1000) and (1000, 1) -> (1000, 1000)mark_resize_outputsout is new: nothing to resizecompute_typesfloat32 and float32 -> float32, no temporariesfast_setupb has another shape: no shortcutcompute_stridesbytes, logical order: a (4000, 4), b (4, 0)reorder_dimensionsa wants its rows inside, kept: a [4, 4000], b [0, 4]allocate_outputsout contiguous: [4, 4000], like acoalesce_dimensionsb: 1000 x 0 != 4, so the two dimensions staythe loop1000 rows of 1000: a row of a, and b is one number per row
The example of the article through every step of 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

Further reading

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