strided_basic/raw_ops.rs
1//! Allocation-free copy/axpy over borrowed raw strided layouts.
2//!
3//! The map/zip kernels build a traversal plan per call; for small replay
4//! copies that fixed cost dominates. These entry points take
5//! [`RawStridedRef`]/[`RawStridedMut`], fuse the stride pair into a loop nest
6//! (inline storage for fused ranks at most [`RAW_FUSED_RANK_LIMIT`], a stack
7//! layout bounded by the moving-axis count above that), and run plain loops -
8//! no view plan, no cache, and no per-element allocation on any call path; the
9//! `replay_*_raw` entries allocate nothing at any rank on a serial token.
10//! Higher *original* ranks are normalized and fused before that choice is
11//! made, so they no longer leave the fused replay.
12
13use crate::cost::KernelClass;
14use crate::{ElementOpApply, Exec, RawStridedMut, RawStridedRef, Result};
15use core::mem::MaybeUninit;
16use core::num::NonZeroUsize;
17use core::ops::{Add, Mul};
18
19/// Rank up to which a fused loop nest is stored inline.
20///
21/// It selects the traversal: a layout of at most this many axes replays through
22/// the inline loop nest, a longer one through the out-of-line wide loop. It
23/// does not decide allocation for the `replay_*_raw` entries, which allocate
24/// nothing at any rank on a serial token (see [`replay_copy_raw`]).
25///
26/// The stateless [`copy_scale_raw`] family and the compilation of
27/// [`crate::CopyPlan`] fuse any rank. An *original* rank above this limit needs
28/// one transient fusion scratch buffer there even when the fused layout still
29/// fits inline, because fusion happens before the representation is chosen.
30pub const RAW_FUSED_RANK_LIMIT: usize = 8;
31
32/// Capacity of the stack storage of the wide replay route.
33///
34/// A replay reaches its loops only with a checked, nonzero element count, and
35/// every axis of extent above 1 at least doubles that count, so
36/// `2^m <= total <= usize::MAX` bounds the `m` moving axes by
37/// `usize::BITS - 1`. Extent-1 axes are dropped before the bound is used: their
38/// coordinate is 0 throughout the walk, so dropping them changes neither the
39/// slots nor their column-major order.
40pub(crate) const MAX_MOVING_AXES: usize = usize::BITS as usize;
41
42/// One fused axis, used while sorting and merging axes and when a layout has to
43/// spill beyond [`RAW_FUSED_RANK_LIMIT`].
44#[derive(Clone, Copy, Debug)]
45pub(crate) struct FusedAxis {
46 pub(crate) dim: usize,
47 pub(crate) dst: isize,
48 pub(crate) src: isize,
49}
50
51const EMPTY_AXIS: FusedAxis = FusedAxis {
52 dim: 1,
53 dst: 0,
54 src: 0,
55};
56
57/// Stack-allocated fused stride pair (axes ordered by destination stride,
58/// adjacent contiguous axes merged). Built once and replayed by both the
59/// per-call raw kernels and the prepared [`crate::CopyPlan`].
60///
61/// This is the representation every call site replays through, so it keeps the
62/// exact shape, size and `Copy`-ness it had before high-rank fusion existed.
63#[derive(Clone, Copy, Debug)]
64pub(crate) struct FusedPairLayout {
65 pub(crate) rank: usize,
66 pub(crate) dims: [usize; RAW_FUSED_RANK_LIMIT],
67 pub(crate) dst_strides: [isize; RAW_FUSED_RANK_LIMIT],
68 pub(crate) src_strides: [isize; RAW_FUSED_RANK_LIMIT],
69}
70
71impl FusedPairLayout {
72 /// An empty rank-zero layout (one element at the base offset).
73 ///
74 /// Used as the neutral value when an inline `TinyVec<[CopyPlan; N]>` is
75 /// default-initialized; it is never executed as a real plan.
76 fn empty() -> Self {
77 Self {
78 rank: 0,
79 dims: [1; RAW_FUSED_RANK_LIMIT],
80 dst_strides: [0; RAW_FUSED_RANK_LIMIT],
81 src_strides: [0; RAW_FUSED_RANK_LIMIT],
82 }
83 }
84
85 fn from_axes(axes: &[FusedAxis]) -> Self {
86 debug_assert!(axes.len() <= RAW_FUSED_RANK_LIMIT);
87 let mut layout = Self {
88 rank: axes.len(),
89 dims: [1; RAW_FUSED_RANK_LIMIT],
90 dst_strides: [0; RAW_FUSED_RANK_LIMIT],
91 src_strides: [0; RAW_FUSED_RANK_LIMIT],
92 };
93 for (slot, axis) in layout.dims[..axes.len()].iter_mut().zip(axes) {
94 *slot = axis.dim;
95 }
96 for (slot, axis) in layout.dst_strides[..axes.len()].iter_mut().zip(axes) {
97 *slot = axis.dst;
98 }
99 for (slot, axis) in layout.src_strides[..axes.len()].iter_mut().zip(axes) {
100 *slot = axis.src;
101 }
102 layout
103 }
104}
105
106/// A fused pair traversal of any rank.
107///
108/// Fused ranks at most [`RAW_FUSED_RANK_LIMIT`] use the inline layout; longer
109/// layouts keep their axes in one `Vec`. That storage is sized by the original
110/// rank (the fusion scratch is reused, and `truncate` keeps its capacity), never
111/// by the tensor's element count.
112#[derive(Clone, Debug)]
113pub(crate) enum PairTraversal {
114 Inline(FusedPairLayout),
115 Spilled(Vec<FusedAxis>),
116}
117
118impl Default for FusedPairLayout {
119 fn default() -> Self {
120 Self::empty()
121 }
122}
123
124impl Default for PairTraversal {
125 fn default() -> Self {
126 Self::empty()
127 }
128}
129
130impl PairTraversal {
131 /// The empty inline layout, used as a neutral default.
132 #[inline]
133 fn empty() -> Self {
134 Self::Inline(FusedPairLayout::empty())
135 }
136
137 /// Run `f` on the replay route of this traversal: its axes with the cache
138 /// tiles of destination element `D` and source element `S`, or no tiles
139 /// when the column-major walk is kept.
140 ///
141 /// The one decision entry point for both storage shapes, so a plan and a
142 /// replay entry ask the same question whatever the fused rank. A spilled
143 /// traversal decides in [`with_spilled_route`], whose stack frame holds the
144 /// wide tiles while `f` runs.
145 pub(crate) fn with_route<D, S, R>(&self, f: impl FnOnce(Route<'_>) -> R) -> R {
146 match self {
147 Self::Inline(layout) => {
148 let tiles = pair_tiles::<D, S>(layout);
149 f(Route::Inline {
150 layout,
151 tiles: tiles.as_ref(),
152 })
153 }
154 Self::Spilled(axes) => with_spilled_route::<D, S, R>(axes, f),
155 }
156 }
157
158 /// The cache tiles of this traversal, copied out of its route.
159 #[cfg(test)]
160 pub(crate) fn tiles<D, S>(&self) -> Option<Tiles> {
161 self.with_route::<D, S, _>(|route| route.snapshot())
162 }
163
164 /// Whether [`Self::with_route`] can tile for any element types: `false`
165 /// when the traversal covers at most one element or has fewer than two
166 /// axes of extent above 1, the exits [`pair_tiles`] and
167 /// [`with_spilled_route`] take before they look at an element size. Such
168 /// a traversal is one run, whose order no block vector can change.
169 pub(crate) fn may_tile(&self) -> bool {
170 let (total, moving) = match self {
171 Self::Inline(layout) => (
172 fused_total(layout),
173 layout.dims[..layout.rank]
174 .iter()
175 .filter(|&&dim| dim != 1)
176 .count(),
177 ),
178 Self::Spilled(axes) => (
179 spilled_total(axes),
180 axes.iter().filter(|axis| axis.dim != 1).count(),
181 ),
182 };
183 total > 1 && moving >= 2
184 }
185
186 /// The inline layout, or `None` when the traversal spilled.
187 #[inline]
188 pub(crate) fn inline(&self) -> Option<&FusedPairLayout> {
189 match self {
190 Self::Inline(layout) => Some(layout),
191 Self::Spilled(_) => None,
192 }
193 }
194
195 /// Number of fused axes.
196 #[cfg(test)]
197 pub(crate) fn rank(&self) -> usize {
198 match self {
199 Self::Inline(layout) => layout.rank,
200 Self::Spilled(axes) => axes.len(),
201 }
202 }
203}
204
205/// Sort `dims`/`dst_strides`/`src_strides` by destination stride, drop size-1
206/// axes, and merge axes that are contiguous in both layouts.
207///
208/// Returns the fused rank written to `scratch[..rank]`. A zero extent collapses
209/// to a single zero-length axis, which every replay treats as an empty range.
210fn fuse_axes(
211 scratch: &mut [FusedAxis],
212 dims: &[usize],
213 dst_strides: &[isize],
214 src_strides: &[isize],
215) -> usize {
216 debug_assert!(scratch.len() >= dims.len());
217 let mut rank = 0usize;
218 for axis in 0..dims.len() {
219 if dims[axis] == 1 {
220 continue;
221 }
222 if dims[axis] == 0 {
223 scratch[0] = FusedAxis {
224 dim: 0,
225 dst: 0,
226 src: 0,
227 };
228 return 1;
229 }
230 let entry = FusedAxis {
231 dim: dims[axis],
232 dst: dst_strides[axis],
233 src: src_strides[axis],
234 };
235 let mut position = rank;
236 while position > 0 && scratch[position - 1].dst > entry.dst {
237 scratch[position] = scratch[position - 1];
238 position -= 1;
239 }
240 scratch[position] = entry;
241 rank += 1;
242 }
243 if rank == 0 {
244 scratch[0] = EMPTY_AXIS;
245 return 1;
246 }
247 let mut fused = 0usize;
248 for axis in 1..rank {
249 // A merged extent that overflows (possible for a stride-0 broadcast
250 // whose element count exceeds usize) leaves the axes unfused.
251 let merged = isize::try_from(scratch[fused].dim)
252 .ok()
253 .filter(|&extent| {
254 scratch[fused].dst.checked_mul(extent) == Some(scratch[axis].dst)
255 && scratch[fused].src.checked_mul(extent) == Some(scratch[axis].src)
256 })
257 .and_then(|_| scratch[fused].dim.checked_mul(scratch[axis].dim));
258 if let Some(merged) = merged {
259 scratch[fused].dim = merged;
260 } else {
261 fused += 1;
262 scratch[fused] = scratch[axis];
263 }
264 }
265 fused + 1
266}
267
268/// Fuse a raw stride pair into a traversal of any rank.
269///
270/// Inline when the fused rank is at most [`RAW_FUSED_RANK_LIMIT`], otherwise one
271/// rank-bounded spill. An original rank above the limit uses a transient scratch
272/// buffer even when the fused layout still fits inline, so that fusion happens
273/// before the representation is chosen.
274pub(crate) fn fuse_pair_traversal(
275 dims: &[usize],
276 dst_strides: &[isize],
277 src_strides: &[isize],
278) -> PairTraversal {
279 if dims.len() <= RAW_FUSED_RANK_LIMIT {
280 let mut scratch = [EMPTY_AXIS; RAW_FUSED_RANK_LIMIT];
281 let rank = fuse_axes(&mut scratch, dims, dst_strides, src_strides);
282 debug_assert!(rank <= RAW_FUSED_RANK_LIMIT);
283 return PairTraversal::Inline(FusedPairLayout::from_axes(&scratch[..rank]));
284 }
285 let mut scratch = vec![EMPTY_AXIS; dims.len()];
286 let rank = fuse_axes(&mut scratch, dims, dst_strides, src_strides);
287 scratch.truncate(rank);
288 if rank <= RAW_FUSED_RANK_LIMIT {
289 PairTraversal::Inline(FusedPairLayout::from_axes(&scratch))
290 } else {
291 PairTraversal::Spilled(scratch)
292 }
293}
294
295impl PairTraversal {
296 /// The traversal [`with_given_route`] replays for the given axes, as an
297 /// owned value for the tests.
298 #[cfg(test)]
299 pub(crate) fn given(dims: &[usize], dst_strides: &[isize], src_strides: &[isize]) -> Self {
300 with_given_route::<(), (), _>(dims, dst_strides, src_strides, |route| match route {
301 Route::Inline { layout, .. } => Self::Inline(*layout),
302 Route::Spilled { axes, .. } => Self::Spilled(axes.to_vec()),
303 })
304 }
305}
306
307/// A replay route borrowed from the frame that decided it: the axes to walk
308/// and, when the walk is tiled, their cache tiles.
309///
310/// The wide storage lives in the out-of-line frames of [`with_spilled_route`]
311/// and [`with_given_route`], so the inline route's frame never holds it.
312#[derive(Clone, Copy, Debug)]
313pub(crate) enum Route<'a> {
314 Inline {
315 layout: &'a FusedPairLayout,
316 tiles: Option<&'a PairTiles>,
317 },
318 Spilled {
319 axes: &'a [FusedAxis],
320 tiles: Option<&'a SpilledTiles>,
321 },
322}
323
324impl<'a> Route<'a> {
325 /// Whether the route walks cache tiles.
326 pub(crate) fn is_tiled(&self) -> bool {
327 match self {
328 Self::Inline { tiles, .. } => tiles.is_some(),
329 Self::Spilled { tiles, .. } => tiles.is_some(),
330 }
331 }
332
333 /// The same axes walked column-major.
334 pub(crate) fn untiled(self) -> Self {
335 match self {
336 Self::Inline { layout, .. } => Self::Inline {
337 layout,
338 tiles: None,
339 },
340 Self::Spilled { axes, .. } => Self::Spilled { axes, tiles: None },
341 }
342 }
343
344 /// The block vector of the tiles over their compressed axes, or `None` for
345 /// the column-major walk.
346 #[cfg(feature = "bench-hooks")]
347 pub(crate) fn blocks(&self) -> Option<&'a [usize]> {
348 match *self {
349 Self::Inline { tiles, .. } => tiles.map(|tiles| &tiles.blocks[..tiles.layout.rank]),
350 Self::Spilled { tiles, .. } => tiles.map(SpilledTiles::blocks),
351 }
352 }
353
354 /// The tiles of the route, copied out.
355 #[cfg(test)]
356 pub(crate) fn snapshot(self) -> Option<Tiles> {
357 match self {
358 Self::Inline { tiles, .. } => tiles.copied().map(Tiles::Inline),
359 Self::Spilled { tiles, .. } => tiles.copied().map(Tiles::Spilled),
360 }
361 }
362}
363
364/// Run `f` on the replay route of the given axes, in their given order:
365/// nothing is sorted or merged. Rank zero becomes the one-element
366/// `EMPTY_AXIS` layout that [`fuse_axes`] also produces.
367///
368/// The three slices must have equal length, and the extents a checked,
369/// nonzero product (the replay totals multiply them unchecked). A rank above
370/// [`RAW_FUSED_RANK_LIMIT`] is compacted to its moving axes first, out of line
371/// ([`with_wide_given_route`]).
372pub(crate) fn with_given_route<D, S, R>(
373 dims: &[usize],
374 dst_strides: &[isize],
375 src_strides: &[isize],
376 f: impl FnOnce(Route<'_>) -> R,
377) -> R {
378 debug_assert!(dims.len() == dst_strides.len() && dims.len() == src_strides.len());
379 let rank = dims.len();
380 if rank > RAW_FUSED_RANK_LIMIT {
381 return with_wide_given_route::<D, S, R>(dims, dst_strides, src_strides, f);
382 }
383 let mut layout = FusedPairLayout::empty();
384 layout.rank = rank.max(1);
385 layout.dims[..rank].copy_from_slice(dims);
386 layout.dst_strides[..rank].copy_from_slice(dst_strides);
387 layout.src_strides[..rank].copy_from_slice(src_strides);
388 let tiles = pair_tiles::<D, S>(&layout);
389 f(Route::Inline {
390 layout: &layout,
391 tiles: tiles.as_ref(),
392 })
393}
394
395/// [`with_given_route`] above [`RAW_FUSED_RANK_LIMIT`] given axes: the moving
396/// axes, in their given order, in a stack array. At most
397/// [`RAW_FUSED_RANK_LIMIT`] of them replay through the inline layout, more
398/// through [`with_spilled_route`].
399///
400/// The tile decision is the one the given axes would get: the model already
401/// drops extent-1 axes before it decides.
402#[inline(never)]
403fn with_wide_given_route<D, S, R>(
404 dims: &[usize],
405 dst_strides: &[isize],
406 src_strides: &[isize],
407 f: impl FnOnce(Route<'_>) -> R,
408) -> R {
409 let mut axes = [EMPTY_AXIS; MAX_MOVING_AXES];
410 let mut moving = 0;
411 for ((&dim, &dst), &src) in dims.iter().zip(dst_strides).zip(src_strides) {
412 if dim == 1 {
413 continue;
414 }
415 // INVARIANT: the caller's checked nonzero count gives
416 // `2^moving <= total <= usize::MAX`, so `moving < MAX_MOVING_AXES`.
417 axes[moving] = FusedAxis { dim, dst, src };
418 moving += 1;
419 }
420 if moving <= RAW_FUSED_RANK_LIMIT {
421 let layout = FusedPairLayout::from_axes(if moving == 0 {
422 &[EMPTY_AXIS]
423 } else {
424 &axes[..moving]
425 });
426 let tiles = pair_tiles::<D, S>(&layout);
427 return f(Route::Inline {
428 layout: &layout,
429 tiles: tiles.as_ref(),
430 });
431 }
432 with_spilled_route::<D, S, R>(&axes[..moving], f)
433}
434
435/// Run `f` on the replay route of a spilled axis list: more than
436/// [`RAW_FUSED_RANK_LIMIT`] axes, every extent at least 2, and a checked
437/// product (fused or compacted axes).
438///
439/// The exits the model decides before its metadata are answered from the axes
440/// first ([#425]), so a layout they answer never sets up the tiles' storage.
441///
442/// [#425]: https://github.com/tensor4all/strided-rs/issues/425
443#[inline(never)]
444fn with_spilled_route<D, S, R>(axes: &[FusedAxis], f: impl FnOnce(Route<'_>) -> R) -> R {
445 debug_assert!(axes.len() > RAW_FUSED_RANK_LIMIT && axes.iter().all(|axis| axis.dim >= 2));
446 if crate::block::exits_before_metadata(
447 axes.iter().map(|axis| (axis.dim, axis.dst, axis.src)),
448 core::mem::size_of::<D>(),
449 core::mem::size_of::<S>(),
450 ) {
451 return f(Route::Spilled { axes, tiles: None });
452 }
453 with_modelled_spilled_route::<D, S, R>(axes, f)
454}
455
456/// [`with_spilled_route`] past the model's early exits: the tiles live in this
457/// frame while `f` runs, so neither the inline route nor an early exit carries
458/// their storage.
459#[inline(never)]
460fn with_modelled_spilled_route<D, S, R>(axes: &[FusedAxis], f: impl FnOnce(Route<'_>) -> R) -> R {
461 let mut tiles = SpilledTiles::EMPTY;
462 let tiled = spilled_tiles::<D, S>(axes, &mut tiles);
463 f(Route::Spilled {
464 axes,
465 tiles: tiled.then_some(&tiles),
466 })
467}
468
469/// Fuse a raw stride pair into the inline representation.
470///
471/// Returns `None` when the fused rank exceeds [`RAW_FUSED_RANK_LIMIT`]. Used by
472/// the window plans, whose non-fused replay is compiled alongside the plan.
473pub(crate) fn fuse_pair_layout(
474 dims: &[usize],
475 dst_strides: &[isize],
476 src_strides: &[isize],
477) -> Option<FusedPairLayout> {
478 match fuse_pair_traversal(dims, dst_strides, src_strides) {
479 PairTraversal::Inline(layout) => Some(layout),
480 PairTraversal::Spilled(_) => None,
481 }
482}
483
484/// Number of logical elements covered by a fused layout.
485///
486/// Every constructor of a [`FusedPairLayout`] starts from dims whose product
487/// was checked by [`crate::kernel::total_len`], and fusion only merges axes
488/// with a checked product, so the product cannot overflow.
489#[inline]
490pub(crate) fn fused_total(layout: &FusedPairLayout) -> usize {
491 layout.dims[..layout.rank].iter().product()
492}
493
494/// Number of logical elements covered by a spilled axis list.
495#[inline]
496fn spilled_total(axes: &[FusedAxis]) -> usize {
497 axes.iter().map(|axis| axis.dim).product()
498}
499
500/// The tiles of a route, copied out for the tests.
501#[cfg(test)]
502#[derive(Clone, Debug)]
503#[allow(clippy::large_enum_variant)] // a test snapshot; production borrows `Route`
504pub(crate) enum Tiles {
505 Inline(PairTiles),
506 Spilled(SpilledTiles),
507}
508
509#[cfg(test)]
510impl Tiles {
511 /// The tiles of the inline walk, or `None` for a spilled one.
512 pub(crate) fn inline(&self) -> Option<&PairTiles> {
513 match self {
514 Self::Inline(tiles) => Some(tiles),
515 Self::Spilled(_) => None,
516 }
517 }
518}
519
520/// The cache tiles of a spilled axis list whose rank exceeds
521/// [`RAW_FUSED_RANK_LIMIT`].
522///
523/// `dims`/`dst`/`src` are the axes of the list, every extent at least 2, and
524/// address exactly its slots in the same column-major order. They are stored
525/// in arrays of [`MAX_MOVING_AXES`] and read as `rank`-long slices, because the
526/// tile walk and the dimension splitter both take slices.
527#[derive(Clone, Copy, Debug)]
528pub(crate) struct SpilledTiles {
529 rank: usize,
530 dims: [usize; MAX_MOVING_AXES],
531 dst: [isize; MAX_MOVING_AXES],
532 src: [isize; MAX_MOVING_AXES],
533 blocks: [usize; MAX_MOVING_AXES],
534}
535
536impl SpilledTiles {
537 const EMPTY: Self = Self {
538 rank: 0,
539 dims: [1; MAX_MOVING_AXES],
540 dst: [0; MAX_MOVING_AXES],
541 src: [0; MAX_MOVING_AXES],
542 blocks: [1; MAX_MOVING_AXES],
543 };
544
545 pub(crate) fn dims(&self) -> &[usize] {
546 &self.dims[..self.rank]
547 }
548
549 pub(crate) fn dst(&self) -> &[isize] {
550 &self.dst[..self.rank]
551 }
552
553 pub(crate) fn src(&self) -> &[isize] {
554 &self.src[..self.rank]
555 }
556
557 pub(crate) fn blocks(&self) -> &[usize] {
558 &self.blocks[..self.rank]
559 }
560}
561
562/// The cache tiles of a fused pair layout whose tiled walk visits the slots in
563/// a different order from the column-major walk.
564///
565/// Built by [`pair_tiles`]; `layout` addresses exactly the slots of the layout
566/// it was built from, in the same column-major order, without its extent-1
567/// axes.
568#[derive(Clone, Copy, Debug)]
569pub(crate) struct PairTiles {
570 pub(crate) layout: FusedPairLayout,
571 pub(crate) blocks: [usize; RAW_FUSED_RANK_LIMIT],
572}
573
574/// Cache tiles for replaying `layout` with destination element `D` and source
575/// element `S`, or `None` when the column-major walk is kept.
576///
577/// The extent-1 axes are dropped first: they address offset 0 whatever their
578/// stride, so the compressed layout addresses the same slots in the same
579/// order, and an unvalidated stride on such an axis never reaches the block
580/// arithmetic. Fewer than two remaining axes form one run, whose order no
581/// block vector can change. The blocks come from the shared model
582/// (`block::compute_block_sizes`), which sizes each operand by its own element
583/// size exactly as the view path does. Tiles are returned only when they
584/// change the visit order (the first axis whose block is smaller than its
585/// extent is followed by an axis with a block above 1) and when that change can
586/// reuse a cache line (see [`crate::block::declines_tiles`]).
587///
588/// The extents of `layout` must have a product that fits `usize` (every
589/// constructor of a [`FusedPairLayout`] checks it).
590pub(crate) fn pair_tiles<D, S>(layout: &FusedPairLayout) -> Option<PairTiles> {
591 if fused_total(layout) <= 1 {
592 return None;
593 }
594 let moving = layout.dims[..layout.rank]
595 .iter()
596 .filter(|&&dim| dim != 1)
597 .count();
598 if moving < 2 {
599 return None;
600 }
601 let compressed;
602 let layout = if moving == layout.rank {
603 layout
604 } else {
605 compressed = without_unit_axes(layout);
606 &compressed
607 };
608 let rank = layout.rank;
609 let mut blocks = [1; RAW_FUSED_RANK_LIMIT];
610 tile_blocks::<D, S, { 2 * RAW_FUSED_RANK_LIMIT }, RAW_FUSED_RANK_LIMIT>(
611 &layout.dims[..rank],
612 &layout.dst_strides[..rank],
613 &layout.src_strides[..rank],
614 &mut blocks[..rank],
615 )
616 .then_some(PairTiles {
617 layout: *layout,
618 blocks,
619 })
620}
621
622/// The block vector of the shared cache-block model for already-compressed
623/// axes (`dims`/`dst`/`src` of one length, every extent at least 2), written
624/// to `blocks`; `false` when the column-major walk is kept.
625///
626/// The model's scratch holds `ORDERS` stride-order slots (two per axis) and
627/// `AXES` cost slots, at least what `dims` needs. It is set up only past the
628/// model's exits, so a layout they answer does not pay for it.
629///
630/// The single source of the tiling decision for both storage shapes: the
631/// inline [`FusedPairLayout`] and the spilled [`SpilledTiles`].
632fn tile_blocks<D, S, const ORDERS: usize, const AXES: usize>(
633 dims: &[usize],
634 dst: &[isize],
635 src: &[isize],
636 blocks: &mut [usize],
637) -> bool {
638 let strides = [dst, src];
639 let elem_sizes = [core::mem::size_of::<D>(), core::mem::size_of::<S>()];
640 // `false`: one of the model's exits keeps the full dimensions, which
641 // cannot change the visit order.
642 if crate::block::model_exits(dims, &strides, &elem_sizes) {
643 return false;
644 }
645 let rank = dims.len();
646 // INVARIANT: both callers pass capacities of at least their rank.
647 let mut orders = [0usize; ORDERS];
648 let mut costs = [0isize; AXES];
649 crate::block::reduced_block_sizes_into(
650 dims,
651 &strides,
652 &elem_sizes,
653 blocks,
654 &mut orders[..2 * rank],
655 &mut costs[..rank],
656 );
657 let Some(first_cut) = (0..dims.len()).find(|&axis| blocks[axis] < dims[axis]) else {
658 return false;
659 };
660 if blocks[first_cut + 1..].iter().all(|&block| block == 1) {
661 return false;
662 }
663 // The axes before `first_cut` are walked whole inside every tile, so each
664 // operand is judged with its own element size, as the model now does.
665 if crate::block::declines_tiles(dims, &strides, &elem_sizes, blocks) {
666 return false;
667 }
668 // Operand 0 is the destination, as on the view path (#287).
669 crate::block::fit_l1_sets(dims, &strides, &elem_sizes, 0, blocks);
670 true
671}
672
673/// Cache tiles for replaying a spilled axis list (more than
674/// [`RAW_FUSED_RANK_LIMIT`] axes, every extent at least 2, a checked product)
675/// that [`crate::block::exits_before_metadata`] does not answer, written to
676/// `tiles`; `false` when the column-major walk is kept.
677///
678/// The invariant: an axis list is tiled exactly when the same layout given
679/// inline would be.
680fn spilled_tiles<D, S>(axes: &[FusedAxis], tiles: &mut SpilledTiles) -> bool {
681 let rank = axes.len();
682 // INVARIANT: every axis has an extent of at least 2 and the product is a
683 // checked nonzero count, so `2^rank <= usize::MAX` and
684 // `rank < MAX_MOVING_AXES`.
685 tiles.rank = rank;
686 for (axis, entry) in axes.iter().enumerate() {
687 tiles.dims[axis] = entry.dim;
688 tiles.dst[axis] = entry.dst;
689 tiles.src[axis] = entry.src;
690 }
691 tile_blocks::<D, S, { 2 * MAX_MOVING_AXES }, MAX_MOVING_AXES>(
692 &tiles.dims[..rank],
693 &tiles.dst[..rank],
694 &tiles.src[..rank],
695 &mut tiles.blocks[..rank],
696 )
697}
698
699/// `layout` without its extent-1 axes, in the given order.
700fn without_unit_axes(layout: &FusedPairLayout) -> FusedPairLayout {
701 let mut compressed = FusedPairLayout::empty();
702 let mut rank = 0;
703 for axis in 0..layout.rank {
704 if layout.dims[axis] == 1 {
705 continue;
706 }
707 compressed.dims[rank] = layout.dims[axis];
708 compressed.dst_strides[rank] = layout.dst_strides[axis];
709 compressed.src_strides[rank] = layout.src_strides[axis];
710 rank += 1;
711 }
712 compressed.rank = rank;
713 compressed
714}
715
716/// Replay every logical index of `tile_box` tile by tile: the tiles of extents
717/// `blocks`, anchored at the box origin and clipped to the box, are visited in
718/// column-major order of the tile grid, and each tile is walked in
719/// column-major order by [`apply_fused_range`].
720///
721/// Kept out of line so that the untiled replay keeps its code shape.
722///
723/// # Safety
724///
725/// The [`apply_fused_range`] contract for the whole of `tile_box`, and every
726/// `blocks[axis]` for `axis < tile_box.rank` is at least 1.
727#[inline(never)]
728pub(crate) unsafe fn apply_tiled_box<D, S, Apply>(
729 dst_ptr: *mut D,
730 dst_base: isize,
731 src_ptr: *const S,
732 src_base: isize,
733 tile_box: &FusedPairLayout,
734 blocks: &[usize; RAW_FUSED_RANK_LIMIT],
735 apply: &mut Apply,
736) where
737 D: Copy,
738 S: Copy,
739 Apply: FnMut(&mut D, S),
740{
741 let tiles = tile_count(tile_box, blocks);
742 // SAFETY: forwarded caller contract; `0..tiles` is the whole tile grid.
743 unsafe {
744 apply_tile_range(
745 dst_ptr, dst_base, src_ptr, src_base, tile_box, blocks, 0, tiles, apply,
746 );
747 }
748}
749
750/// Number of tiles of extents `blocks` that cover `tile_box`; at most its
751/// element count, so it cannot overflow.
752pub(crate) fn tile_count(
753 tile_box: &FusedPairLayout,
754 blocks: &[usize; RAW_FUSED_RANK_LIMIT],
755) -> usize {
756 tile_box.dims[..tile_box.rank]
757 .iter()
758 .zip(blocks)
759 .map(|(&dim, &block)| dim.div_ceil(block))
760 .product()
761}
762
763/// Replay the tiles `first..first + count` of `tile_box`, numbered in
764/// column-major order of the tile grid [`apply_tiled_box`] walks, each in
765/// column-major order by [`apply_fused_range`].
766///
767/// Disjoint tile ranges address disjoint logical indices, and the ranges
768/// `0..k`, `k..tile_count` together walk exactly what [`apply_tiled_box`]
769/// walks, in the same order.
770///
771/// # Safety
772///
773/// The [`apply_fused_range`] contract for the whole of `tile_box`, every
774/// `blocks[axis]` for `axis < tile_box.rank` at least 1, and
775/// `first + count` at most [`tile_count`] of `tile_box` and `blocks`.
776#[allow(clippy::too_many_arguments)]
777#[inline(never)]
778pub(crate) unsafe fn apply_tile_range<D, S, Apply>(
779 dst_ptr: *mut D,
780 dst_base: isize,
781 src_ptr: *const S,
782 src_base: isize,
783 tile_box: &FusedPairLayout,
784 blocks: &[usize; RAW_FUSED_RANK_LIMIT],
785 first: usize,
786 count: usize,
787 apply: &mut Apply,
788) where
789 D: Copy,
790 S: Copy,
791 Apply: FnMut(&mut D, S),
792{
793 if count == 0 {
794 return;
795 }
796 let rank = tile_box.rank;
797 let mut tile = *tile_box;
798 // `origin[axis]` is the first box coordinate of the current tile along
799 // `axis`; `dst_tile`/`src_tile` are the offsets of the tile origin.
800 let mut origin = [0usize; RAW_FUSED_RANK_LIMIT];
801 let mut dst_tile = dst_base;
802 let mut src_tile = src_base;
803 // Decode `first` into its tile-grid coordinates, axis 0 fastest.
804 let mut rest = first;
805 for axis in 0..rank {
806 let along = tile_box.dims[axis].div_ceil(blocks[axis]);
807 origin[axis] = (rest % along) * blocks[axis];
808 rest /= along;
809 dst_tile += origin[axis] as isize * tile_box.dst_strides[axis];
810 src_tile += origin[axis] as isize * tile_box.src_strides[axis];
811 tile.dims[axis] = blocks[axis].min(tile_box.dims[axis] - origin[axis]);
812 }
813 let mut left = count;
814 loop {
815 // Counted here, where the tile is walked, so that a test sees the
816 // walk itself and not the range a caller asked for.
817 #[cfg(test)]
818 crate::threading::record_tile_box();
819 // SAFETY: the tile is a sub-box of `tile_box` at a reachable origin, so
820 // the caller's contract covers every logical index of the tile.
821 unsafe {
822 apply_fused_range(
823 dst_ptr,
824 dst_tile,
825 src_ptr,
826 src_tile,
827 &tile,
828 0,
829 fused_total(&tile),
830 apply,
831 );
832 }
833 left -= 1;
834 if left == 0 {
835 return;
836 }
837 // Column-major odometer over the tile grid. An axis advances only
838 // when another tile follows along it, so `blocks[axis]` is at most
839 // its last box coordinate, and it rewinds by its current origin:
840 // every intermediate offset is a reachable offset of the box. The
841 // caller's bound on `first + count` keeps the walk inside the grid.
842 let mut axis = 0;
843 loop {
844 debug_assert!(axis < rank, "tile range past the end of the grid");
845 let next = origin[axis] + blocks[axis];
846 if next < tile_box.dims[axis] {
847 origin[axis] = next;
848 dst_tile += blocks[axis] as isize * tile_box.dst_strides[axis];
849 src_tile += blocks[axis] as isize * tile_box.src_strides[axis];
850 tile.dims[axis] = blocks[axis].min(tile_box.dims[axis] - next);
851 break;
852 }
853 dst_tile -= origin[axis] as isize * tile_box.dst_strides[axis];
854 src_tile -= origin[axis] as isize * tile_box.src_strides[axis];
855 origin[axis] = 0;
856 tile.dims[axis] = blocks[axis].min(tile_box.dims[axis]);
857 axis += 1;
858 }
859 }
860}
861
862/// Replay every logical index of `box_dims`, a sub-box of `tiles`, tile by
863/// tile: the tiles of extents `tiles.blocks`, anchored at the box origin and
864/// clipped to it, are visited in column-major order of the tile grid, and each
865/// tile is walked in column-major order by [`apply_spilled_range`].
866///
867/// The spilled counterpart of [`apply_tiled_box`]: same tile odometer, same
868/// per-element walk as the untiled replay, only the axis storage differs. Kept
869/// out of line so that the untiled spilled replay keeps its code shape. The
870/// tile, its cursor and its origin are stack arrays of [`MAX_MOVING_AXES`].
871///
872/// # Safety
873///
874/// The [`apply_spilled_range`] contract for the whole of `box_dims`, which
875/// must be `tiles.dims` or a sub-box of it anchored at `dst_base`/`src_base`,
876/// and every `tiles.blocks[axis]` at least 1.
877#[allow(clippy::too_many_arguments)]
878#[inline(never)]
879pub(crate) unsafe fn apply_spilled_tiled_box<D, S, Apply>(
880 dst_ptr: *mut D,
881 dst_base: isize,
882 src_ptr: *const S,
883 src_base: isize,
884 tiles: &SpilledTiles,
885 box_dims: &[usize],
886 apply: &mut Apply,
887) where
888 D: Copy,
889 S: Copy,
890 Apply: FnMut(&mut D, S),
891{
892 let rank = box_dims.len();
893 // One axis list for the current tile and one cursor for the whole walk,
894 // however many tiles it visits.
895 // INVARIANT: `box_dims` is `tiles.dims` or a sub-box of it, so
896 // `rank == tiles.rank < MAX_MOVING_AXES`.
897 let mut tile_axes = [EMPTY_AXIS; MAX_MOVING_AXES];
898 let tile = &mut tile_axes[..rank];
899 for (axis, slot) in tile.iter_mut().enumerate() {
900 slot.dst = tiles.dst[axis];
901 slot.src = tiles.src[axis];
902 }
903 let mut cursor = [0usize; MAX_MOVING_AXES];
904 let index = &mut cursor[..rank];
905 let mut origins = [0usize; MAX_MOVING_AXES];
906 let origin = &mut origins[..rank];
907 let mut dst_tile = dst_base;
908 let mut src_tile = src_base;
909 loop {
910 #[cfg(test)]
911 crate::threading::record_tile_box();
912 let mut count = 1usize;
913 for axis in 0..rank {
914 let dim = tiles.blocks[axis].min(box_dims[axis] - origin[axis]);
915 tile[axis].dim = dim;
916 count *= dim;
917 }
918 // SAFETY: the tile is a sub-box of `box_dims` at a reachable origin, so
919 // the caller's contract covers every logical index of the tile.
920 unsafe {
921 apply_spilled_range_with(
922 dst_ptr, dst_tile, src_ptr, src_tile, tile, 0, count, index, apply,
923 );
924 }
925 // The column-major odometer of [`apply_tiled_box`], over slices.
926 let mut axis = 0;
927 loop {
928 if axis == rank {
929 return;
930 }
931 let next = origin[axis] + tiles.blocks[axis];
932 if next < box_dims[axis] {
933 origin[axis] = next;
934 dst_tile += tiles.blocks[axis] as isize * tiles.dst[axis];
935 src_tile += tiles.blocks[axis] as isize * tiles.src[axis];
936 break;
937 }
938 dst_tile -= origin[axis] as isize * tiles.dst[axis];
939 src_tile -= origin[axis] as isize * tiles.src[axis];
940 origin[axis] = 0;
941 axis += 1;
942 }
943 }
944}
945
946/// Serial replay of a fused pair layout over borrowed raw views.
947///
948/// The destination layout need not be injective: runs are replayed in order,
949/// so accumulating callers such as [`axpy_raw`] keep their sequential
950/// semantics. Parallel replay goes through `copy_plan::replay_fused`, which
951/// the plans and the `replay_*_raw` entries call only with a destination
952/// proven injective or a serial token.
953pub(crate) fn apply_fused_pair<D, S, Apply>(
954 dst: &mut RawStridedMut<'_, D>,
955 src: &RawStridedRef<'_, S>,
956 layout: &FusedPairLayout,
957 mut apply: Apply,
958) where
959 D: Copy,
960 S: Copy,
961 Apply: FnMut(&mut D, S),
962{
963 let total = fused_total(layout);
964 if total == 0 {
965 return;
966 }
967 let src_ptr = src.data().as_ptr();
968 let src_base = src.offset();
969 let dst_base = dst.offset();
970 let dst_ptr = dst.data_mut().as_mut_ptr();
971 // SAFETY: `RawStridedRef`/`RawStridedMut` guarantee (by `new`, or by the
972 // caller of `new_unchecked`) that every offset reachable from their offset
973 // through their dims/strides lies inside their data. Callers pass a layout
974 // fused from exactly those dims/strides, so every logical index in
975 // `0..total` maps to in-bounds source and destination slots. The shared
976 // and exclusive borrows cannot overlap, and this is the only writer.
977 unsafe {
978 apply_fused_range(
979 dst_ptr, dst_base, src_ptr, src_base, layout, 0, total, &mut apply,
980 );
981 }
982}
983
984/// Serial replay of a spilled fused axis list over borrowed raw views.
985///
986/// Kept out of line and separate from [`apply_fused_pair`] so that the inline
987/// entry points keep the code shape they had before high-rank fusion existed:
988/// fused ranks above [`RAW_FUSED_RANK_LIMIT`] are the rare case, and inlining
989/// this second carry loop into them measurably slowed the inline path (extra
990/// register pressure in a loop that runs once per short run).
991#[inline(never)]
992pub(crate) fn apply_spilled_pair<D, S, Apply>(
993 dst: &mut RawStridedMut<'_, D>,
994 src: &RawStridedRef<'_, S>,
995 axes: &[FusedAxis],
996 mut apply: Apply,
997) where
998 D: Copy,
999 S: Copy,
1000 Apply: FnMut(&mut D, S),
1001{
1002 let total = spilled_total(axes);
1003 if total == 0 {
1004 return;
1005 }
1006 let src_ptr = src.data().as_ptr();
1007 let src_base = src.offset();
1008 let dst_base = dst.offset();
1009 let dst_ptr = dst.data_mut().as_mut_ptr();
1010 // SAFETY: same contract as `apply_fused_pair`, for the axis list fused from
1011 // the same dims/strides.
1012 unsafe {
1013 apply_spilled_range(
1014 dst_ptr, dst_base, src_ptr, src_base, axes, 0, total, &mut apply,
1015 );
1016 }
1017}
1018
1019/// Serial replay of a route on the calling thread: the four whole-box walks of
1020/// the parallel replay's serial branches, one sequential pass through `apply`.
1021///
1022/// [`crate::copy_plan::replay_fused`] sends a serial token here, and so does
1023/// [`replay_map_raw_serial`] with its `FnMut`, so both walk the same leaves in
1024/// the same order. No arm needs `Send` or `Sync`: nothing crosses a thread.
1025///
1026/// # Safety
1027///
1028/// The [`crate::copy_plan::replay_fused`] contract for `route` at these bases,
1029/// with a serial token: every logical index maps to in-bounds slots of both
1030/// allocations, the product of the extents does not overflow, the tiles (when
1031/// present) are the route builder's own and the destination is injective over
1032/// a tiled route, and the destination does not overlap the source.
1033pub(crate) unsafe fn replay_route_serial<D, S, Apply>(
1034 dst_ptr: *mut D,
1035 dst_base: isize,
1036 src_ptr: *const S,
1037 src_base: isize,
1038 route: Route<'_>,
1039 apply: &mut Apply,
1040) where
1041 D: Copy,
1042 S: Copy,
1043 Apply: FnMut(&mut D, S),
1044{
1045 // SAFETY: forwarded caller contract. Inline tiles address exactly the
1046 // slots of their layout; spilled tiles hold their own axes. One
1047 // sequential walk updates a repeated slot once per logical index, in
1048 // order, so an untiled route needs no injectivity.
1049 unsafe {
1050 match route {
1051 Route::Inline {
1052 layout,
1053 tiles: None,
1054 } => apply_fused_range(
1055 dst_ptr,
1056 dst_base,
1057 src_ptr,
1058 src_base,
1059 layout,
1060 0,
1061 fused_total(layout),
1062 apply,
1063 ),
1064 Route::Inline {
1065 tiles: Some(tiles), ..
1066 } => apply_tiled_box(
1067 dst_ptr,
1068 dst_base,
1069 src_ptr,
1070 src_base,
1071 &tiles.layout,
1072 &tiles.blocks,
1073 apply,
1074 ),
1075 Route::Spilled { axes, tiles: None } => apply_spilled_range(
1076 dst_ptr,
1077 dst_base,
1078 src_ptr,
1079 src_base,
1080 axes,
1081 0,
1082 spilled_total(axes),
1083 apply,
1084 ),
1085 Route::Spilled {
1086 tiles: Some(tiles), ..
1087 } => apply_spilled_tiled_box(
1088 dst_ptr,
1089 dst_base,
1090 src_ptr,
1091 src_base,
1092 tiles,
1093 tiles.dims(),
1094 apply,
1095 ),
1096 }
1097 }
1098}
1099
1100/// Replay logical indices `start..start + len` of a fused pair layout, in
1101/// column-major order of the fused axes (axis 0 fastest).
1102///
1103/// The start coordinate is decoded once; runs along axis 0 then advance the
1104/// outer coordinates incrementally, so no per-element range checks or
1105/// coordinate rebuilds remain in the hot loop.
1106///
1107/// # Safety
1108///
1109/// - `start + len` must not exceed [`fused_total`] of `layout`.
1110/// - For every logical index `i` in the range, `dst_base` plus the fused
1111/// destination offset of `i` must be an in-bounds, writable slot of the
1112/// allocation behind `dst_ptr`, and likewise `src_base` plus the source
1113/// offset must be an in-bounds, readable slot behind `src_ptr`.
1114/// - No other thread may access the destination slots of this range while it
1115/// runs, and the source slots must not be written concurrently. Destination
1116/// and source slots must not overlap.
1117// Range leaf: both bases, the layout, the range and the closure, called once per worker
1118// range.
1119#[allow(clippy::too_many_arguments)]
1120pub(crate) unsafe fn apply_fused_range<D, S, Apply>(
1121 dst_ptr: *mut D,
1122 dst_base: isize,
1123 src_ptr: *const S,
1124 src_base: isize,
1125 layout: &FusedPairLayout,
1126 start: usize,
1127 len: usize,
1128 apply: &mut Apply,
1129) where
1130 D: Copy,
1131 S: Copy,
1132 Apply: FnMut(&mut D, S),
1133{
1134 if len == 0 {
1135 return;
1136 }
1137 let rank = layout.rank;
1138 let inner_len = layout.dims[0];
1139 let inner_dst = layout.dst_strides[0];
1140 let inner_src = layout.src_strides[0];
1141
1142 // Decode the start coordinate once per range. `dst_offset`/`src_offset`
1143 // track the offset of the current run start (outer coordinates plus the
1144 // inner coordinate `inner_start`); every value is a reachable offset.
1145 let mut index = [0usize; RAW_FUSED_RANK_LIMIT];
1146 let mut rest = start;
1147 let mut dst_outer = dst_base;
1148 let mut src_outer = src_base;
1149 // The axis indexes `index`, `layout.dims` and both stride tables at once.
1150 #[allow(clippy::needless_range_loop)]
1151 for axis in 0..rank {
1152 let dim = layout.dims[axis];
1153 index[axis] = rest % dim;
1154 rest /= dim;
1155 if axis > 0 {
1156 dst_outer += index[axis] as isize * layout.dst_strides[axis];
1157 src_outer += index[axis] as isize * layout.src_strides[axis];
1158 }
1159 }
1160 let mut inner_start = index[0];
1161 let mut remaining = len;
1162 loop {
1163 let run = (inner_len - inner_start).min(remaining);
1164 let dst_run = dst_outer + inner_start as isize * inner_dst;
1165 let src_run = src_outer + inner_start as isize * inner_src;
1166 // SAFETY: the run covers logical indices inside the caller's range, so
1167 // by this function's contract every slot touched below is in-bounds,
1168 // exclusively owned by this call (destination) and unaliased.
1169 unsafe {
1170 apply_run(
1171 dst_ptr, dst_run, inner_dst, src_ptr, src_run, inner_src, run, apply,
1172 )
1173 };
1174 remaining -= run;
1175 if remaining == 0 {
1176 return;
1177 }
1178 inner_start = 0;
1179 // Advance an axis only when another position along it follows, and
1180 // rewind it from its last position, so every intermediate base is a
1181 // reachable offset of a validated layout (issue #243 follow-up): a
1182 // layout ending within one stride of `isize::MAX` must not overflow.
1183 // `remaining > 0` guarantees a following run exists, so the loop
1184 // always finds an axis to advance before running out of rank.
1185 let mut axis = 1;
1186 while axis < rank {
1187 if index[axis] + 1 < layout.dims[axis] {
1188 index[axis] += 1;
1189 dst_outer += layout.dst_strides[axis];
1190 src_outer += layout.src_strides[axis];
1191 break;
1192 }
1193 let last = (layout.dims[axis] - 1) as isize;
1194 dst_outer -= last * layout.dst_strides[axis];
1195 src_outer -= last * layout.src_strides[axis];
1196 index[axis] = 0;
1197 axis += 1;
1198 }
1199 }
1200}
1201
1202/// Replay logical indices `start..start + len` of a spilled fused axis list, in
1203/// column-major order of the axes (axis 0 fastest).
1204///
1205/// The carry loop is the one [`apply_fused_range`] uses, over interleaved axes
1206/// with its carry state in a stack array of [`MAX_MOVING_AXES`]: nothing is
1207/// allocated and no per-element coordinate decode happens.
1208///
1209/// # Safety
1210///
1211/// The [`apply_fused_range`] contract holds for `axes`, which hold at most
1212/// [`MAX_MOVING_AXES`] entries (every caller passes fused or compacted axes of
1213/// a checked count; a longer list panics before any access).
1214///
1215/// Kept out of line: inlining this second carry loop into the inline replay
1216/// measurably slows that one down.
1217// Same shape as `apply_fused_range` for the spilled layout, per worker range.
1218#[allow(clippy::too_many_arguments)]
1219#[inline(never)]
1220pub(crate) unsafe fn apply_spilled_range<D, S, Apply>(
1221 dst_ptr: *mut D,
1222 dst_base: isize,
1223 src_ptr: *const S,
1224 src_base: isize,
1225 axes: &[FusedAxis],
1226 start: usize,
1227 len: usize,
1228 apply: &mut Apply,
1229) where
1230 D: Copy,
1231 S: Copy,
1232 Apply: FnMut(&mut D, S),
1233{
1234 if len == 0 {
1235 return;
1236 }
1237 let mut cursor = [0usize; MAX_MOVING_AXES];
1238 // INVARIANT: fused and compacted axes have extents of at least 2 and a
1239 // checked product, so `axes.len() < MAX_MOVING_AXES`.
1240 let index = &mut cursor[..axes.len()];
1241 // SAFETY: forwarded caller contract; `index` is the rank-sized cursor.
1242 unsafe {
1243 apply_spilled_range_with(
1244 dst_ptr, dst_base, src_ptr, src_base, axes, start, len, index, apply,
1245 )
1246 }
1247}
1248
1249/// [`apply_spilled_range`] with the caller's rank-sized coordinate buffer, so
1250/// that the tile walk keeps one cursor for all its tiles.
1251///
1252/// # Safety
1253///
1254/// The [`apply_spilled_range`] contract, and `index.len()` at least
1255/// `axes.len()`.
1256#[allow(clippy::too_many_arguments)]
1257unsafe fn apply_spilled_range_with<D, S, Apply>(
1258 dst_ptr: *mut D,
1259 dst_base: isize,
1260 src_ptr: *const S,
1261 src_base: isize,
1262 axes: &[FusedAxis],
1263 start: usize,
1264 len: usize,
1265 index: &mut [usize],
1266 apply: &mut Apply,
1267) where
1268 D: Copy,
1269 S: Copy,
1270 Apply: FnMut(&mut D, S),
1271{
1272 if len == 0 {
1273 return;
1274 }
1275 let rank = axes.len();
1276 debug_assert!(index.len() >= rank);
1277 let inner_len = axes[0].dim;
1278 let inner_dst = axes[0].dst;
1279 let inner_src = axes[0].src;
1280
1281 let mut rest = start;
1282 let mut dst_outer = dst_base;
1283 let mut src_outer = src_base;
1284 for axis in 0..rank {
1285 let dim = axes[axis].dim;
1286 index[axis] = rest % dim;
1287 rest /= dim;
1288 if axis > 0 {
1289 dst_outer += index[axis] as isize * axes[axis].dst;
1290 src_outer += index[axis] as isize * axes[axis].src;
1291 }
1292 }
1293 let mut inner_start = index[0];
1294 let mut remaining = len;
1295 loop {
1296 let run = (inner_len - inner_start).min(remaining);
1297 let dst_run = dst_outer + inner_start as isize * inner_dst;
1298 let src_run = src_outer + inner_start as isize * inner_src;
1299 // SAFETY: the run covers logical indices inside the caller's range, so
1300 // by the caller's contract every slot touched below is in-bounds,
1301 // exclusively owned by this call (destination) and unaliased.
1302 unsafe {
1303 apply_run(
1304 dst_ptr, dst_run, inner_dst, src_ptr, src_run, inner_src, run, apply,
1305 )
1306 };
1307 remaining -= run;
1308 if remaining == 0 {
1309 return;
1310 }
1311 inner_start = 0;
1312 // Same incremental carry as the inline replay: offsets only ever hold
1313 // reachable positions, and `remaining > 0` guarantees an axis advances.
1314 let mut axis = 1;
1315 while axis < rank {
1316 if index[axis] + 1 < axes[axis].dim {
1317 index[axis] += 1;
1318 dst_outer += axes[axis].dst;
1319 src_outer += axes[axis].src;
1320 break;
1321 }
1322 let last = (axes[axis].dim - 1) as isize;
1323 dst_outer -= last * axes[axis].dst;
1324 src_outer -= last * axes[axis].src;
1325 index[axis] = 0;
1326 axis += 1;
1327 }
1328 }
1329}
1330
1331/// One run along the fused inner axis.
1332///
1333/// # Safety
1334///
1335/// Every `dst_offset + k * dst_stride` and `src_offset + k * src_stride` for
1336/// `k < len` must be an in-bounds slot as described in [`apply_fused_range`],
1337/// with exclusive access to the destination slots.
1338// Run leaf: both base/offset/stride triples, the length and the closure, per run.
1339#[allow(clippy::too_many_arguments)]
1340#[inline(always)]
1341unsafe fn apply_run<D, S, Apply>(
1342 dst_ptr: *mut D,
1343 dst_offset: isize,
1344 dst_stride: isize,
1345 src_ptr: *const S,
1346 src_offset: isize,
1347 src_stride: isize,
1348 len: usize,
1349 apply: &mut Apply,
1350) where
1351 D: Copy,
1352 S: Copy,
1353 Apply: FnMut(&mut D, S),
1354{
1355 if dst_stride == 1 {
1356 // SAFETY: a unit destination stride makes the run `len` consecutive
1357 // in-bounds slots starting at `dst_offset`, exclusively owned here.
1358 let dst_run = unsafe { core::slice::from_raw_parts_mut(dst_ptr.offset(dst_offset), len) };
1359 if src_stride == 1 {
1360 // A `copy_nonoverlapping` per run is not used for plain copies:
1361 // it measured slower than this element loop for short runs
1362 // (one `memcpy` call each) and for long cache-resident copies.
1363 // SAFETY: `len` consecutive in-bounds source slots, which the
1364 // exclusive destination run cannot overlap.
1365 let src_run = unsafe { core::slice::from_raw_parts(src_ptr.offset(src_offset), len) };
1366 for (dst, &value) in dst_run.iter_mut().zip(src_run) {
1367 apply(dst, value);
1368 }
1369 return;
1370 }
1371 if src_stride == -1 {
1372 // INVARIANT: the range walks never pass an empty run, and both
1373 // strides are nonzero, so the validated reach `len - 1` fits
1374 // `isize`; casting `len` itself would wrap for a run of
1375 // `isize::MAX + 1` elements. (A `saturating_sub` here measurably
1376 // slowed short unit-stride runs by changing the code layout of
1377 // the whole inlined walk.)
1378 let last = (len - 1) as isize;
1379 // SAFETY: the run reads `src_offset - (len - 1) ..= src_offset`,
1380 // all in-bounds; the lowest one is the run's last source slot.
1381 let src_run =
1382 unsafe { core::slice::from_raw_parts(src_ptr.offset(src_offset - last), len) };
1383 for (dst, &value) in dst_run.iter_mut().zip(src_run.iter().rev()) {
1384 apply(dst, value);
1385 }
1386 return;
1387 }
1388 // SAFETY: the run start is an in-bounds source slot.
1389 let src_start = unsafe { src_ptr.offset(src_offset) };
1390 for (position, dst) in dst_run.iter_mut().enumerate() {
1391 // SAFETY: `position < len`, so this is a run source slot.
1392 let value = unsafe { *src_start.offset(position as isize * src_stride) };
1393 apply(dst, value);
1394 }
1395 return;
1396 }
1397 // SAFETY: the run start is an in-bounds slot of each allocation.
1398 let dst_start = unsafe { dst_ptr.offset(dst_offset) };
1399 let src_start = unsafe { src_ptr.offset(src_offset) };
1400 // The bound stays `usize`: a checked broadcast run may hold more than
1401 // `isize::MAX` elements, and `len as isize` would wrap to an empty loop.
1402 for position in 0..len {
1403 // INVARIANT: a nonzero stride bounds the run by its validated reach,
1404 // so `position` fits `isize` exactly; a longer run is possible only
1405 // along a zero stride, where the wrapped cast is multiplied by zero.
1406 let position = position as isize;
1407 // SAFETY: `position < len`, so both are slots of this run.
1408 unsafe {
1409 let value = *src_start.offset(position * src_stride);
1410 apply(&mut *dst_start.offset(position * dst_stride), value);
1411 }
1412 }
1413}
1414
1415fn ensure_same_dims(dst: &[usize], src: &[usize]) -> Result<()> {
1416 if dst != src {
1417 return Err(crate::StridedError::ShapeMismatch(
1418 dst.to_vec(),
1419 src.to_vec(),
1420 ));
1421 }
1422 // Reject an element count beyond usize (a huge stride-0 broadcast)
1423 // instead of replaying it.
1424 crate::kernel::total_len(dst)?;
1425 Ok(())
1426}
1427
1428/// `dest = scale * src` over borrowed raw strided layouts.
1429///
1430/// # Errors
1431///
1432/// Returns [`crate::StridedError::ShapeMismatch`] when `dest` and `src` do
1433/// not describe the same extents, or [`crate::StridedError::OffsetOverflow`]
1434/// when the element count does not fit `usize`. Nothing is written on error.
1435pub fn copy_scale_raw<T>(
1436 dest: &mut RawStridedMut<'_, T>,
1437 src: &RawStridedRef<'_, T>,
1438 scale: T,
1439) -> Result<()>
1440where
1441 T: Copy + Mul<T, Output = T> + ElementOpApply + Send + Sync,
1442{
1443 ensure_same_dims(dest.dims(), src.dims())?;
1444 match fuse_pair_traversal(dest.dims(), dest.strides(), src.strides()) {
1445 PairTraversal::Inline(layout) => {
1446 apply_fused_pair(dest, src, &layout, |dst: &mut T, value: T| {
1447 *dst = scale * value
1448 })
1449 }
1450 PairTraversal::Spilled(axes) => {
1451 apply_spilled_pair(dest, src, &axes, |dst: &mut T, value: T| {
1452 *dst = scale * value
1453 })
1454 }
1455 }
1456 Ok(())
1457}
1458
1459/// `dest = scale * conj(src)` over borrowed raw strided layouts.
1460///
1461/// # Errors
1462///
1463/// Returns [`crate::StridedError::ShapeMismatch`] when `dest` and `src` do
1464/// not describe the same extents, or [`crate::StridedError::OffsetOverflow`]
1465/// when the element count does not fit `usize`. Nothing is written on error.
1466pub fn copy_scale_conj_raw<T>(
1467 dest: &mut RawStridedMut<'_, T>,
1468 src: &RawStridedRef<'_, T>,
1469 scale: T,
1470) -> Result<()>
1471where
1472 T: Copy + Mul<T, Output = T> + ElementOpApply + Send + Sync,
1473{
1474 ensure_same_dims(dest.dims(), src.dims())?;
1475 match fuse_pair_traversal(dest.dims(), dest.strides(), src.strides()) {
1476 PairTraversal::Inline(layout) => {
1477 apply_fused_pair(dest, src, &layout, |dst: &mut T, value: T| {
1478 *dst = scale * value.conj()
1479 })
1480 }
1481 PairTraversal::Spilled(axes) => {
1482 apply_spilled_pair(dest, src, &axes, |dst: &mut T, value: T| {
1483 *dst = scale * value.conj()
1484 })
1485 }
1486 }
1487 Ok(())
1488}
1489
1490/// `dest = alpha * src + dest` over borrowed raw strided layouts.
1491///
1492/// # Errors
1493///
1494/// Returns [`crate::StridedError::ShapeMismatch`] when `dest` and `src` do
1495/// not describe the same extents, or [`crate::StridedError::OffsetOverflow`]
1496/// when the element count does not fit `usize`. Nothing is written on error.
1497pub fn axpy_raw<T>(
1498 dest: &mut RawStridedMut<'_, T>,
1499 src: &RawStridedRef<'_, T>,
1500 alpha: T,
1501) -> Result<()>
1502where
1503 T: Copy + Add<T, Output = T> + Mul<T, Output = T> + ElementOpApply + Send + Sync,
1504{
1505 ensure_same_dims(dest.dims(), src.dims())?;
1506 match fuse_pair_traversal(dest.dims(), dest.strides(), src.strides()) {
1507 PairTraversal::Inline(layout) => {
1508 apply_fused_pair(dest, src, &layout, |dst: &mut T, value: T| {
1509 *dst = *dst + alpha * value
1510 })
1511 }
1512 PairTraversal::Spilled(axes) => {
1513 apply_spilled_pair(dest, src, &axes, |dst: &mut T, value: T| {
1514 *dst = *dst + alpha * value
1515 })
1516 }
1517 }
1518 Ok(())
1519}
1520
1521/// `dest = alpha * conj(src) + dest` over borrowed raw strided layouts.
1522///
1523/// # Errors
1524///
1525/// Returns [`crate::StridedError::ShapeMismatch`] when `dest` and `src` do
1526/// not describe the same extents, or [`crate::StridedError::OffsetOverflow`]
1527/// when the element count does not fit `usize`. Nothing is written on error.
1528pub fn axpy_conj_raw<T>(
1529 dest: &mut RawStridedMut<'_, T>,
1530 src: &RawStridedRef<'_, T>,
1531 alpha: T,
1532) -> Result<()>
1533where
1534 T: Copy + Add<T, Output = T> + Mul<T, Output = T> + ElementOpApply + Send + Sync,
1535{
1536 ensure_same_dims(dest.dims(), src.dims())?;
1537 match fuse_pair_traversal(dest.dims(), dest.strides(), src.strides()) {
1538 PairTraversal::Inline(layout) => {
1539 apply_fused_pair(dest, src, &layout, |dst: &mut T, value: T| {
1540 *dst = *dst + alpha * value.conj()
1541 })
1542 }
1543 PairTraversal::Spilled(axes) => {
1544 apply_spilled_pair(dest, src, &axes, |dst: &mut T, value: T| {
1545 *dst = *dst + alpha * value.conj()
1546 })
1547 }
1548 }
1549 Ok(())
1550}
1551
1552/// The checked route of the given axes of two views: the shared front of
1553/// every `replay_*_raw` entry, parallel and serial.
1554///
1555/// The element count is checked before anything is built. The unfused
1556/// traversal keeps every given extent, and the replay totals (`fused_total`,
1557/// `replay_spilled_raw`) take an unchecked product, so the zero-first count
1558/// of `kernel::total_len` has to keep an empty layout whose nonzero prefix
1559/// overflows, such as `[usize::MAX, 2, 0]`, away from them. An empty layout
1560/// returns before `f` runs.
1561///
1562/// `f` receives the route, the element count and, when the route came out
1563/// tiled, whether the destination was proven injective; the tiles are dropped
1564/// unless it was.
1565///
1566/// The slices are the views' own metadata, borrowed apart from the views so
1567/// that `f` can take the destination mutably.
1568fn with_checked_route<D, S>(
1569 dims: &[usize],
1570 dst_strides: &[isize],
1571 src_dims: &[usize],
1572 src_strides: &[isize],
1573 f: impl FnOnce(Route<'_>, usize, Option<bool>),
1574) -> Result<()> {
1575 ensure_same_dims(dims, src_dims)?;
1576 let total = crate::kernel::total_len(dims)?;
1577 if total == 0 {
1578 return Ok(());
1579 }
1580 with_given_route::<D, S, _>(dims, dst_strides, src_strides, |route| {
1581 let mut route = route;
1582 let mut proven = None;
1583 if route.is_tiled() {
1584 let holds = crate::layout_check::is_injective_layout_without_alloc(dims, dst_strides);
1585 proven = Some(holds);
1586 if !holds {
1587 route = route.untiled();
1588 }
1589 }
1590 f(route, total, proven)
1591 });
1592 Ok(())
1593}
1594
1595/// Checked replay of the given axes of two views: the shared body of the
1596/// parallel `replay_*_raw` entries.
1597fn replay_given<D, S, Apply>(
1598 dest: &mut RawStridedMut<'_, D>,
1599 src: &RawStridedRef<'_, S>,
1600 apply: Apply,
1601 exec: Exec<'_>,
1602) -> Result<()>
1603where
1604 D: Copy + Send + Sync,
1605 S: Copy + Send + Sync,
1606 Apply: Fn(&mut D, S) + Sync,
1607{
1608 let (dims, dst_strides) = (dest.dims(), dest.strides());
1609 let injective = || crate::layout_check::is_injective_layout_without_alloc(dims, dst_strides);
1610 with_checked_route::<D, S>(
1611 dims,
1612 dst_strides,
1613 src.dims(),
1614 src.strides(),
1615 |route, total, proven| {
1616 let exec = if route.is_tiled() {
1617 // The tiled tree gates every node on the caller's token itself; the
1618 // flat width rule would cap it at the width of one flat dispatch.
1619 exec
1620 } else {
1621 let exec = crate::cost::for_len(exec, KernelClass::Copy, total);
1622 if !exec.is_serial() && !proven.unwrap_or_else(injective) {
1623 // A destination not proven injective replays as one sequential
1624 // column-major walk, which is also its defined semantics; the
1625 // budget-one token cannot be widened again by the replay's own
1626 // width rule.
1627 exec.limit(NonZeroUsize::MIN)
1628 } else {
1629 exec
1630 }
1631 };
1632 // SAFETY: the route is built from exactly the views' dims and strides
1633 // (`ensure_same_dims` proved the dims agree); compaction drops only
1634 // extent-1 axes, whose coordinate is always 0, so the reachable
1635 // offsets equal the views' validated set, and the original metadata
1636 // still drives bounds, shape and injectivity. The views' bounds proofs
1637 // therefore cover every replayed offset; `total_len` checked the
1638 // nonzero product; the route's tiles are the decision for its own
1639 // axes, and tiles or a non-serial `exec` are left only for a
1640 // destination proven injective; the exclusive and shared borrows
1641 // cannot overlap.
1642 unsafe {
1643 crate::copy_plan::replay_fused(
1644 dest,
1645 src,
1646 route,
1647 apply,
1648 KernelClass::Copy.ns_per_element(),
1649 exec,
1650 )
1651 };
1652 },
1653 )
1654}
1655
1656/// `dest = src`, replaying the axes of the two views exactly as given.
1657///
1658/// The views carry already-fused dims: no axis is reordered, dropped or
1659/// merged, and no plan is compiled. Axis 0 is the inner run of the
1660/// column-major walk; when the shared cache-block model finds tiles that change
1661/// the visit order and can reuse a cache line, the walk goes tile by tile
1662/// instead, each tile column-major over the given axes. Bounds were validated when the views were built
1663/// ([`RawStridedRef::new`], [`RawStridedMut::new`]).
1664///
1665/// On a successful call the replay itself (validation, traversal and
1666/// dispatch) allocates nothing at any rank on a serial token, or on a pooled
1667/// token whose replay is not tiled. A pooled tiled replay with more than
1668/// [`RAW_FUSED_RANK_LIMIT`] moving axes may allocate the splitter's metadata.
1669/// The wide route uses a rank-bounded amount of stack. An error may allocate
1670/// its payload.
1671///
1672/// The width comes from the repository rule on `exec`. A parallel or tiled
1673/// replay runs only on a destination proven injective without allocating; any
1674/// other destination is replayed serially in column-major order of the given
1675/// axes.
1676///
1677/// # Errors
1678///
1679/// [`StridedError::ShapeMismatch`](crate::StridedError::ShapeMismatch) when the
1680/// two views have different dims, and
1681/// [`StridedError::OffsetOverflow`](crate::StridedError::OffsetOverflow) when the
1682/// element count overflows `usize`; both before any write.
1683///
1684/// # Examples
1685///
1686/// Copy the outer band `1..3` of a stored `2 x 3` block into a transposed
1687/// destination:
1688///
1689/// ```rust
1690/// use strided_basic::{replay_copy_raw, Exec, RawStridedMut, RawStridedRef};
1691///
1692/// let stored = [0.0f64, 1.0, 2.0, 3.0, 4.0, 5.0]; // column-major 2 x 3
1693/// let band = [2usize, 2];
1694/// let src = RawStridedRef::new(&stored, &band, &[1, 2], 2).unwrap();
1695/// let mut out = [0.0f64; 4];
1696/// let mut dst = RawStridedMut::new(&mut out, &band, &[2, 1], 0).unwrap();
1697/// replay_copy_raw(&mut dst, &src, Exec::serial()).unwrap();
1698/// assert_eq!(out, [2.0, 4.0, 3.0, 5.0]);
1699/// ```
1700pub fn replay_copy_raw<T>(
1701 dest: &mut RawStridedMut<'_, T>,
1702 src: &RawStridedRef<'_, T>,
1703 exec: Exec<'_>,
1704) -> Result<()>
1705where
1706 T: Copy + Send + Sync,
1707{
1708 replay_given(dest, src, |dst: &mut T, value: T| *dst = value, exec)
1709}
1710
1711/// [`replay_copy_raw`] into a potentially uninitialized destination.
1712///
1713/// On success every reachable destination element is initialized and no
1714/// other slot is written. The destination is never read.
1715///
1716/// # Errors
1717///
1718/// As [`replay_copy_raw`].
1719///
1720/// # Examples
1721///
1722/// ```rust
1723/// use core::mem::MaybeUninit;
1724/// use strided_basic::{replay_copy_raw_uninit, Exec, RawStridedMut, RawStridedRef};
1725///
1726/// let src = [1.0f64, 2.0, 3.0];
1727/// let mut storage = [MaybeUninit::<f64>::uninit(); 3];
1728/// let mut dst = RawStridedMut::new(&mut storage, &[3], &[1], 0).unwrap();
1729/// let source = RawStridedRef::new(&src, &[3], &[-1], 2).unwrap();
1730/// replay_copy_raw_uninit(&mut dst, &source, Exec::serial()).unwrap();
1731/// drop(dst);
1732/// // SAFETY: every reachable destination slot was initialized above.
1733/// let values: Vec<f64> = storage.iter().map(|v| unsafe { v.assume_init() }).collect();
1734/// assert_eq!(values, [3.0, 2.0, 1.0]);
1735/// ```
1736pub fn replay_copy_raw_uninit<T>(
1737 dest: &mut RawStridedMut<'_, MaybeUninit<T>>,
1738 src: &RawStridedRef<'_, T>,
1739 exec: Exec<'_>,
1740) -> Result<()>
1741where
1742 T: Copy + Send + Sync,
1743{
1744 replay_given(
1745 dest,
1746 src,
1747 |dst: &mut MaybeUninit<T>, value: T| {
1748 dst.write(value);
1749 },
1750 exec,
1751 )
1752}
1753
1754/// `f(&mut dest[i], src[i])` for every element, replaying the axes of the two
1755/// views exactly as given.
1756///
1757/// Traversal, width and errors are those of [`replay_copy_raw`], and so is the
1758/// allocation guarantee, which covers the replay only: allocations made by `f`
1759/// are its own. `f` runs once per logical element with exactly its arithmetic,
1760/// so an accumulate such as `|d, s| *d += s` is exact. The order in which
1761/// elements are visited is unspecified, and on a parallel replay `f` runs
1762/// concurrently on disjoint slots: the result is defined only for an `f` whose
1763/// effect depends on the supplied slot values alone. On a destination that is
1764/// not proven injective, the elements are visited serially in column-major
1765/// order of the given axes.
1766/// For an `FnMut`, or for element types that are not `Send + Sync`, use
1767/// [`replay_map_raw_serial`].
1768///
1769/// # Errors
1770///
1771/// As [`replay_copy_raw`].
1772///
1773/// # Examples
1774///
1775/// ```rust
1776/// use strided_basic::{replay_map_raw, Exec, RawStridedMut, RawStridedRef};
1777///
1778/// let src = [1.0f64, 2.0, 3.0, 4.0];
1779/// let mut acc = [10.0f64, 20.0, 30.0, 40.0];
1780/// let source = RawStridedRef::new(&src, &[2, 2], &[2, 1], 0).unwrap();
1781/// let mut dst = RawStridedMut::new(&mut acc, &[2, 2], &[1, 2], 0).unwrap();
1782/// replay_map_raw(&mut dst, &source, |d, s| *d += s, Exec::serial()).unwrap();
1783/// assert_eq!(acc, [11.0, 23.0, 32.0, 44.0]);
1784/// ```
1785pub fn replay_map_raw<D, S, F>(
1786 dest: &mut RawStridedMut<'_, D>,
1787 src: &RawStridedRef<'_, S>,
1788 f: F,
1789 exec: Exec<'_>,
1790) -> Result<()>
1791where
1792 D: Copy + Send + Sync,
1793 S: Copy + Send + Sync,
1794 F: Fn(&mut D, S) + Send + Sync,
1795{
1796 replay_given(dest, src, f, exec)
1797}
1798
1799/// [`replay_map_raw`] on the calling thread, for callbacks and elements that
1800/// are not `Send + Sync`: `f(&mut dest[i], src[i])` for every element, with
1801/// `f` an `FnMut`.
1802///
1803/// The traversal, the errors and the visit order are those of
1804/// [`replay_map_raw`] under [`Exec::serial()`]: both walk the same route
1805/// through the same leaves. `f` is called exactly once per logical element,
1806/// sequentially on the calling thread, column-major over the given axes with
1807/// axis 0 fastest. The one exception is a destination proven injective whose
1808/// layout the shared cache-block model tiles: the walk then goes tile by tile,
1809/// the tile grid and each tile column-major. A destination that is not proven
1810/// injective is always walked column-major, so an accumulating `f` sees a
1811/// repeated slot once per logical index, in that order.
1812///
1813/// A successful call allocates nothing at any rank; allocations made by `f`
1814/// are its own. The wide route uses a rank-bounded amount of the caller's
1815/// stack. An error may allocate its payload.
1816///
1817/// With `D = MaybeUninit<T>` the destination is initialized only if `f`
1818/// writes its slot on every call: a successful return guarantees that `f` ran
1819/// exactly once for every reachable destination element, not that it wrote.
1820///
1821/// # Errors
1822///
1823/// As [`replay_copy_raw`], before `f` first runs.
1824///
1825/// # Examples
1826///
1827/// A generic copy whose element type need not be `Send` or `Sync`, counting
1828/// its calls through a captured `Rc`:
1829///
1830/// ```rust
1831/// use std::cell::Cell;
1832/// use std::rc::Rc;
1833/// use strided_basic::{replay_map_raw_serial, RawStridedMut, RawStridedRef, Result};
1834///
1835/// fn copy_generic<T: Copy>(dst: &mut RawStridedMut<'_, T>, src: &RawStridedRef<'_, T>) -> Result<()> {
1836/// replay_map_raw_serial(dst, src, |d, s| *d = s)
1837/// }
1838///
1839/// let stored = [0.0f64, 1.0, 2.0, 3.0, 4.0, 5.0]; // column-major 2 x 3
1840/// let src = RawStridedRef::new(&stored, &[2, 3], &[1, 2], 0).unwrap();
1841/// let mut out = [0.0f64; 6];
1842/// let mut dst = RawStridedMut::new(&mut out, &[2, 3], &[3, 1], 0).unwrap();
1843/// copy_generic(&mut dst, &src).unwrap();
1844///
1845/// let calls = Rc::new(Cell::new(0));
1846/// let counter = Rc::clone(&calls);
1847/// replay_map_raw_serial(&mut dst, &src, |d, s| {
1848/// counter.set(counter.get() + 1);
1849/// *d += s;
1850/// })
1851/// .unwrap();
1852/// drop(dst);
1853/// assert_eq!(calls.get(), 6);
1854/// assert_eq!(out, [0.0, 4.0, 8.0, 2.0, 6.0, 10.0]);
1855/// ```
1856///
1857/// An uninitialized destination, filled by a closure that writes every slot:
1858///
1859/// ```rust
1860/// use core::mem::MaybeUninit;
1861/// use strided_basic::{replay_map_raw_serial, RawStridedMut, RawStridedRef};
1862///
1863/// let src = [1.0f64, 2.0, 3.0];
1864/// let mut storage = [MaybeUninit::<f64>::uninit(); 3];
1865/// let mut dst = RawStridedMut::new(&mut storage, &[3], &[1], 0).unwrap();
1866/// let source = RawStridedRef::new(&src, &[3], &[-1], 2).unwrap();
1867/// replay_map_raw_serial(&mut dst, &source, |d: &mut MaybeUninit<f64>, s| {
1868/// d.write(s);
1869/// })
1870/// .unwrap();
1871/// drop(dst);
1872/// // SAFETY: the closure writes its slot on every call, and the successful
1873/// // replay called it once for every reachable destination slot, which are
1874/// // all three slots of `storage`.
1875/// let values: Vec<f64> = storage.iter().map(|v| unsafe { v.assume_init() }).collect();
1876/// assert_eq!(values, [3.0, 2.0, 1.0]);
1877/// ```
1878pub fn replay_map_raw_serial<D, S, F>(
1879 dest: &mut RawStridedMut<'_, D>,
1880 src: &RawStridedRef<'_, S>,
1881 mut f: F,
1882) -> Result<()>
1883where
1884 D: Copy,
1885 S: Copy,
1886 F: FnMut(&mut D, S),
1887{
1888 let (dims, dst_strides) = (dest.dims(), dest.strides());
1889 with_checked_route::<D, S>(
1890 dims,
1891 dst_strides,
1892 src.dims(),
1893 src.strides(),
1894 |route, _, _| {
1895 let src_ptr = src.data().as_ptr();
1896 let src_base = src.offset();
1897 let dst_base = dest.offset();
1898 let dst_ptr = dest.data_mut().as_mut_ptr();
1899 // SAFETY: the route is the one `replay_given` builds from exactly the
1900 // views' dims and strides, so the views' bounds proofs cover every
1901 // replayed offset and `total_len` checked the nonzero product (see
1902 // there). `with_checked_route` kept tiles only for a destination
1903 // proven injective, and an untiled walk is one sequential pass; the
1904 // exclusive and shared borrows cannot overlap.
1905 unsafe { replay_route_serial(dst_ptr, dst_base, src_ptr, src_base, route, &mut f) };
1906 },
1907 )
1908}
1909
1910/// `dest[i] = f(src[i])` into a potentially uninitialized destination.
1911///
1912/// `f` cannot read the destination. On success every reachable destination
1913/// element is initialized and no other slot is written. The visit-order,
1914/// callback and allocation contract is that of [`replay_map_raw`].
1915///
1916/// # Errors
1917///
1918/// As [`replay_copy_raw`].
1919///
1920/// # Examples
1921///
1922/// ```rust
1923/// use core::mem::MaybeUninit;
1924/// use strided_basic::{replay_map_raw_uninit, Exec, RawStridedMut, RawStridedRef};
1925///
1926/// let src = [1i32, 2, 3];
1927/// let mut storage = [MaybeUninit::<f64>::uninit(); 3];
1928/// let mut dst = RawStridedMut::new(&mut storage, &[3], &[1], 0).unwrap();
1929/// let source = RawStridedRef::new(&src, &[3], &[1], 0).unwrap();
1930/// replay_map_raw_uninit(&mut dst, &source, |s| f64::from(s) * 0.5, Exec::serial()).unwrap();
1931/// drop(dst);
1932/// // SAFETY: every reachable destination slot was initialized above.
1933/// let values: Vec<f64> = storage.iter().map(|v| unsafe { v.assume_init() }).collect();
1934/// assert_eq!(values, [0.5, 1.0, 1.5]);
1935/// ```
1936pub fn replay_map_raw_uninit<D, S, F>(
1937 dest: &mut RawStridedMut<'_, MaybeUninit<D>>,
1938 src: &RawStridedRef<'_, S>,
1939 f: F,
1940 exec: Exec<'_>,
1941) -> Result<()>
1942where
1943 D: Copy + Send + Sync,
1944 S: Copy + Send + Sync,
1945 F: Fn(S) -> D + Send + Sync,
1946{
1947 replay_given(
1948 dest,
1949 src,
1950 move |dst: &mut MaybeUninit<D>, value: S| {
1951 dst.write(f(value));
1952 },
1953 exec,
1954 )
1955}
1956
1957/// `f(&mut dest[i], src[i])` after fusing the two layouts inside the call.
1958///
1959/// [`replay_map_raw`] replays the axes exactly as given, so a caller that holds
1960/// an unfused layout has to fuse it first and pays that pass per call. This
1961/// entry performs the same fusion [`copy_scale_raw`] does before choosing the
1962/// route, then replays with the caller's token; the small-block fusion cost is
1963/// therefore inside the crate, once, instead of at every call site.
1964///
1965/// The traversal, width, callback and allocation contracts are those of
1966/// [`replay_map_raw`]: the visit order is unspecified, and a successful call
1967/// allocates nothing at any rank on a serial token, or on a pooled token whose
1968/// replay is not tiled above [`RAW_FUSED_RANK_LIMIT`] moving axes. The fusion
1969/// itself holds its scratch on the stack, so it does not allocate either.
1970///
1971/// # Errors
1972///
1973/// As [`replay_map_raw`].
1974///
1975/// # Examples
1976///
1977/// ```rust
1978/// use strided_basic::{replay_map_raw_fused, Exec, RawStridedMut, RawStridedRef};
1979///
1980/// let src = [1.0f64, 2.0, 3.0, 4.0];
1981/// let mut acc = [10.0f64, 20.0, 30.0, 40.0];
1982/// let source = RawStridedRef::new(&src, &[2, 2], &[2, 1], 0).unwrap();
1983/// // The destination is transposed relative to the source; the fused entry
1984/// // fuses the two layouts before it walks them.
1985/// let mut dst = RawStridedMut::new(&mut acc, &[2, 2], &[1, 2], 0).unwrap();
1986/// replay_map_raw_fused(&mut dst, &source, |d, s| *d += s, Exec::serial()).unwrap();
1987/// assert_eq!(acc, [11.0, 23.0, 32.0, 44.0]);
1988/// ```
1989pub fn replay_map_raw_fused<D, S, F>(
1990 dest: &mut RawStridedMut<'_, D>,
1991 src: &RawStridedRef<'_, S>,
1992 f: F,
1993 exec: Exec<'_>,
1994) -> Result<()>
1995where
1996 D: Copy + Send + Sync,
1997 S: Copy + Send + Sync,
1998 F: Fn(&mut D, S) + Send + Sync,
1999{
2000 replay_fused_given(dest, src, f, exec)
2001}
2002
2003/// [`replay_map_raw_fused`] into a potentially uninitialized destination.
2004///
2005/// `f` cannot read the destination. On success every reachable destination
2006/// element is initialized and no other slot is written. The fused traversal,
2007/// callback and allocation contract is that of [`replay_map_raw_fused`].
2008///
2009/// # Errors
2010///
2011/// As [`replay_map_raw`].
2012///
2013/// # Examples
2014///
2015/// ```rust
2016/// use core::mem::MaybeUninit;
2017/// use strided_basic::{replay_map_raw_uninit_fused, Exec, RawStridedMut, RawStridedRef};
2018///
2019/// let src = [1i32, 2, 3];
2020/// let mut storage = [MaybeUninit::<f64>::uninit(); 3];
2021/// let mut dst = RawStridedMut::new(&mut storage, &[3], &[1], 0).unwrap();
2022/// let source = RawStridedRef::new(&src, &[3], &[1], 0).unwrap();
2023/// replay_map_raw_uninit_fused(&mut dst, &source, |s| f64::from(s) * 0.5, Exec::serial())
2024/// .unwrap();
2025/// drop(dst);
2026/// // SAFETY: every reachable destination slot was initialized above.
2027/// let values: Vec<f64> = storage.iter().map(|v| unsafe { v.assume_init() }).collect();
2028/// assert_eq!(values, [0.5, 1.0, 1.5]);
2029/// ```
2030pub fn replay_map_raw_uninit_fused<D, S, F>(
2031 dest: &mut RawStridedMut<'_, MaybeUninit<D>>,
2032 src: &RawStridedRef<'_, S>,
2033 f: F,
2034 exec: Exec<'_>,
2035) -> Result<()>
2036where
2037 D: Copy + Send + Sync,
2038 S: Copy + Send + Sync,
2039 F: Fn(S) -> D + Send + Sync,
2040{
2041 replay_fused_given(
2042 dest,
2043 src,
2044 move |dst: &mut MaybeUninit<D>, value: S| {
2045 dst.write(f(value));
2046 },
2047 exec,
2048 )
2049}
2050
2051/// Fuse the compacted moving axes of the pair on the stack, then replay them.
2052///
2053/// [`fuse_pair_traversal`] keeps a `Vec` for an original rank above
2054/// [`RAW_FUSED_RANK_LIMIT`]; this path compacts extent-1 axes first and holds
2055/// both the compacted and the fused axes in fixed arrays, so the fusion adds no
2056/// allocation at any rank. The element count is checked before the arrays are
2057/// indexed, which also bounds the moving-axis count by
2058/// [`MAX_MOVING_AXES`].
2059fn replay_fused_given<D, S, Apply>(
2060 dest: &mut RawStridedMut<'_, D>,
2061 src: &RawStridedRef<'_, S>,
2062 apply: Apply,
2063 exec: Exec<'_>,
2064) -> Result<()>
2065where
2066 D: Copy + Send + Sync,
2067 S: Copy + Send + Sync,
2068 Apply: Fn(&mut D, S) + Send + Sync,
2069{
2070 ensure_same_dims(dest.dims(), src.dims())?;
2071 if crate::kernel::total_len(dest.dims())? == 0 {
2072 return Ok(());
2073 }
2074
2075 let mut dims = [1usize; MAX_MOVING_AXES];
2076 let mut dst_strides = [0isize; MAX_MOVING_AXES];
2077 let mut src_strides = [0isize; MAX_MOVING_AXES];
2078 let mut moving = 0;
2079 for ((&dim, &dst), &src_stride) in dest.dims().iter().zip(dest.strides()).zip(src.strides()) {
2080 if dim == 1 {
2081 continue;
2082 }
2083 // INVARIANT: the checked nonzero count gives `2^moving <= total`, so
2084 // `moving < MAX_MOVING_AXES`.
2085 dims[moving] = dim;
2086 dst_strides[moving] = dst;
2087 src_strides[moving] = src_stride;
2088 moving += 1;
2089 }
2090
2091 let mut fused = [EMPTY_AXIS; MAX_MOVING_AXES];
2092 let rank = fuse_axes(
2093 &mut fused[..moving.max(1)],
2094 &dims[..moving],
2095 &dst_strides[..moving],
2096 &src_strides[..moving],
2097 );
2098 let mut fused_dims = [1usize; MAX_MOVING_AXES];
2099 let mut fused_dst = [0isize; MAX_MOVING_AXES];
2100 let mut fused_src = [0isize; MAX_MOVING_AXES];
2101 for (slot, axis) in fused[..rank].iter().enumerate() {
2102 fused_dims[slot] = axis.dim;
2103 fused_dst[slot] = axis.dst;
2104 fused_src[slot] = axis.src;
2105 }
2106
2107 let dst_offset = dest.offset();
2108 let src_offset = src.offset();
2109 // SAFETY: fusion only reorders and merges the compacted moving axes, so the
2110 // set of reachable offsets is unchanged and the views' constructors already
2111 // proved that set inside their data.
2112 let mut dest = unsafe {
2113 RawStridedMut::new_unchecked(
2114 dest.data_mut(),
2115 &fused_dims[..rank],
2116 &fused_dst[..rank],
2117 dst_offset,
2118 )
2119 };
2120 let src = unsafe {
2121 RawStridedRef::new_unchecked(
2122 src.data(),
2123 &fused_dims[..rank],
2124 &fused_src[..rank],
2125 src_offset,
2126 )
2127 };
2128 replay_given(&mut dest, &src, apply, exec)
2129}
2130
2131#[cfg(test)]
2132#[path = "raw_ops/tests/tests.rs"]
2133mod tests;
2134
2135#[cfg(test)]
2136#[path = "raw_ops/tests/replay_tests.rs"]
2137mod replay_tests;
2138
2139#[cfg(test)]
2140#[path = "raw_ops/tests/tiled_tests.rs"]
2141mod tiled_tests;