Mask Sugar

In Finch, expressions like i == j are treated as a sugar for mask tensors, which can be used to encode fancy iteration patterns. For example, the expression i == j is converted to a diagonal boolean mask tensor DiagMask()[i, j], which allows an expression like

@finch begin
    for i in _, j in _
        if i == j
            s[] += A[i, j]
        end
    end
end

to compile to something like

for i in 1:n
    s[] += A[i, i]
end

There are several mask tensors and syntaxes available, summarized in the following table where i, j are indices:

Expression	Transformed Expression
`i < j`	`UpTriMask()[i, j - 1]`
`i <= j`	`UpTriMask()[i, j]`
`i > j`	`LoTriMask()[i, j + 1]`
`i >= j`	`LoTriMask()[i, j]`
`i == j`	`DiagMask()[i, j]`
`i != j`	`!(DiagMask()[i, j])`

Note that either i or j may be expressions, so long as the expression is constant with respect to the loop over the index.

The mask tensors are described below:

Finch.uptrimask — Constant

uptrimask

A mask for an upper triangular tensor, uptrimask[i, j] = i <= j. Note that this specializes each column for the cases where i <= j and i > j. For an upper triangle with offset k, use uptrimask[i, j - k].

Finch.lotrimask — Constant

lotrimask

A mask for a lower triangular tensor, lotrimask[i, j] = i >= j. Note that this specializes each column for the cases where i < j and i >= j. For a lower triangle with offset k, use lotrimask[i, j - k].

Finch.diagmask — Constant

diagmask

A mask for a diagonal tensor, diagmask[i, j] = i == j. Note that this specializes each column for the cases where i < j, i == j, and i > j. For a diagonal with offset k, use diagmask[i, j - k].

Finch.bandmask — Constant

bandmask

A mask for a banded tensor, bandmask[i, j, k] = j <= i <= k. Note that this specializes each column for the cases where i < j, j <= i <= k, and k < i.

Finch.splitmask — Function

splitmask(n, P)

A mask to evenly divide n indices into P regions. If M = splitmask(P, n), then M[i, j] = fld(n * (j - 1), P) <= i < fld(n * j, P).

julia> splitmask(10, 3)
10×3 Finch.SplitMask{Int64}:
 1  0  0
 1  0  0
 1  0  0
 0  1  0
 0  1  0
 0  1  0
 0  0  1
 0  0  1
 0  0  1
 0  0  1

Finch.chunkmask — Function

chunkmask(n, b)

A mask to evenly divide n indices into regions of size b. If m = chunkmask(b, n), then m[i, j] = b * (j - 1) < i <= b * j. Note that this specializes for the cleanup case at the end of the range.

julia> chunkmask(10, 3)
10×4 Finch.ChunkMask{Int64}:
 1  0  0  0
 1  0  0  0
 1  0  0  0
 0  1  0  0
 0  1  0  0
 0  1  0  0
 0  0  1  0
 0  0  1  0
 0  0  1  0
 0  0  0  1

Finch.pairsummask — Constant

pairsummask

A mask for summing adjacent pairs, pairsummask[i, j] = 2i - 1 <= j <= 2i. Each column contains a single true entry at i = cld(j, 2).

Finch.paircarrymask — Constant

paircarrymask

A mask for carrying partial pair sums, paircarrymask[i, j] = 2j <= i <= 2j + 1. The first row is false. Each column specializes the interval containing its two true entries.

Finch.reversemask — Function

reversemask(n)

A mask for reversing an axis of length n, reversemask(n)[i, j] = j == n - i + 1. Each column specializes its single true entry. The row extent is inferred from other tensors or the loop bounds.

Finch.rollmask — Function

rollmask(n, k=0)

A mask for rolling an axis of length n by k, rollmask(n, k)[i, j] = n > 0 && j == mod(i - k - 1, n) + 1. The row extent is inferred. Each column steps through its true entries with period n, so rectangular uses may contain multiple true entries per column.

Finch.repeatmask — Function

repeatmask(k=0)

A mask for repeating each entry k times, repeatmask(k)[i, j] = k > 0 && j == fld(i - 1, k) + 1. Each column specializes the interval k * (j - 1) < i <= k * j. For k <= 0, all entries are false. Both extents are inferred.

Finch.onehotmask — Function

onehotmask(index)

A vector mask with a single true entry, onehotmask(index)[i] = i == index. The index is one-based and the extent is inferred from other tensors or loop bounds. An index outside that extent produces an all-false mask.

Finch.paritymask — Function

paritymask(parity=0)

A vector mask selecting alternating entries, paritymask(parity)[i] = mod(i - 1, 2) == parity. Parity refers to the zero-based position: 0 selects Julia indices 1, 3, 5, … and 1 selects 2, 4, 6, …. Other values produce an all-false mask. The extent is inferred.

Finch.oddevenmergesortpartnermask — Function

oddevenmergesortpartnermask(n, p, k)

A mask mapping each index to its compare-exchange partner in an odd-even merge sort stage of length n. With zero-based position r = i - 1 and offset = mod(k, p), i is a left endpoint when r + k < n, r >= offset, mod(r - offset, 2k) < k, and fld(r, 2p) == fld(r + k, 2p). Partners exchange i and i + k; unpaired indices map to themselves. Both p and k must be positive. The row extent is inferred.

Finch.oddevenmergesortlowermask — Function

oddevenmergesortlowermask(n, p, k)

A vector mask selecting the left endpoints of the compare-exchanges in oddevenmergesortpartnermask(n, p, k). These endpoints receive the smaller value. Both p and k must be positive.

Finch.reshapemask — Function

reshapemask(old_shape, new_shape)

A mask relating coordinates with equal row-major linear positions in two shapes. The axes are (old_shape..., new_shape...); the last axis of each shape varies fastest, matching the Python pattern. Coordinates are one-based. The shapes must have equal products. Empty tuples represent scalars.

For example, reshapemask((2, 3), (3, 2))[i, j, k, l] is true when 3(i - 1) + j - 1 == 2(k - 1) + l - 1.

Finch.randommask — Function

randommask([rng], shape, p; seed=nothing)

A Boolean mask with reproducible random-looking entries and an approximate true fraction of p. shape is a tuple of nonnegative dimensions, or an integer for a vector. An empty tuple gives a scalar. The probability is stored as Float64 and must lie in [0, 1]; p = 0 and p = 1 give constant masks.

An indexed mask starts with a mixed 64-bit seed, then XORs in each one-based coordinate and mixes again, from the last axis to the first. The high 53 bits of the result are converted to a value in [0, 1) and compared with p. This is a pseudorandom hash construction; it does not promise n-wise independence. Scalar masks convert the seed directly to a value in [0, 1) and compare with p. Each read specializes into separate true and false branches.

Reads consume no randomness and are independent of traversal order. The same seed and coordinates give the same entry even when the shape changes. There is no limit on the product of the dimensions, since coordinates are never flattened. Only the shape, probability, and one seed are stored.

Pass seed as an integer in [0, typemax(UInt64)] to reproduce a mask directly. If omitted, one seed is drawn from rng (the default RNG if omitted).

For example, mask = randommask((100, 200), 0.1; seed=42) creates a matrix mask that can be read as mask[i, j] inside @finch.