1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
//! Serial cost classes and the parallel gate of the strided kernels.
//!
//! A kernel does not own a minimum length. It states how long its region takes
//! on one thread (elements times the serial throughput of its class) and asks
//! the placement token whether that pays: a region runs in parallel when the
//! serial time is at least [`threadteam::PAYS`] times the dispatch cost of every
//! section it opens (`Exec::pays`). The cost of a section belongs to the token
//! and the thread that calls, not to this crate; the design record is
//! `threadteam`'s `docs/design/thresholds.md`.
//!
//! # The class table
//!
//! This table is the only place the throughputs live (the `Copy` row is owned by
//! `strided-perm`, which sits below this crate). Every kernel of the workspace is
//! one of four classes, and the rate of a class depends on the *host class*
//! (`strided_perm::HostClass`, keyed by the kernel dispatch the machine takes,
//! detected once at first use; the enum is `threadteam::HostClass` re-exported by
//! `strided-perm`). Serial, `f64`, in nanoseconds per element:
//!
//! | [`KernelClass`] | `x86_64-avx512` | `aarch64-apple` | `generic` (every other class) | kernels |
//! | --- | --- | --- | --- | --- |
//! | `Copy` | 0.171 | 0.090 | 0.090 | copies, fills, permutations, gathers, static indexing, transposes |
//! | `Map` | 0.173 | 0.100 | 0.100 | element-wise map, zip, add_acc, mul_acc, axpy_acc, fma_acc, in-place update, fused arithmetic chains |
//! | `Transcendental` | 5.60 | 1.38 | 1.38 | `exp`, `ln`, `tanh`, other libm-like functions (fused chains that contain one, softmax) |
//! | `Reduce` | 0.104 | 0.081 | 0.081 | sum, dot, reduce, zip-reduce, axis reductions, norms, scans and arg-reductions |
//!
//! * `aarch64-apple`: one Apple M5 Max core, memory resident (thresholds.md
//! section 3.2).
//! * `x86_64-avx512`: an AMD Ryzen AI 9 HX 470 at 2.0 GHz (boost off), from the
//! `seq` column of the strided probes (`copy`, `map`, `exp`, `sum`) in
//! `faer-benchmark` `data/probes/20261026-awake-team-linux/tables-confirm-exec3.md`
//! (width 8 table): the median over the L2-resident sizes 16384, 32768 and
//! 65536 elements of `seq us * 1000 / elements`. Copy 2.80, 4.29, 13.17 us give
//! 0.171, 0.131, 0.201; map 2.84, 5.21, 15.39 us give 0.173, 0.159, 0.235; exp
//! 91.77, 180, 419 us give 5.60, 5.49, 6.39; sum 1.71, 3.55, 6.65 us give 0.104,
//! 0.108, 0.102.
//! * `generic` (`x86_64-avx2`, `x86_64-scalar`, `aarch64`, `generic`: no
//! measurement): the fastest known value of each row, the minimum over the
//! measured classes. It is the conservative choice: a rate that is too small
//! keeps work serial.
//!
//! The rates of a class and the dispatch costs of the same class in `threadteam`
//! come from the same machine in the same clock state: boost on or off moves both
//! by about 1.66x and leaves their ratio stable within a few percent
//! (`raw-exec3-boost`, `tables-*-exec3-boost.md`).
//!
//! A reduction counts the source elements it reads (outputs times reduced
//! elements). A kernel with a cost not in the table is classified by the nearest
//! row, never given a constant of its own.
//!
//! A [`CopyPlan`](crate::CopyPlan) prices itself above the `Copy` row by the runs
//! its walk takes: `Copy` row + one cache line per run
//! (`copy_ns_per_element_for_plan`, which carries the measurement of both
//! regimes; strided-rs#364). A run is a contiguous stretch of the walk on both
//! sides, so a transposing plan walks one element per run and pays a line per
//! element: a hit inside the class's L2, one DRAM line past it. The footprint and
//! the run structure are both known in `CopyPlan::compile`, so the plan carries
//! them and nothing is probed at run time, and the rate reaches every scheduling
//! decision the replay makes: the width of the replay that is not tiled
//! (`for_len_at_rate`) and both the fork gate and every node of the recursive
//! splitter of the tiled replay of strided-rs#422 (`is_parallel_at_rate`). A
//! contiguous run keeps the row at every size:
//! a streamed unit-stride copy measures the row's rate past L2 as well, which is
//! why the row itself is not raised. Every other kernel still prices itself at
//! the row.
//!
//! # Sections
//!
//! `sections` is the number of dispatches the entry performs, counted truthfully:
//!
//! * A *flat* entry (`Exec::for_ranges`: the copy and fill helpers, the
//! permutation engine, the axis-chunked kernels) publishes the region once:
//! 1 section at the chosen width.
//! * A *tree* entry (the recursive halving of `parallel_map_reduce` and of the
//! dimension splitter) forks twice per level and the children fork again on
//! half of the budget, so the critical path holds `ceil(log2 width)` sections.
//! The splitter gates every node on its own fork (1 section at width 2) because
//! each child decides again for the work it has left.
use NonZeroUsize;
use Duration;
use ;
use Exec;
/// Working set, in bytes, past which a copy pays L3/DRAM traffic instead of the
/// L2-resident rate: the L2 size of both hosts behind the `x86_64-avx512` `Copy`
/// row (1 MiB per core on the Zen 5 host of the worklog of `strided-rs#364` and
/// on the Xeon Platinum 9242 of `strided-rs#363`).
const COPY_L2_BYTES: usize = 1 << 20;
/// Serial throughput of a copy whose working set is past the class's L2 cache and
/// whose runs are one element long, in nanoseconds per element: the sum of the
/// `Copy` row and one DRAM line per element, 3.0 on the `x86_64-avx512` class
/// (the derivation is below).
const COPY_BEYOND_L2_NS_PER_RUN: f64 = 3.0;
/// Extra nanoseconds per run of the walk while the working set fits the class's
/// L2 cache: one further cache line touched per run, on the line-hitting side.
///
/// Derived from the three in-L2 transposing rows of strided-rs#363's table (Intel
/// Xeon Platinum 9242, serial and warm, `f64`, one-element runs) minus the 0.171
/// row: `n` = 64 measures 0.65-0.68 (0.48-0.51 over the row), 128 measures 0.78
/// (0.61 over) and 256 measures 0.90-0.94 (0.73-0.77 over). The median is 0.609
/// and is rounded to 0.61, which puts every one of those rows within 1.25x: 64
/// prices at 0.781 against 0.65-0.68 (1.20x), 128 at 0.781 against the measured
/// 0.78, and 256 at 0.781 against 0.90-0.94 (1.20x).
const COPY_NS_PER_RUN_RESIDENT: f64 = 0.61;
/// Serial throughput of a copy in nanoseconds per element on `host` for a plan
/// whose source and destination span `bytes` bytes together and whose walk covers
/// `run_len` elements per run: `Copy` row + [`COPY_NS_PER_RUN_RESIDENT`] (or one
/// DRAM line, past [`COPY_L2_BYTES`]) per run, i.e. the `segments * per_segment +
/// elements * per_element` cost of strided-rs#364 divided by `elements`, since
/// `segments = elements / run_len`.
///
/// A run is a contiguous stretch of the walk on both sides; a transposing plan
/// walks one element per run, so it pays a cache line per element. Inside the
/// class's L2 that line is a hit ([`COPY_NS_PER_RUN_RESIDENT`]); past it the plan
/// touches a new line per element: it reads a line to take one `f64` out of it and
/// writes a line to put it down, so the cost is the L3/DRAM traffic of the plan and
/// the line is [`COPY_BEYOND_L2_NS_PER_RUN`] minus the row.
///
/// Past [`COPY_L2_BYTES`] this is a calibration of the *tiled* transposing path;
/// the replay that is not tiled is not calibrated row by row. A transposing
/// `n x n` `f64` copy measures 2.33-2.45 ns per element at `n` = 512 and 1024 on
/// the Zen 5 host of
/// `docs/worklogs/2026-11-09-issue-364-copy-plan-footprint.md`, and 2.91-3.24 on
/// the Xeon Platinum 9242 (`n` = 512 and 1024, quoted from the table of #364), so
/// the beyond-L2 rate is 3.0: 3.0 / 2.33 = 1.29, 3.0 / 3.24 = 0.93, i.e. within
/// 1.3x of every one of those medians, and 9.7 / 3.0 = 3.2 below the 7.2-9.7 the
/// same host measured before strided-rs#422 tiled its transposed path.
///
/// A *contiguous* copy is not priced here: it streams 0.176-0.177 ns per element
/// at 2 and 16 MiB on that host, which is the row within 4%, so a plan that is one
/// unit-stride run keeps the row at every footprint (the caller does not ask this
/// function for such a plan). Every class without a beyond-L2 measurement keeps the
/// row at every size: only `x86_64-avx512` has the second rate.
///
/// A traversal whose runs are shorter than a cache line may be worse than 3.0: a
/// rank-1 run at stride 256 (one element per 2 KiB) measured 9.6-12.7 ns per element
/// under a co-tenant process. A contended sample cannot establish the uncontended
/// value, so this is recorded as an observation and this rate is not claimed to
/// under- or over-price that extreme.
pub
/// Serial cost class of a kernel; see the module documentation of `strided-basic/src/cost.rs` for the
/// table.
///
/// # Examples
///
/// ```
/// use strided_basic::execution::KernelClass;
///
/// assert!(KernelClass::Transcendental.ns_per_element() > KernelClass::Map.ns_per_element());
/// // 1e6 elements at the rate of this host's class.
/// let ns = KernelClass::Map.ns_per_element() * 1e6;
/// assert_eq!(KernelClass::Map.estimate(1_000_000).as_nanos() as f64, ns.round());
/// ```
const ONE: NonZeroUsize = MIN;
/// Width of a flat entry (one section) that `exec` should use for `elements`
/// elements of `class`: the width in `1..=budget` that minimises the section
/// cost plus the share of the work, `1` when no width pays.
///
/// # Examples
///
/// ```
/// use strided_basic::execution::{parallel_width, KernelClass};
/// use strided_basic::Exec;
///
/// assert_eq!(parallel_width(&Exec::serial(), KernelClass::Copy, usize::MAX >> 8).get(), 1);
/// ```
/// Width of a tree entry (`parallel_map_reduce`): the width in `1..=budget`
/// that minimises `ceil(log2 k) * D(k) + estimate / k` among the widths at which
/// `ceil(log2 k)` sections pay, `1` when none does.
///
/// # Examples
///
/// ```
/// use strided_basic::execution::{tree_width, KernelClass};
/// use strided_basic::Exec;
///
/// assert_eq!(tree_width(&Exec::serial(), KernelClass::Reduce, usize::MAX >> 8).get(), 1);
/// ```
/// Narrows `exec` to the width a flat entry over `len` elements of `class` justifies.
pub
/// Narrows `exec` to the width a flat entry over `len` elements costing
/// `ns_per_element` each justifies.
///
/// [`for_len`] is this function at the rate of a class. A `CopyPlan` passes a rate
/// of its own: one whose traversal is not a single contiguous run pays a cache
/// line per run on top of the row
/// (`copy_ns_per_element_for_plan`, strided-rs#364).
pub
/// Narrows `exec` to the width a tree entry over `len` elements of `class` justifies.
pub
/// Whether one fork of `exec` over `len` elements of `class` pays: the gate of a
/// node of the dimension splitter and of the entries that call it.
pub
/// Whether one fork of `exec` over `len` elements costing `ns_per_element` each
/// pays: the gate of a node of the dimension splitter, at the rate its caller
/// prices the work at.
///
/// [`is_parallel`] is this function at the rate of a class. A `CopyPlan` passes its
/// own rate, so the tiled splitter of strided-rs#422 opens the same fork the plan's
/// width rule asks for (`copy_ns_per_element_for_plan`, strided-rs#364).
pub