# The cases that `tests/speed.rs` times in the native build and `tests/wasm-speed.mjs` times in the browser build. Each case line holds the code, its native budget and its wasm budget, separated by tabs. Each section starts with its name in brackets and the prefs its session starts with. Every session then runs the lines under the `[setup]` before its section.
# Budgets in `[copies]`, `[exact]`, `[images]`, `[objectives]`, `[calls]`, `[derivatives]` and `[structure]` count copies of the `n` items that the section's setup makes. A budget in `[widths]` is the most that the time in that section's 32-bit session may be, as a fraction of the time in the `[exact]` session. Natively and in wasm, it is the worse of that fraction on a Mac and on CI's runner, plus 0.25.
# A wasm budget in copies is twice the most the case has cost on a Mac and on CI's runner, in the module that `cargo wasm` builds, and at least 0.5. `tests/speed.rs` gives the same rule for native budgets in copies.
# A case in copies that CI hasn't timed yet has four times its Mac cost, natively and in wasm. A `[widths]` case that CI hasn't timed yet has its Mac fraction plus 0.25. The next CI run that logs every cost, a push's `Test` run or a `Speed` run, sets their budgets under the rules above.
# The CI figures come from the `Test` and `Speed` runs that last set each budget. Every one ran on the AMD Ryzen 9 7950X3D 16-Core Processor.
[setup]
side←256 ⋄ n←side×side ⋄ v←¿n⍴0 ⋄ w←¿n⍴0 ⋄ s←v-0.5 ⋄ m←[side side]⍴v
jv←¿n⍴1000ₓ ⋄ kv←¿n⍴1000000000000ₓ ⋄ b←0=¿n⍴3ₓ ⋄ i←¿n⍴⌊n ⋄ cnt←¿n⍴3ₓ
c←n⍴"the quick brown fox jumps over the lazy dog"
nd←•distribution "normal" ⋄ coeffs←0.5 ¯1.25 0.75 2 ¯0.125 0.0625 ¯1.5 0.25
ms←[n÷64 8 8]⍴v ⋄ ss←ms+0 2 1⍉ms ⋄ sps←ss+⍤2(16×=⊗⍨⍳8) ⋄ t←[n÷16 16]⍴v ⋄ tq←¿[n÷4 24]⍴0
z←v+0j1×w ⋄ zm←128 128↑m+0j1×⊖m ⋄ f←"svd"•decompose m ⋄ h←"eigen"•decompose m+⍉m ⋄ bm←[side side]⍴b ⋄ jm←[side side]⍴jv ⋄ cm←[side side]⍴c
[copies]
# Sharing storage copies nothing.
,m	0.5	0.5
(⍴m)⍴v	0.5	0.5
# Reading each item once, with almost nothing to write.
+/v	1.1	2
+/jv	0.5	0.68
+/z	2.4	2.4
-/v	1.3	1.6
-/jv	0.5	0.69
⌈/v	1.1	2.8
∧/b	0.5	0.5
+/m	1.4	2.3
+⌿m	1.5	2.1
# A cheap ordered right fold keeps each consecutive lane's running value in a local.
|/jv	20	15
# Reading one argument and writing each item once.
-v	2.2	2.3
-jv	0.71	1.2
~b	0.5	0.5
∧\b	0.5	0.5
∨\b	0.5	0.5
⌽v	2.2	3.1
1⌽v	2.3	2.1
⊖m	2.2	2.7
1↓v	2.4	2.2
(n÷2)↑v	1.2	1.3
n⍴0	1.3	2.1
# Reading two arguments and writing each item once.
v+w	3.2	3.3
jv+jv	0.95	1.2
kv+kv	3.5	4.1
v×2	2.3	2.2
jv×2	1.8	2.2
jv=jv	0.54	1.1
b×jv	0.72	0.81
b×kv	2.6	3.5
v⌊w	3.3	3.4
b∧b	0.5	0.5
c=c	0.86	1.9
(⍳√n)×⊗⍳√n	2.3	2.9
# Products of 64-bit integers that leave 64 bits become exact big integers, each held in an allocation of its own.
kv×kv	1700	1700
# Compressing by a mask can't be vectorised, because each kept item's place depends on the items before it.
b#v	6.2	7.6
⍸b	2.9	4.3
# Replicating by counts of 0 to 2 writes four copies of each item where its run starts. The next item overwrites the copies past its count.
cnt#v	17	18
# Counts held as floats are checked for whole numbers 256 at a time before they replicate.
(•float cnt)#v	30	33
# A range with an approximate length converts each position from an integer to a float. Wasm has no vector instruction for that, so there each block of 8 positions adds 0 to 7 to the block's first float.
⍳n	2.3	2.4
# Comparing within tolerance takes a subtraction, the magnitudes, a scale and a comparison for each item. Tolerant floor raises each item by its scaled magnitude, capped below a half, before it floors.
⌊v	5.4	5.9
v<w	5	6.3
jv<500	0.5	1.1
# Writing twice as many items, or writing in a different order from reading.
v,w	4.2	3.3
⍉m	5.5	6.8
# Windows copy each item once for every window that holds it. Padded windows first copy the argument with its padding.
3↕v	10	14
3 3↕m	43	39
¯3 ¯3↕m	47	42
# A small-table index finds the items' range in one vectorised pass, then writes each item's first position into the table, one item at a time.
≠jv	1.4	1.4
# A search also looks each item of the other argument up in the table, and unique then compresses by the mask.
jv⍳jv	12	9.7
jv∊jv	13	12
c⍳c	12	14
∪jv	2.9	4.2
∪c	5.4	9.4
# Key classifies the keys, then counts and places each group's positions. With `(≢⊢)` it only counts the classes.
{≢⍵}⌸b	5.6	5.2
(≢⊢)⌸b	0.63	0.73
# `(+/⊢)` folds each group of the values in one pass. The keys `i` make about 41,000 groups, each of which the general path would call the operand for.
i (+/⊢)⌸ v	370	430
# Classify of Booleans compares each item with the first. Groups of Booleans write each class's positions 8 items at a time, from a table indexed by the byte of those items' classes.
⍷b	5.3	4.8
=b	0.54	0.66
# Interval index sorts its boundaries, then reads each value's count of boundaries at or below it from a table over their keys.
# Floats' keys span too much for a table, so sixteen values binary-search the sorted floats together.
(<jv)⍸jv	22	23
(<w)⍸v	420	380
# Each item waits for the result before it. In float scans by `+` and `⌈`, only one item in each group of four waits for the group before it.
+\v	3.6	3.2
⌈\v	2.9	5.3
+\jv	4.2	4.7
+\b	3.2	3.2
≠\b	1.9	2.2
-\v	5.7	5.4
-\jv	5.1	5.5
⌈\jv	1.4	1.4
+\z	4.3	4.7
# After a lane's first result, a comparison scan's totals are 0 or 1. The kernel computes each item's result at both, and rustymath picks between them 64 at a time.
<\v	7.5	13
=⍀m	8.5	14
≠\jv	3.6	5.4
0=\jv	3	4.7
# Scans along short lanes make no call for each lane. Comparison and Boolean scans restart lanes inside each 64-bit word of results. Other scans fold lanes under 16 items one item at a time.
=\[32768 2]⍴jv	17	20
<\[16384 4]⍴v	19	29
≠\[16384 4]⍴b	2.1	3.1
+\[16384 4]⍴v	5.5	5.6
# A residue scan waits on the result before each item. From a whole float seed on integers it runs as integers.
7|\jv	57	72
# An inverse scan by `+`, `-`, `=` or `≠` combines each item with the item before it, in one pass.
+\⁻¹v	2.4	3.2
≠\⁻¹b	0.5	0.55
# Each item waits for a read from a random place.
[i]⌷v	12	12
# An indexed assignment copies the array once, then writes each value at its index.
{x←v ⋄ x.[i]←w ⋄ x}0	17	17
# A modified assignment with repeated indices applies its function to each index's values in turn, one round of distinct indices at a time.
{x←v ⋄ x.[i]+←w ⋄ x}0	82	82
# Few distinct indices make a table with a column for each, which a scan down the columns reduces.
{h←10⍴0 ⋄ h.[10|jv]+←1 ⋄ h}0	92	94
# An approximate divisor reads the integers as floats. Each item then needs a float division and a floor within tolerance.
3|jv	5.6	12
# rustymath's `exp` evaluates a polynomial of 10 terms for each item, and `ln` one of 7 terms and a division.
*s	15	28
⍟v	23	41
# rustymath's sine and cosine reduce each item by π in three fused multiply-adds, and evaluate a polynomial of 7 terms. Tangent reduces by π/2, evaluates a polynomial of 9 terms at half the angle, and divides once.
1○v	15	32
2○v	16	33
3○v	21	46
# The hyperbolic functions build on rustymath's `exp` and `expm1`, with a division. The inverse circle functions evaluate a polynomial of 10 or 12 terms after a reduction with a square root or a division.
5○v	25	50
6○v	17	33
7○v	24	46
1○⁻¹v	17	34
2○⁻¹v	19	37
3○⁻¹v	17	38
# The inverse hyperbolic functions build on rustymath's `log1p`, after a square root or a division.
5○⁻¹v	28	52
4○v	7.4	9.1
# Monadic `○`, cis, runs rustymath's `Cis` on the reals at their own width: through vForce's `vvcosisin` on macOS, and through the slice forms of `Cos` and `Sin` elsewhere.
○v	38	93
# An exponent of 2 squares each item, in a loop of its own. Another exponent calls rustymath's `pow` for each item, which at f64 reads tables that NEON and wasm can't vectorize.
v*2	2.3	2.2
v*w	50	74
# Bases 2 and 10 and degrees 2 and 3 have loops of their own.
2⍟v	24	43
10⍟v	24	40
3√v	20	50
# Exact integers read as floats for a function whose results are always approximate.
⍟jv	25	48
*jv	16	35
jv⍟2ₓ	28	50
√jv	8.3	13
# `!` calls rustymath's `gamma`, which sums its Lanczos series in double words. A distribution's density, cdf and quantile each run over the array as one slice. The quantile's `erfcinv` sorts each block of items by region, then evaluates each region's rational approximation over its items, with no iteration. `⌻` evaluates a polynomial of degree 7 by Horner's rule.
!v	330	650
nd.density v	22	42
nd.cdf v	32	57
nd.quantile v	81	150
coeffs⌻v	8.4	15
# Each item goes into a hash table, and each item of the other argument is looked up in it. A tolerant search looks in two buckets for each item, where an exact search looks in one.
v⍳w	240	320
# A radix sort moves every item once for each byte that differs between the keys. Keys that span a small range, as `jv`'s and `b`'s do, take a counting sort, which places each item once.
⍋v	170	160
⍋jv	18	15
⍋b	5.3	5.5
# A sort of keys that span a small range counts them, then writes each key as many times as it occurs. It needs no positions.
<jv	7.9	7.3
<b	0.88	0.79
# Taking a few items of a grade or a sort selects them, without sorting the rest.
(10↑)∘⍋ v	79	180
(10↑)∘< v	78	180
↑∘< v	51	55
# The ranks `⍋⍋` invert the first grade instead of grading it again.
⍋⍋ v	290	320
# Unique sorts the reals, then compares each with the next one.
∪v	250	250
# The inner products in `rustymath` run `+.×`, `⌈.+` and `⌊.+` on floats and integers, `+.×` on complex numbers, Boolean `∨.∧` and `∧.∨`, and the counts `+.=` and `+.≠`. `rustymath`'s own speed test times those products. Each case here checks that basedpl sends one kind of pair to them. A pair that misses them takes the bounded generic path, several times slower. A case with `⍤2` makes one call for each of 1024 matrices of 8×8.
+.×⍤2⍨ ms	36	48
m+.×m	140	320
m⌈.+m	300	840
bm∨.∧bm	12	22
bm∧.∨bm	12	24
jm+.×jm	160	370
jm+.=jm	94	110
cm+.=⍉cm	99	120
zm+.×zm	78	180
# Matrix division, `•decompose`, `•decompose⁻¹` and the determinant `-.×` run on rustymath, whose own speed test times each factorisation. These cases time basedpl's part: the calls in a `⍤2` stack, each path of `⌹`, the route from monadic `-.×` to LU, turning `"qr"`'s factors into arrays, rebuilding a matrix from factors, and reading complex storage. `tq` is tall enough for `⌹` and `"qr"` to take the CholeskyQR2 path.
⌹⍤2 ms	130	160
ms⌹⍤2 sps	150	200
⌹m	280	430
(side↑w)⌹m	110	160
((n÷16)↑w)⌹t	87	110
⌹t	150	240
((n÷4)↑w)⌹tq	580	700
"qr"•decompose tq	580	800
"qr"•decompose⍤2 ms	510	480
"qr"•decompose m	410	630
"cholesky"•decompose⍤2 sps	87	110
"svd"•decompose⍤2 ms	1400	1200
"svd"•decompose⁻¹ f	160	330
["kind":"svd" "rank":8]•decompose m	130	230
"eigen"•decompose⁻¹ h	1400	1800
"eigen"•decompose⍤2 ss	750	720
"eigen"•decompose⍤2 ms	2300	2100
⌹zm	180	260
-.×m	100	150
-.×⍤2 ms	60	82
[exact] •prefs ["tolerance":0]
# Plain IEEE comparisons and `floor`, with nothing to scale by a tolerance.
⌊v	3	4
v<w	2.6	4.1
v=w	2.7	3.9
3|v	6	8.1
# Each real indexes its `order_key` in a hash map, as exact data does.
v⍳w	120	160
∪v	93	98
[widths] •prefs ["float":32]
# Half the bytes to read and write, and twice the lanes in each SIMD instruction.
-v	0.78	0.79
v+w	0.75	0.76
v×2	0.78	0.8
v<w	0.81	0.84
0.5<v	0.89	0.84
√v	0.78	0.75
+⌿m	0.97	0.88
+/v	0.8	0.82
⌈/v	0.82	0.83
+\v	0.98	0.94
m+.×m	0.82	0.78
# `⌊` reads half the bytes and writes 32-bit integers in place of 64-bit ones.
⌊v	0.85	0.92
# An LU decomposition in 32 bits.
⌹m	0.94	0.9
# rustymath's `exp` and `ln` run shorter polynomials at f32, with twice the lanes in each SIMD instruction.
*s	0.65	0.59
⍟v	0.69	0.64
# rustymath's sine and cosine reduce in f32 with fused multiply-adds, and run a polynomial of 4 terms in place of 7.
1○v	0.7	0.95
2○v	0.71	0.93
3○v	0.66	0.84
7○v	0.68	0.61
1○⁻¹v	0.6	0.53
3○⁻¹v	0.63	0.53
v*2	0.79	0.8
v*w	0.83	0.9
# Grade sorts keys and positions of half the bytes.
⍋v	0.91	0.84
# A hash lookup costs about the same at either width. These budgets catch a 32-bit search that costs much more than a 64-bit one.
v⍳w	1.26	1.18
∪v	1.28	1.2
[setup]
img←¿[4000 3000 3]⍴0 ⋄ flat←,img ⋄ n←≢flat
[images]
# A 4000×3000 image with three channels holds 36 million floats, far more than the caches hold. Each call in a fused graph reads and writes every item.
0⌈1⌊0.5+1.2×img-0.5	7	11
img×1-0.5×img	5.5	6.8
0⌈1⌊img×0.5+(⍳4000)÷8000	5.6	7
# `×` joins the fused graphs on its two sides into one graph that runs block by block.
(img-0.5)×img+0.5	5	7.1
# A reduction at the end of a fused graph folds each block's results while they are in the cache. Along the first axis, it adds each block to one total for each column.
+/flat>0.5	1.6	2
+⌿img×2	3.5	4.1
# `+/img` folds each pixel's 3 channels. Each length of lane up to 15 items has a loop of its own. The reshape shares `flat`'s storage.
+/img	1.9	2
+/[4500000 8]⍴flat	1.7	1.7
# The comparison's Booleans count into a byte for each pixel.
+/img>0.5	1.8	3.4
[setup]
mx←¯0.5+¿[1024 64]⍴0 ⋄ my←1○+/mx ⋄ mp←["w":0.25×¯0.5+¿[64 256]⍴0 "b":256⍴0 "v":0.1×¯0.5+¿256⍴0 "c":0]
mlp←{[x y]←⍺ ⋄ [w b v c]←⍵ ⋄ h←7○b+⍤1 x+.×w ⋄ (+/÷≢)⊼y-c+h+.×v}
gx←¿[1000 32]⍴0 ⋄ gi←=⊗⍨⍳32 ⋄ glow←>⊗⍨⍳32 ⋄ gp←["alpha":¿25⍴0 "mu":¿[25 32]⍴0 "q":0.1×¿[25 32]⍴0 "l":0.1×¿[25 32 32]⍴0]
gmm←{[alpha mu q l]←⍵ ⋄ L←l×⍤2⊢glow ⋄ Q←L+(*q)×⍤1 2⊢gi ⋄ sq←+/⊼(⍺(-⍤1)⍤2 1⊢mu)+.×⍤2⊢0 2 1⍉Q ⋄ t←(alpha++/q)-0.5×sq ⋄ m←⌈⌿t ⋄ am←⌈/alpha ⋄ (+/m+⍟+⌿*t-⍤1⊢m) + (0.5×(+/,⊼*q)++/,⊼L) - (≢⍺)×am+⍟+/*alpha-am}
kx←¿[16384 32]⍴0 ⋄ kc←¿[64 32]⍴0 ⋄ kmeans←{+/⌊⌿((+/⊼⍵)+⊗+/⊼⍺)-2×⍵+.×⍉⍺}
sg←¿[128 128]⍴0 ⋄ sk←[1 2 1⋄2 4 2⋄1 2 1]÷16 ⋄ n←65536
dx←¿1048576⍴0 ⋄ dp←["w":¿[64 256]⍴0 "b":¿256⍴0 "v":¿256⍴0 "c":1]
[objectives]
# Functions that `∂` will differentiate, timed without `∂`. Each gives the cost that its gradient's cost will be measured against.
# The mean squared error of a network with one hidden layer of 256 tanh units, over 1024 inputs of 64 values. Its parameters are in a record.
[mx my] mlp mp	490	630
# ADBench's Gaussian mixture objective, for 1000 points in 32 dimensions and 25 components, without its constant terms and with its Wishart prior at gamma 1 and m 0. Each component's precision factor has the exponentials of `q` on its diagonal and `l` below it.
gx gmm gp	640	680
# The k-means cost sums the squared distance from each of 16384 points to the nearest of 64 centres, in 32 dimensions.
kx kmeans kc	870	980
# A 3 by 3 blur of a 128 by 128 grid. `⌺` calls its operand once for each window.
{+/,sk×⍵}⌺3 3⊢sg	8000	14000
[derivatives]
# `∂` beside the function it differentiates. A unit argument takes one pass, whose tangent is an array of the result's shape. The bar's "Primal cost" row in the design notes asks that the primal keeps its kernels, and the tangent adds whole-array calls beside it.
1○dx	230	570
{1○dx+⍵}∂0	550	1400
# A chain of fusible calls, whose tangent fuses too.
(dx-0.5)×dx+0.5	120	140
{(dx-⍵)×dx+⍵}∂0.5	220	340
# A JVP of the training loss in `[objectives]` along a fixed direction `dp`, which takes one pass through `+.×`, Rank, `7○` and `+/`.
{[mx my] mlp mp+⍵×dp}∂0	650	970
# Gradients of the three objectives in `[objectives]`, each from one run that records its linear calls and one transpose of the record. The bar's "Gradient cost" row asks for a small multiple of the objective's own cost.
[mx my] mlp∂ mp	780	1200
gx gmm∂ gp	5500	5200
kx kmeans∂ kc	7700	5500
[setup]
fib←{⍵<2?⍵;(∇⍵-1)+∇⍵-2} ⋄ n←65536
[calls]
# `fib 16` makes 3193 calls of a dfn, each with up to four primitive calls on single numbers. Its cost is mostly the evaluator's own work for each call.
fib 16	800	740
[setup]
sv←¿1048576⍴0 ⋄ n←≢sv ⋄ sm←[n÷2;2]⍴sv
[structure]
# A structural glyph on a million floats gives a pending copy, which the call around it reads through, with no pass of its own over memory. A forward run is read in place. A reversed one is copied into a buffer for each block.
2×⌽sv+1	6.4	11
2×1⌽sv+1	4.4	4.5
2×(10↓sv)+1	4.4	4.8
+/(⌽sv)×sv	5.9	8.8
# Floor returns exact integers, so this reads a pending copy through an ordinary kernel rather than fusion.
⌊⌽sv	14	16
# Stride-two columns gather through the shared reader before their contiguous subtraction.
(∞ 1⌷sm)-(∞ 0⌷sm)	5	12
