Module reduce 

Reductions and scans over a contiguous slice: sums, products, maximums and minimums, and their running versions. Each compiles inside rustymath once for each item type. A float sum or product may combine the items in any order, which lets its loop vectorize, so its last bits can differ from a sum taken item by item. Beside NaN, a float maximum or minimum gives NaN or the greatest or least of the items that aren’t NaN, and never any other number. Which of the two it gives can depend on the target and the loop. An empty slice gives -∞ or ∞. f16 items compute in f32. Their sum or product is an f32 total. An integer sum or product computes at i64, or at u64 for u64 items. Where it doesn’t fit, it wraps, and reports that it doesn’t fit, as the running versions do.

Structs

Alternated

The right fold by the inverse of a reduction: - for Sum, and ÷ for ScaledProduct on floats and Product on complex numbers. x0 - (x1 - (x2 - …)) is the sum of the items at even positions less the sum of those at odd positions, and x0 ÷ (x1 ÷ (x2 ÷ …)) is the quotient of their products. A total holds that sum or quotient for the items folded so far, with whether their number is odd. step takes an item at an odd position away, and merge takes the later run’s total away where the earlier run’s count is odd, each through Inverse. Every fold that takes a Reduction folds it, as along, fold_into, along_mapped and fold_pieces do. Totals stores its folds without the parity.

And

The fold of integers by bitwise &, and of Booleans by and.

Logical

A function of two Booleans, held as its truth table: Logical(t) gives t[r][x] for the running result r and the next item x. Its scans run any such function.

Max

max as a Reduction. Its step on floats is maximum of the item and the total, which a NaN item leaves unchanged. Every fold and scan starts at -∞, and AArch64’s and wasm’s vector folds keep the running result beside a NaN item, as that step does. So a NaN item changes no running result on any target, and a fold of NaN items alone gives -∞.

Maximum

maximum as a function object, which also takes integers and Booleans. The maximum of two Booleans is their or.

Min

min as a Reduction, as Max is max, starting at ∞.

Minimum

minimum as a function object, which also takes integers and Booleans. The minimum of two Booleans is their and.

Or

The fold of integers by bitwise |, and of Booleans by or.

Product

prod as a Reduction.

Scaled

A product of floats held as m × 2^e, a mantissa m and a whole exponent e kept apart, so that the product never leaves the normal floats however many items it takes. A step leaves the mantissa where it is while its magnitude stays inside 2^±511 (2^±63 in f32), half the floats’ exponents, so that the product of two mantissas stays normal, and moves the mantissa’s exponent into e once it leaves. normal says whether every step so far was a nonzero normal float. ScaledProduct folds into it. The exponent sums exactly up to 2^53 in f64 and 2^24 in f32, which a product that ends inside the floats’ range never nears.

ScaledProduct

The product of floats with its exponent kept apart, as Scaled holds it, so that a running product can’t overflow or underflow where the whole product doesn’t. A step fails only where an item, or a step’s product, isn’t a nonzero normal float: on zeros, infinities and NaNs, on subnormals, and on items so large or small that a mantissa times them leaves the normal floats. The exact fold takes those. Alternated folds ÷ on floats by it.

Squares

The sum of the squares of floats’ or complex numbers’ magnitudes as a Reduction, with each square computed and totalled in f64, where an f32’s square neither overflows nor underflows. It folds the items themselves, with no buffer of squares.

Sum

sum as a Reduction.

SumAs

Sums of Terms as a Reduction, in the type C, which the caller picks to hold every sum, so no step checks whether it fits: counts of the trues among Booleans, or sums of integers.

Total

A compiled fold’s total over items items, as its 8-byte slot holds it: a float as an f64’s bits, an integer extended to 64 bits, and a Boolean as 0 or 1.

Xnor

The fold of integers by bitwise XNOR, !(a ^ b), and of Booleans by ==: true where an even number of them are false.

Xor

The fold of integers by bitwise ^, and of Booleans by !=: true where an odd number of them are true.

Enums

Direction

FoldRoute

How a fold reads an array that a mapping lays over storage, as fold_route chooses.

Part

A block of an array that fold_pieces folds, as its producer hands it over: the block’s items, or the reduction’s total of its n items, where the items all lie in one lane along the last axis.

Picks

The folds that picks finds the extremes of: windows of a width that slide along each lane, as sliding folds them, each whole lane, as along folds it, or each lane’s running folds, as scan_along gives them.

Piece

Reduce

A reduction by name: the tag by which a function object’s row names the reduction it folds by (facts::Facts::fold, facts::Facts::truth), and by which a frontend’s block stages and compiled code fold. with_reduce! gives its type.

Seed

Constants

DIRECT

The widest window that sliding folds directly, with one pass over each block of a lane for each of the window’s rows. Wider windows take van Herk-Gil-Werman.

RUN

The shortest run of consecutive items that along_mapped folds where it lies. Each run costs its own call into the fold, so shorter runs fold faster copied a piece at a time. On one thread, folding runs of 128 floats in place took 9% less time than copying them, and runs of 64 took 15% more.

Traits

Inverse

