Overview¶

Broadcasting refers to the automatic (implicit) expansion of array dimensions to be of equal sizes without copying array data for the purpose of making arrays with different shapes have compatible shapes for element-wise operations.

Broadcasting facilitates user ergonomics by encouraging users to avoid unnecessary copying of array data and canpotentially enable more memory-efficient element-wise operations through vectorization, reduced memory consumption, and cache locality.

Algorithm¶

Given an element-wise operation involving two compatible arrays, an array having a singleton dimension (i.e., a dimension whose size is one) is broadcast (i.e., virtually repeated) across an array having a corresponding non-singleton dimension.

If two arrays are of unequal rank, the array having a lower rank is promoted to a higher rank by (virtually) prepending singleton dimensions until the number of dimensions matches that of the array having a higher rank.

The results of the element-wise operation must be stored in an array having a shape determined by the following algorithm.

1. LetA andB both be arrays.

2. Letshape1 be a tuple describing the shape of arrayA.

3. Letshape2 be a tuple describing the shape of arrayB.

4. LetN1 be the number of dimensions of arrayA (i.e., the result oflen(shape1)).

5. LetN2 be the number of dimensions of arrayB (i.e., the result oflen(shape2)).

6. LetN be the maximum value ofN1 andN2 (i.e., the result ofmax(N1,N2)).

7. Letshape be a temporary list of lengthN for storing the shape of the result array.

8. Leti beN-1.

9. Repeat, whilei>=0

   1. Letn1 beN1-N+i.

   2. Ifn1>=0, letd1 be the size of dimensionn1 for arrayA (i.e., the result ofshape1[n1]); else, letd1 be1.

   3. Letn2 beN2-N+i.

   4. Ifn2>=0, letd2 be the size of dimensionn2 for arrayB (i.e., the result ofshape2[n2]); else, letd2 be1.

   5. Ifd1==1, then set theith element ofshape tod2.

   6. Else, ifd2==1, then

      • set theith element ofshape tod1.

   7. Else, ifd1==d2, then

      • set theith element ofshape tod1.

   8. Else, throw an exception.

   9. Seti toi-1.

10. Lettuple(shape) be the shape of the result array.

A(4darray):8x1x6x1B(3darray):7x1x5---------------------------------Result(4darray):8x7x6x5A(2darray):5x4B(1darray):1-------------------------Result(2darray):5x4A(2darray):5x4B(1darray):4-------------------------Result(2darray):5x4A(3darray):15x3x5B(3darray):15x1x5------------------------------Result(3darray):15x3x5A(3darray):15x3x5B(2darray):3x5------------------------------Result(3darray):15x3x5A(3darray):15x3x5B(2darray):3x1------------------------------Result(3darray):15x3x5

A(1darray):3B(1darray):4# dimension does not matchA(2darray):2x1B(3darray):8x4x3# second dimension does not matchA(3darray):15x3x5B(2darray):15x3# singleton dimensions can only be prepended, not appended

In-place Semantics¶

As implied by the broadcasting algorithm, in-place element-wise operations (including__setitem__) must not change the shape of the in-place array as a result of broadcasting. Such operations should only be supported in the case where the right-hand operand can broadcast to the shape of the left-hand operand, after any indexing operations are performed.

For example:

x=empty((2,3,4))a=empty((1,3,4))# This is OK. The shape of a, (1, 3, 4), can broadcast to the shape of x[...], (2, 3, 4)x[...]=a# This is not allowed. The shape of a, (1, 3, 4), can NOT broadcast to the shape of x[1, ...], (3, 4)x[1,...]=a