A reduction whose step can be undone, as Alternated folds by it: Sum subtracts, and ScaledProduct and Product divide. An integer difference fits only within i64, a complex quotient only inside the normal range, and a float quotient only where no item, or product of the running mantissa and an item, leaves the normal floats. An alternated fold can then fail where the right fold taken item by item, or its exact result, would fit.

Reduction

A reduction by Sum, Product, ScaledProduct, Max, Min, And, Or, Xor, Xnor, SumAs, Squares or Alternated, implemented inside rustymath once for each item type it takes. slice folds a whole slice of consecutive items, in any order, merge combines the folds of two neighbouring runs, and scan gives the running folds. along, fold_into and scan_along fold along an axis whose items aren’t consecutive. Sum and Product take floats, integers and complex numbers. Max and Min take floats, integers and Booleans, And, Or and Xor take integers and Booleans, Xnor takes signed integers, bytes and Booleans, SumAs takes Booleans and integers, Squares takes floats and complex numbers, ScaledProduct takes floats, Alternated<Sum> takes floats, integers and complex numbers, Alternated<ScaledProduct> takes floats, and Alternated<Product> takes complex numbers. An f16 reduction computes in f32. A sum or product of f16s gives an f32 total, for its caller to round once. A total that doesn’t fit its type fails, with its value wrapped to that type.

Tally

An integer type that sums Terms, wrapping where a sum doesn’t fit: u8, i16, i32 or i64. A caller picks one that holds every sum it needs. A count of fewer than 256 Booleans fits a byte, which takes an eighth of the memory of an i64.

Term

An item that sums into any Tally: a Boolean, as 0 or 1, or an integer.

Totals

A fold’s total as an item of a buffer: an Element stores itself, a Scaled product stores its value, and Alternated’s total stores its fold without the parity of its count.

Functions

adjacent_read^⚠

Each item of input, an array of shape dims, combined with the item one row before it along the middle axis, and each lane’s first row with seed’s item in its column, or kept as it is without a seed, as an inverse scan runs it. block combines the items of two equal slices, the earlier items first unless flip, and gives the kind of any combination that failed: a formula’s loop over a block. A failure is an error where the read is checked.

along

The folds by R of the lanes along the middle axis of data, an array of shape [outer, len, inner] held row by row: one fold for each of the outer × inner lanes, and whether every one fits. Where a lane along the last axis, or a group of inner lanes along another axis, fits in one piece of fold_pieces, each lane folds whole. Runs of whole lanes or groups then split across threads as parallel::split splits a call. An array with too few rows to give each of this thread’s parallel::threads a piece of [ROWS] rows splits by columns instead, where a row holds more than one unit: a run of lanes whose part of the array holds at least [PIECE] items. Each thread then reads part of every row. At 4 threads on an M5 Max, +⌿ took 41% less time on 8×524288, which had folded on one thread, and 17% less on 64×65536 than split by rows. With more rows, a split by columns took more time than a split by rows: 33% more on 256×16384 and 66% more on 4000×9000. Otherwise the array folds as fold_pieces folds it.

along_mapped

Folds each lane of the array described by mapping without gathering it. Returns totals, whether every integer total fits, and an optional mapping from those totals to result order.

boolean_scan_read

A Boolean-result scan with its raw seed and chunk carries read at the input’s numeric type.

bounded_scan

A sum scan of integers or Booleans, or with negate a left scan by - of them, whose caller asks for totals in output’s dtype, i16 or i32, wide enough for every stored item that the scan reads, whatever width the kernel computes at. The caller asks only where its bound on every running total fits that type. Each lane totals in it through SumAs, wrapping. None for any other request.

comparison_scan

Appends a Boolean-valued scan of long consecutive lanes, keeping an unseeded lane’s first item as it is. Comparisons at carries 0 and 1 make independent two-state maps, whose packed words compose through mapped. A failed speculative comparison leaves out unchanged and declines, so the ordered runner checks only steps the scan actually takes.

extremes

The least and the greatest item of x, in one pass of comparisons and selects. For floats, min and max take less time together, because their folds run AArch64’s fmin and fmax.

fold_into

Folds block, the items from position start on of an array of shape [outer, len, inner] held row by row, into totals, the folds by R of the array’s lanes along its middle axis so far, which start at R::unit(). Gives whether every fold still fits. Along the last axis, a lane’s items are consecutive. Whole lanes fold as fold_rows folds them, and the pieces of a lane that a block boundary splits fold by slice and join by merge. Along any other axis, runs of whole rows fold as [step_rows] folds them, and a row that a block boundary splits steps item by item.

fold_pieces

Folds an array of shape [outer, len, inner] by R into totals, the folds of its lanes along the middle axis, and gives whether every fold fits. run(range, fold) produces the array’s items in range in order, and hands each block of them to fold with the position of its first item, as a Part: the items, or their total. The array folds in one piece for each of this thread’s parallel::threads, each of at least [piece_size] items. On one thread it folds as one piece. A lane that one piece holds folds as fold_into folds it, and a block’s total joins it as [fold_total] joins it. A lane that crosses pieces folds its part in each piece, and those folds merge.

fold_route

The route of a fold along axes, one axis or two, of the array of shape that mapping lays over storage. It slides where source gives the shape of what the mapping reads and the array is windows along axes. Otherwise it reads through the mapping, unless the array keeps the items it gathers (keeps) and rereads_cheaply is false, where it folds the kept items. A fold of every item takes no axes, never slides, and folds a block of storage from the array’s items (ArrayView::fold_items reads it in place). Python’s folds of views and basedpl’s folds of pending copies both choose here.

lanes_scan

Appends the running results along each lane of len consecutive items in data to out, and gives whether every one fits: first gives each lane’s first result, and step each later one from the one before. Lanes shorter than [SHORT_LANE] run [LANES] side by side (rows_scan).

max

The greatest item of x.

maximum

The greater of x and y, as max gives the greatest item. Beside NaN, or where they’re equal, it gives y. A fold that passes its running result as y keeps it beside a NaN item. NumPy calls it maximum.

min

The least item of x.

minimum

The lesser of x and y, as maximum gives the greater. NumPy calls it minimum.

negated_scan

A left scan by -, run as +’s scan (scan_along) of negated items (negated_cells). Floats and complex numbers, 16-bit floats in 32 bits as the ordered scan computes them, and integers and Booleans whose caller asks for totals in i16 or i32 (bounded_scan). Ok(false), with output unchanged, for other dtypes.

ordered_scan^⚠

Appends the ordered left scan of each lane of [outer, len, inner] in data to out, in the same layout: along the last axis by lane, one call for every lane, stepping from seed’s item; along any other axis by block, one call for each row, stepping the row before it, or seed’s row, by the row’s items. Without a seed, a lane’s first item or row is kept as it is. Gives the kind of the first step that failed.

picks

The row of the first item that gives each fold by R along the middle axis of data, an array of shape [outer, len, inner], for a reduction that picks one of its items, as Max and Min do. of chooses the folds, and the result lays out as their results do. Each row counts from the start of its lane. A fold whose items all leave it at R::unit(), as NaN items do for a float maximum, gives its first row.

prod

The product of x, 1 for an empty slice, and whether it fits. An integer product that doesn’t fit wraps.

rereads_cheaply

Whether along_mapped reads the array of shape that mapping lays over storage where it lies, with no copy: a block of storage, as Mapping::block finds, or runs of at least RUN items. Elsewhere each read copies the array’s items a piece at a time, at about a gather’s cost, so a caller that will read the array again keeps a compact copy instead, as basedpl does for a pending copy that a name holds and the Python API does for a view that keeps what it gathers.

reverse_rows

running

How many independent running values a loop keeps, each of size bytes: a fold’s partial results, or a block of items under Horner’s rule. 32 measured faster on the Mac than 8 or 16 for items of up to 8 bytes. A 16-byte item, such as a Complex<f64>, keeps 16, because 32 fill every vector register, and a complex sum then took 1.7 times as long. In wasm, LLVM leaves 32 values of 8 bytes, or 16 of 16 bytes, in linear memory, where each step loads and stores them. It keeps half as many in locals.

scan_along

Appends the running folds by R along the middle axis of data, an array of shape [outer, len, inner] held row by row, to out, in the same layout. Where seed is given, each lane’s first fold combines seed’s item for its column, or its only item. Gives whether every fold fits. Lanes of consecutive items scan by Reduction::short_lanes where the reduction takes them, else by scan. Along any other axis, each row’s folds step the row before’s by checked.

scan_read

seed_row

Cell cell’s inner seed items from read: its one item in every column where it holds one, else the cell’s own row.

sliding

The folds by R of each window of width neighbouring rows along the middle axis of data, an array of shape [outer, len, inner] held row by row. The result has shape [outer, len - width + 1, inner], with whether every fold fits. Each fold combines its window’s items in order, except that a window as long as a lane of single items folds as along folds the lane. A window of at most DIRECT rows folds directly. A wider one takes van Herk-Gil-Werman’s method: each lane splits into blocks of width rows, and each window is the fold of one block’s suffix and the next block’s prefix, so an item costs the same whatever the width.

sliding_2d

The folds by R of each window of w1 rows along axis 1 and w2 rows along axis 3 of data, an array of shape [outer, len1, mid, len2, inner] held row by row. Windows start every e1 positions along axis 1 and every e2 along axis 3: every position for windows that slide, or every window’s width for windows that tile the axis, as pooling’s do. The result has shape [outer, c1, mid, c2, inner], where c1 and c2 count the windows along each axis, with whether every fold fits. Each band of w1 rows folds into a buffer that stays in cache, and the windows along axis 3 fold from that buffer, so data is read once. A window’s items fold along axis 1 and then along axis 3, which suits reductions that fold in any order. None for a window wider than DIRECT rows.

sum

The sum of x, 0 for an empty slice, and whether it fits. An integer sum that doesn’t fit wraps.

view_picks

picks of the items of x at their own type, by Max, or by Min where max is false. None for complex numbers and characters, which have no order.

Type Aliases

Pieces