strided_basic/copy_plan.rs
1//! Prepared (compile-once, execute-many) copy plans over raw strided layouts.
2//!
3//! [`copy_scale_raw`](crate::copy_scale_raw) and friends rebuild the fused
4//! loop nest on every call; for prepared-replay consumers that issue many
5//! small copies with a fixed layout, that per-call planning dominates
6//! (see issue #139). [`CopyPlan`] splits the work: [`CopyPlan::compile`]
7//! validates the layout pair and builds the fused traversal once,
8//! [`CopyPlan::execute`]/[`CopyPlan::execute_scale`]/[`CopyPlan::execute_conj`]
9//! replay it with no heap allocation for fused ranks at most
10//! [`RAW_FUSED_RANK_LIMIT`](crate::RAW_FUSED_RANK_LIMIT). The only per-execute
11//! planning is the cache-block selection for the element type, which runs the
12//! shared block model on layouts of at least two non-unit axes. A layout is
13//! walked tile by tile when the tiles change the visit order and can reuse a
14//! cache line across the runs they regroup.
15
16use core::{
17 marker::PhantomData,
18 mem::{size_of, MaybeUninit},
19 ops::{Add, Mul},
20};
21
22use num_traits::{One, Zero};
23
24use crate::cost::KernelClass;
25use crate::raw_ops::{
26 apply_fused_range, apply_spilled_range, apply_spilled_tiled_box, apply_tiled_box,
27 fuse_pair_traversal, fused_total, pair_tiles, replay_route_serial, FusedAxis, FusedPairLayout,
28 PairTiles, PairTraversal, Route, SpilledTiles,
29};
30use crate::{ElementOpApply, Exec, RawStridedMut, RawStridedRef, Result, StridedError};
31use strided_perm::HostClass;
32
33// Same pattern as map_view.rs / outer_product.rs: inline storage in both
34// feature configurations. Only `compile` touches these; `execute*` never
35// allocates for them. (A spilled fused layout replays from stack arrays bounded
36// by its moving-axis count: see `raw_ops::MAX_MOVING_AXES`.)
37type AxisVec<T> = crate::inline::InlineVec<T>;
38
39pub(crate) trait OverwriteWriter<T> {
40 fn dims(&self) -> &[usize];
41 fn strides(&self) -> &[isize];
42 fn offset(&self) -> isize;
43 /// # Safety
44 /// The caller must use the pointer only for the validated allocation and
45 /// logical layout represented by this writer.
46 unsafe fn data_ptr(&mut self) -> *mut T;
47 /// # Safety
48 /// The offset must be an in-bounds logical destination proven by layout.
49 unsafe fn write_at(&mut self, offset: isize, value: T);
50}
51
52pub(crate) trait ReadModifyWrite<T>: OverwriteWriter<T> {
53 /// # Safety
54 /// The offset must be an in-bounds initialized slot covered by the
55 /// traversal's copy and disjointness proof.
56 unsafe fn add_at<F>(&mut self, offset: isize, value: T, combine: F)
57 where
58 F: FnOnce(T, T) -> T;
59}
60
61impl<'a, T> OverwriteWriter<T> for RawStridedMut<'a, T> {
62 fn dims(&self) -> &[usize] {
63 self.dims()
64 }
65 fn strides(&self) -> &[isize] {
66 self.strides()
67 }
68 fn offset(&self) -> isize {
69 self.offset()
70 }
71 unsafe fn data_ptr(&mut self) -> *mut T {
72 self.data_mut().as_mut_ptr()
73 }
74 unsafe fn write_at(&mut self, offset: isize, value: T) {
75 // SAFETY: the prepared layout validates every logical destination.
76 unsafe { self.data_mut().as_mut_ptr().offset(offset).write(value) }
77 }
78}
79
80impl<'a, T> ReadModifyWrite<T> for RawStridedMut<'a, T>
81where
82 T: Add<Output = T>,
83{
84 #[inline(always)]
85 unsafe fn add_at<F>(&mut self, offset: isize, value: T, combine: F)
86 where
87 F: FnOnce(T, T) -> T,
88 {
89 // SAFETY: the copy or initialized caller proves this logical slot.
90 unsafe {
91 let ptr = self.data_mut().as_mut_ptr().offset(offset);
92 ptr.write(combine(ptr.read(), value));
93 }
94 }
95}
96
97impl<'a, T> OverwriteWriter<T> for RawStridedMut<'a, MaybeUninit<T>> {
98 fn dims(&self) -> &[usize] {
99 self.dims()
100 }
101 fn strides(&self) -> &[isize] {
102 self.strides()
103 }
104 fn offset(&self) -> isize {
105 self.offset()
106 }
107 unsafe fn data_ptr(&mut self) -> *mut T {
108 self.data_mut().as_mut_ptr().cast()
109 }
110 unsafe fn write_at(&mut self, offset: isize, value: T) {
111 // SAFETY: the prepared layout validates every logical destination.
112 unsafe {
113 self.data_mut()
114 .as_mut_ptr()
115 .offset(offset)
116 .write(MaybeUninit::new(value))
117 }
118 }
119}
120
121pub(crate) struct InitializedRawDest<'a, T> {
122 ptr: *mut T,
123 extent: usize,
124 dims: &'a [usize],
125 strides: &'a [isize],
126 offset: isize,
127 _marker: PhantomData<&'a mut [MaybeUninit<T>]>,
128}
129
130impl<'a, T> OverwriteWriter<T> for InitializedRawDest<'a, T> {
131 fn dims(&self) -> &[usize] {
132 self.dims
133 }
134 fn strides(&self) -> &[isize] {
135 self.strides
136 }
137 fn offset(&self) -> isize {
138 self.offset
139 }
140 unsafe fn data_ptr(&mut self) -> *mut T {
141 self.ptr
142 }
143 unsafe fn write_at(&mut self, offset: isize, value: T) {
144 debug_assert!(offset >= 0 && (offset as usize) < self.extent);
145 // SAFETY: the copy proof and extent check cover this logical slot.
146 unsafe { self.ptr.offset(offset).write(value) }
147 }
148}
149
150impl<'a, T> ReadModifyWrite<T> for InitializedRawDest<'a, T>
151where
152 T: Add<Output = T>,
153{
154 #[inline(always)]
155 unsafe fn add_at<F>(&mut self, offset: isize, value: T, combine: F)
156 where
157 F: FnOnce(T, T) -> T,
158 {
159 debug_assert!(offset >= 0 && (offset as usize) < self.extent);
160 // SAFETY: the copy proof and extent check cover this logical slot.
161 unsafe {
162 let ptr = self.ptr.offset(offset);
163 ptr.write(combine(ptr.read(), value));
164 }
165 }
166}
167
168/// A compiled copy traversal for one `(dims, dst_strides, src_strides)`
169/// layout pair.
170///
171/// `compile` proves the layout facts once (rank agreement, extent overflow,
172/// destination injectivity) and fuses/orders the loop nest; each `execute*`
173/// call then only re-checks the per-call facts (that the supplied views carry
174/// exactly the compiled layout) and selects the cache blocks for its element
175/// type before replaying the prepared loops. The order in which elements are
176/// visited is unspecified.
177///
178/// Overlapping `src`/`dest` memory is not supported, matching the rest of the
179/// crate.
180///
181/// Ranks above [`RAW_FUSED_RANK_LIMIT`](crate::RAW_FUSED_RANK_LIMIT) are supported by the same fused
182/// traversal, which then stores its axes in one rank-bounded allocation.
183///
184/// # Example
185///
186/// ```rust
187/// use strided_basic::{CopyPlan, Exec, RawStridedMut, RawStridedRef};
188///
189/// let dims = [2usize, 3];
190/// let src_strides = [3isize, 1];
191/// let dst_strides = [1isize, 2]; // transposed destination
192/// let plan = CopyPlan::compile(&dims, &dst_strides, &src_strides).unwrap();
193///
194/// let src = [0.0f64, 1.0, 2.0, 10.0, 11.0, 12.0];
195/// let mut dst = [0.0f64; 6];
196/// let src_ref = RawStridedRef::new(&src, &dims, &src_strides, 0).unwrap();
197/// let mut dst_mut = RawStridedMut::new(&mut dst, &dims, &dst_strides, 0).unwrap();
198/// plan.execute(&mut dst_mut, &src_ref, Exec::serial()).unwrap();
199/// assert_eq!(dst, [0.0, 10.0, 1.0, 11.0, 2.0, 12.0]);
200/// ```
201#[derive(Clone, Debug, Default)]
202pub struct CopyPlan {
203 dims: AxisVec<usize>,
204 dst_strides: AxisVec<isize>,
205 src_strides: AxisVec<isize>,
206 fused: PairTraversal,
207 /// Elements each side spans ([`span_elements`]), so that the working set in
208 /// bytes is `dst_span * size_of::<D>() + src_span * size_of::<S>()` at replay,
209 /// where the element types are known.
210 dst_span: usize,
211 src_span: usize,
212}
213
214impl CopyPlan {
215 /// `None` when the fused traversal is stored in the rank-bounded spill.
216 #[inline]
217 pub(crate) fn fused_layout(&self) -> Option<&FusedPairLayout> {
218 self.fused.inline()
219 }
220
221 /// The cache tiles [`Self::execute`] replays this plan's inline layout with
222 /// for destination element `D` and source element `S`, or `None` when it
223 /// keeps the column-major walk or the layout spilled: the one decision a
224 /// caller replaying the plan's inline traversal itself must reuse.
225 #[inline]
226 pub(crate) fn inline_tiles<D, S>(&self) -> Option<PairTiles> {
227 self.fused.inline().and_then(pair_tiles::<D, S>)
228 }
229
230 /// Whether [`Self::tiles`] can return tiles for any element types; known
231 /// at compile time ([`PairTraversal::may_tile`]).
232 #[inline]
233 pub(crate) fn may_tile(&self) -> bool {
234 self.fused.may_tile()
235 }
236
237 /// Copy into uninitialized storage, then lend the initialized destination to `f`.
238 ///
239 /// [`Self::execute_uninit`] initializes every reachable logical destination
240 /// element before `f` runs, so the [`InitializedRawDest`] receipt handed to `f`
241 /// may read and overwrite exactly those offsets. Slots outside the plan's
242 /// reachable set are not written by that copy and it makes no claim about
243 /// them: a caller that handed in a `MaybeUninit` array still owns those slots,
244 /// so they keep whatever initialization the caller left. With
245 /// `CopyPlan::compile(&[2], &[2], &[1])` the offset-1 hole keeps the caller's
246 /// value (measured `[7.0, 99.0, 8.0]` for `src = [7, 8]`) rather than
247 /// becoming uninitialized. That is why the receipt exposes
248 /// `write_at`/`add_at` (copy_plan.rs:138, :150) instead of a typed slice: their
249 /// contracts require an offset proven by this plan's layout. The receipt borrows
250 /// the destination for `f`'s lifetime, so a read-modify-write consumer (the
251 /// gather and scatter update replay in gather_plan.rs) sees the copied operand
252 /// once and cannot alias the source.
253 ///
254 /// # Errors
255 ///
256 /// Returns the [`Self::execute_uninit`] errors (`PlanLayoutMismatch`, before any
257 /// write); `f` runs only on success.
258 pub(crate) fn execute_uninit_then<'a, T, R>(
259 &self,
260 dest: &'a mut RawStridedMut<'a, MaybeUninit<T>>,
261 src: &RawStridedRef<'_, T>,
262 mut exec: Exec<'_>,
263 f: impl for<'b, 'e> FnOnce(InitializedRawDest<'b, T>, Exec<'e>) -> R,
264 ) -> Result<R>
265 where
266 T: Copy + Send + Sync,
267 {
268 self.execute_uninit(dest, src, exec.reborrow())?;
269 let data = dest.data_mut();
270 let receipt = InitializedRawDest {
271 ptr: data.as_mut_ptr().cast(),
272 extent: data.len(),
273 dims: dest.dims(),
274 strides: dest.strides(),
275 offset: dest.offset(),
276 _marker: PhantomData,
277 };
278 Ok(f(receipt, exec))
279 }
280
281 /// Compile a copy plan for the given layout pair.
282 ///
283 /// Performs the layout validation and traversal construction
284 /// (fuse + order) once.
285 ///
286 /// # Errors
287 ///
288 /// Returns [`StridedError::StrideLengthMismatch`] when `dims`,
289 /// `dst_strides`, and `src_strides` do not all have the same length,
290 /// [`StridedError::OffsetOverflow`] when the total element count does not
291 /// fit `usize`, and [`StridedError::NonInjectiveOutputLayout`] when the
292 /// destination layout cannot be proven injective (aliasing elements, or a
293 /// span the check cannot represent).
294 pub fn compile(dims: &[usize], dst_strides: &[isize], src_strides: &[isize]) -> Result<Self> {
295 if dims.len() != dst_strides.len() || dims.len() != src_strides.len() {
296 return Err(StridedError::StrideLengthMismatch);
297 }
298 // A zero-sized layout has zero elements even when its other extents
299 // overflow; only a nonempty overflowing count is rejected.
300 crate::kernel::total_len(dims)?;
301 if !crate::layout_check::is_injective_layout(dims, dst_strides) {
302 return Err(StridedError::NonInjectiveOutputLayout);
303 }
304 let fused = fuse_pair_traversal(dims, dst_strides, src_strides);
305 Ok(Self {
306 dims: dims.into(),
307 dst_strides: dst_strides.into(),
308 src_strides: src_strides.into(),
309 fused,
310 dst_span: span_elements(dims, dst_strides),
311 src_span: span_elements(dims, src_strides),
312 })
313 }
314
315 /// Serial rate this plan prices itself at on host class `host`: the `Copy`
316 /// row while the plan is one contiguous run, the row plus one cache line per
317 /// run of its walk otherwise, the class's beyond-L2 line past its L2 cache
318 /// (strided-rs#364). [`Self::replay`] asks it for [`HostClass::detect`]; the
319 /// class is a parameter so that the tests can pin it.
320 ///
321 /// The element size is the one fact `compile` cannot know, so the footprint
322 /// in bytes is formed here from the compiled span; nothing is probed.
323 fn ns_per_element_on<D, S>(&self, host: HostClass) -> f64 {
324 plan_ns_per_element::<D, S>(host, &self.fused, self.dst_span, self.src_span)
325 }
326
327 /// Check the per-call facts: the supplied views must carry exactly the
328 /// compiled layout. Buffer bounds against that layout were already proven
329 /// by [`RawStridedRef::new`]/[`RawStridedMut::new`] (or asserted by the
330 /// caller of the `new_unchecked` constructors), so layout equality is the
331 /// complete precondition for the pointer-based fused replay below.
332 fn check_call<D, S>(
333 &self,
334 dest: &RawStridedMut<'_, D>,
335 src: &RawStridedRef<'_, S>,
336 ) -> Result<()> {
337 check_layout_pair(&self.dims, &self.dst_strides, &self.src_strides, dest, src)
338 }
339
340 /// Check the per-call facts, then replay the compiled traversal, priced for
341 /// this host's class.
342 fn replay<D, S, Apply>(
343 &self,
344 dest: &mut RawStridedMut<'_, D>,
345 src: &RawStridedRef<'_, S>,
346 apply: Apply,
347 exec: Exec<'_>,
348 ) -> Result<()>
349 where
350 D: Copy + Send + Sync,
351 S: Copy + Send + Sync,
352 Apply: Fn(&mut D, S) + Sync,
353 {
354 self.replay_on(HostClass::detect(), dest, src, apply, exec)
355 }
356
357 /// [`Self::replay`] priced for host class `host`: every scheduling decision
358 /// of the replay asks at [`Self::ns_per_element_on`] of that class. Split out
359 /// so that a test can pin the class and observe the rate reach the replay on
360 /// every host (strided-rs#364).
361 fn replay_on<D, S, Apply>(
362 &self,
363 host: HostClass,
364 dest: &mut RawStridedMut<'_, D>,
365 src: &RawStridedRef<'_, S>,
366 apply: Apply,
367 exec: Exec<'_>,
368 ) -> Result<()>
369 where
370 D: Copy + Send + Sync,
371 S: Copy + Send + Sync,
372 Apply: Fn(&mut D, S) + Sync,
373 {
374 self.check_call(dest, src)?;
375 let ns_per_element = self.ns_per_element_on::<D, S>(host);
376 self.fused.with_route::<D, S, _>(|route| {
377 // SAFETY: `check_call` proved both views carry exactly the compiled
378 // layout, and `fused` is the fusion of that layout (only `compile`
379 // and `Default`, the rank-zero layout, build it). `compile` checked
380 // the element count and proved the destination injective, so the
381 // tiles of `fused` may be replayed.
382 unsafe { replay_fused(dest, src, route, apply, ns_per_element, exec) }
383 });
384 Ok(())
385 }
386
387 /// `dest = src` into a potentially uninitialized destination.
388 ///
389 /// On success every reachable logical destination element is initialized.
390 /// Non-reachable holes in the backing allocation are not written.
391 ///
392 /// # Errors
393 ///
394 /// Returns [`StridedError::PlanLayoutMismatch`] when the views do not
395 /// carry the compiled layout, before any write.
396 pub fn execute_uninit<T>(
397 &self,
398 dest: &mut RawStridedMut<'_, MaybeUninit<T>>,
399 src: &RawStridedRef<'_, T>,
400 exec: Exec<'_>,
401 ) -> Result<()>
402 where
403 T: Copy + Send + Sync,
404 {
405 self.replay(
406 dest,
407 src,
408 |dst: &mut MaybeUninit<T>, value: T| {
409 dst.write(value);
410 },
411 exec,
412 )
413 }
414
415 /// `dest = src`. Allocation-free for fused ranks at most
416 /// [`RAW_FUSED_RANK_LIMIT`](crate::RAW_FUSED_RANK_LIMIT).
417 ///
418 /// # Errors
419 ///
420 /// Returns [`StridedError::PlanLayoutMismatch`] when the views do not
421 /// carry the compiled layout, before any write.
422 pub fn execute<T>(
423 &self,
424 dest: &mut RawStridedMut<'_, T>,
425 src: &RawStridedRef<'_, T>,
426 exec: Exec<'_>,
427 ) -> Result<()>
428 where
429 T: Copy + Send + Sync,
430 {
431 self.replay(dest, src, |dst: &mut T, value: T| *dst = value, exec)
432 }
433
434 /// `dest = scale * src`. Allocation-free for fused ranks at most
435 /// [`RAW_FUSED_RANK_LIMIT`](crate::RAW_FUSED_RANK_LIMIT).
436 ///
437 /// # Errors
438 ///
439 /// Returns [`StridedError::PlanLayoutMismatch`] when the views do not
440 /// carry the compiled layout, before any write.
441 pub fn execute_scale<T>(
442 &self,
443 dest: &mut RawStridedMut<'_, T>,
444 src: &RawStridedRef<'_, T>,
445 scale: T,
446 exec: Exec<'_>,
447 ) -> Result<()>
448 where
449 T: Copy + Mul<T, Output = T> + Send + Sync,
450 {
451 self.replay(
452 dest,
453 src,
454 |dst: &mut T, value: T| *dst = scale * value,
455 exec,
456 )
457 }
458
459 /// `dest = conj(src)`. Allocation-free for fused ranks at most
460 /// [`RAW_FUSED_RANK_LIMIT`](crate::RAW_FUSED_RANK_LIMIT).
461 ///
462 /// # Errors
463 ///
464 /// Returns [`StridedError::PlanLayoutMismatch`] when the views do not
465 /// carry the compiled layout, before any write.
466 pub fn execute_conj<T>(
467 &self,
468 dest: &mut RawStridedMut<'_, T>,
469 src: &RawStridedRef<'_, T>,
470 exec: Exec<'_>,
471 ) -> Result<()>
472 where
473 T: Copy + ElementOpApply + Send + Sync,
474 {
475 self.replay(dest, src, |dst: &mut T, value: T| *dst = value.conj(), exec)
476 }
477}
478
479/// Whether the replay walks `fused` as one unit-stride run on each side, the
480/// layout the `Copy` row is calibrated on, and the length of the unit-stride run
481/// its walk starts with.
482///
483/// A *run* is a stretch of the walk that advances by one element on both sides;
484/// a streamed contiguous copy is one run and keeps the row at every footprint, a
485/// reversed one (`-1` on a side) streams the same way, and a transposing walk
486/// takes one run of one element per visit. The run length is the
487/// `elements / segments` ratio of strided-rs#364's
488/// `segments * per_segment + elements * per_element_inside_segment`, read off the
489/// frozen fused layout, so it is a compile-time plan property and nothing is
490/// probed.
491///
492/// The question is about the walk the replay takes, not about a walk the layout
493/// would allow: both replays walk the fused axes in their stored order with axis 0
494/// fastest (`apply_fused_range`, `apply_spilled_range`), and the tiled replay only
495/// exists for two or more moving axes. So the strides, read in that order, must be
496/// the running products of the extents with one sign per operand. Fusion already
497/// merges every such pair, so in practice a one-run walk is a fused rank of one at
498/// unit stride; a dense *reversed* buffer of rank two or more is not one run here,
499/// because fusion sorts the axes by signed destination stride and walks
500/// `[-1, -512]` over `[512, 512]` with `-512` fastest (strided-rs#364 review).
501/// That walk's runs are one element long, and it is priced as the strided walk it
502/// is.
503fn walk_runs(fused: &PairTraversal) -> (usize, bool) {
504 /// `(leading run length, that run is the whole walk)`.
505 fn runs(axes: impl Iterator<Item = (usize, isize, isize)>) -> (usize, bool) {
506 let mut len = 1usize;
507 let mut signs = None;
508 for (dim, dst, src) in axes {
509 if dim == 1 {
510 continue;
511 }
512 // A direction flip ends the run too: the walk reverses there, so the
513 // next element is a new cache line even at a unit stride.
514 let axis_signs = (dst < 0, src < 0);
515 if dst.unsigned_abs() != len
516 || src.unsigned_abs() != len
517 || *signs.get_or_insert(axis_signs) != axis_signs
518 {
519 return (len, false);
520 }
521 len = len.saturating_mul(dim);
522 }
523 (len, true)
524 }
525 match fused {
526 PairTraversal::Inline(layout) => runs(inline_axes(layout)),
527 PairTraversal::Spilled(axes) => runs(spilled_axes(axes)),
528 }
529}
530
531// shortcut: the run length is the fused axes' untiled walk. The tiled replay of
532// strided-rs#422 cuts a box, so its runs can be shorter than the leading axis run
533// (an inner extent of 8 tiled to 6 and 2 halves the run length and so doubles the
534// per-run line charge). Upgrade when a tiled plan's in-L2 pricing is measured
535// against the model: derive the charge from `PairTraversal::with_route` then.
536
537/// The axes of a fused walk in replay order (axis 0 fastest) as
538/// `(extent, destination stride, source stride)`.
539fn inline_axes(layout: &FusedPairLayout) -> impl Iterator<Item = (usize, isize, isize)> + '_ {
540 (0..layout.rank).map(move |axis| {
541 (
542 layout.dims[axis],
543 layout.dst_strides[axis],
544 layout.src_strides[axis],
545 )
546 })
547}
548
549/// [`inline_axes`] for the spilled traversal.
550fn spilled_axes(axes: &[FusedAxis]) -> impl Iterator<Item = (usize, isize, isize)> + '_ {
551 axes.iter().map(|axis| (axis.dim, axis.dst, axis.src))
552}
553
554/// Serial rate a copy-shaped plan prices itself at on `host`, from the three
555/// facts `compile` froze in its fused layout and spans: whether the whole walk is
556/// one contiguous run, the length of its runs, and the working set in bytes.
557///
558/// [`CopyPlan`] and [`UpdatePlan`] both replay [`replay_fused`], so both ask their
559/// rate here (strided-rs#364).
560fn plan_ns_per_element<D, S>(
561 host: HostClass,
562 fused: &PairTraversal,
563 dst_span: usize,
564 src_span: usize,
565) -> f64 {
566 let (run_len, one_run) = walk_runs(fused);
567 if one_run {
568 return KernelClass::Copy.ns_per_element_of(host);
569 }
570 let bytes = dst_span
571 .saturating_mul(size_of::<D>())
572 .saturating_add(src_span.saturating_mul(size_of::<S>()));
573 crate::cost::copy_ns_per_element_for_plan(host, bytes, run_len)
574}
575
576/// Elements one side of a compiled layout spans: `1 + sum((dim - 1) * |stride|)`,
577/// the reach of the side from its base offset. Summed over the two sides it is
578/// the plan's working set in elements, saturating rather than wrapping because a
579/// stride is only bounded by `isize`.
580fn span_elements(dims: &[usize], strides: &[isize]) -> usize {
581 dims.iter()
582 .zip(strides)
583 .fold(1usize, |span, (&dim, &stride)| {
584 span.saturating_add(dim.saturating_sub(1).saturating_mul(stride.unsigned_abs()))
585 })
586}
587
588/// Verify that a pair of raw views carries exactly a compiled layout.
589///
590/// Shared by [`CopyPlan`] and [`UpdatePlan`], whose `compile` methods prove the
591/// layout facts once. Buffer bounds against that layout were already proven by
592/// [`RawStridedRef::new`]/[`RawStridedMut::new`] (or asserted by the caller of
593/// the `new_unchecked` constructors), so layout equality is the complete
594/// per-call precondition for the pointer-based fused replay.
595fn check_layout_pair<D, S>(
596 dims: &[usize],
597 dst_strides: &[isize],
598 src_strides: &[isize],
599 dest: &RawStridedMut<'_, D>,
600 src: &RawStridedRef<'_, S>,
601) -> Result<()> {
602 if dest.dims() != dims
603 || src.dims() != dims
604 || dest.strides() != dst_strides
605 || src.strides() != src_strides
606 {
607 return Err(StridedError::PlanLayoutMismatch);
608 }
609 Ok(())
610}
611
612/// A compiled read-modify-write traversal for one `(dims, dst_strides,
613/// src_strides)` layout pair.
614///
615/// [`execute`](Self::execute) computes `dest = alpha * f(src) + beta * dest` by
616/// replaying the same fused pair traversal as [`CopyPlan`]: `compile` proves
617/// the layout facts once (rank agreement, extent overflow, destination
618/// injectivity) and each call only re-checks that the supplied views carry the
619/// compiled layout before running monomorphized loops. Execute is
620/// allocation-free for fused ranks at most
621/// [`RAW_FUSED_RANK_LIMIT`](crate::RAW_FUSED_RANK_LIMIT), and the injective
622/// destination makes a large replay parallel-safe exactly as in [`CopyPlan`].
623///
624/// Overlapping `src`/`dest` memory is not supported, matching the rest of the
625/// crate.
626///
627/// # Example
628///
629/// ```rust
630/// use strided_basic::{Exec, RawStridedMut, RawStridedRef, UpdatePlan};
631///
632/// let dims = [2usize, 2];
633/// let dst_strides = [1isize, 2];
634/// let src_strides = [1isize, 2];
635/// let plan = UpdatePlan::compile(&dims, &dst_strides, &src_strides).unwrap();
636///
637/// let src = [1.0f64, 2.0, 3.0, 4.0];
638/// let mut dst = [10.0f64, 20.0, 30.0, 40.0];
639/// let src_ref = RawStridedRef::new(&src, &dims, &src_strides, 0).unwrap();
640/// let mut dst_mut = RawStridedMut::new(&mut dst, &dims, &dst_strides, 0).unwrap();
641/// // dst = 2 * src + 3 * dst
642/// plan.execute(&mut dst_mut, &src_ref, 2.0, 3.0, |x| x, Exec::serial()).unwrap();
643/// assert_eq!(dst, [32.0, 64.0, 96.0, 128.0]);
644/// ```
645#[derive(Clone, Debug)]
646pub struct UpdatePlan {
647 dims: AxisVec<usize>,
648 dst_strides: AxisVec<isize>,
649 src_strides: AxisVec<isize>,
650 fused: PairTraversal,
651 /// Working-set spans, as on [`CopyPlan`]: the footprint in bytes is formed at
652 /// replay, where the element types are known.
653 dst_span: usize,
654 src_span: usize,
655}
656
657impl UpdatePlan {
658 /// Compile an update plan for the given layout pair.
659 ///
660 /// Performs the same layout validation as [`CopyPlan::compile`].
661 ///
662 /// # Errors
663 ///
664 /// Returns [`StridedError::StrideLengthMismatch`] when `dims`,
665 /// `dst_strides`, and `src_strides` do not all have the same length,
666 /// [`StridedError::OffsetOverflow`] when the total element count does not
667 /// fit `usize`, and [`StridedError::NonInjectiveOutputLayout`] when the
668 /// destination layout cannot be proven injective: two logical indices name
669 /// one slot (so a parallel replay would write that slot once per index), or
670 /// the offset span cannot be represented, leaving injectivity undecided.
671 pub fn compile(dims: &[usize], dst_strides: &[isize], src_strides: &[isize]) -> Result<Self> {
672 if dims.len() != dst_strides.len() || dims.len() != src_strides.len() {
673 return Err(StridedError::StrideLengthMismatch);
674 }
675 crate::kernel::total_len(dims)?;
676 if !crate::layout_check::is_injective_layout(dims, dst_strides) {
677 return Err(StridedError::NonInjectiveOutputLayout);
678 }
679 let fused = fuse_pair_traversal(dims, dst_strides, src_strides);
680 Ok(Self {
681 dims: dims.into(),
682 dst_strides: dst_strides.into(),
683 src_strides: src_strides.into(),
684 fused,
685 dst_span: span_elements(dims, dst_strides),
686 src_span: span_elements(dims, src_strides),
687 })
688 }
689
690 /// Serial rate this plan prices itself at on host class `host`: the same
691 /// [`plan_ns_per_element`] as [`CopyPlan`], because both replay
692 /// [`replay_fused`] and a caller that paid the line per run on one would pay
693 /// it on the other (strided-rs#364).
694 fn ns_per_element_on<D, S>(&self, host: HostClass) -> f64 {
695 plan_ns_per_element::<D, S>(host, &self.fused, self.dst_span, self.src_span)
696 }
697
698 /// Check the per-call facts, then replay the compiled traversal, priced for
699 /// this host's class.
700 fn replay<D, S, Apply>(
701 &self,
702 dest: &mut RawStridedMut<'_, D>,
703 src: &RawStridedRef<'_, S>,
704 apply: Apply,
705 exec: Exec<'_>,
706 ) -> Result<()>
707 where
708 D: Copy + Send + Sync,
709 S: Copy + Send + Sync,
710 Apply: Fn(&mut D, S) + Sync,
711 {
712 self.replay_on(HostClass::detect(), dest, src, apply, exec)
713 }
714
715 /// [`Self::replay`] priced for host class `host`: split out for the same
716 /// reason as [`CopyPlan::replay_on`], so that a test can pin the class and see
717 /// the plan's rate reach the replay on every host (strided-rs#364).
718 fn replay_on<D, S, Apply>(
719 &self,
720 host: HostClass,
721 dest: &mut RawStridedMut<'_, D>,
722 src: &RawStridedRef<'_, S>,
723 apply: Apply,
724 exec: Exec<'_>,
725 ) -> Result<()>
726 where
727 D: Copy + Send + Sync,
728 S: Copy + Send + Sync,
729 Apply: Fn(&mut D, S) + Sync,
730 {
731 check_layout_pair(&self.dims, &self.dst_strides, &self.src_strides, dest, src)?;
732 let ns_per_element = self.ns_per_element_on::<D, S>(host);
733 self.fused.with_route::<D, S, _>(|route| {
734 // SAFETY: as in `CopyPlan::replay`: the views carry the compiled
735 // layout, `fused` is its fusion (built only by `compile`), and
736 // `compile` checked the count and destination injectivity.
737 unsafe { replay_fused(dest, src, route, apply, ns_per_element, exec) }
738 });
739 Ok(())
740 }
741
742 /// `dest = alpha * f(src) + beta * dest`.
743 ///
744 /// `f` is applied to the source element before scaling. When `beta` is
745 /// zero (`-0.0` included; `NaN` is not zero) the replay is write-only: the
746 /// old destination element is never read, so a NaN-filled or uninitialized
747 /// destination cannot contaminate the result, matching BLAS `beta = 0`
748 /// semantics. Otherwise the old destination element is read through the
749 /// destination layout. Allocation-free for fused ranks at most
750 /// [`RAW_FUSED_RANK_LIMIT`](crate::RAW_FUSED_RANK_LIMIT).
751 ///
752 /// `f` runs once per logical element. The order in which elements are
753 /// visited is unspecified, and on a parallel replay `f` runs concurrently
754 /// on disjoint slots: the result is defined only for an `f` whose effect
755 /// depends on the supplied value alone.
756 ///
757 /// # Errors
758 ///
759 /// [`StridedError::PlanLayoutMismatch`] when the supplied views do not
760 /// carry the compiled layout, before any write.
761 pub fn execute<T, F>(
762 &self,
763 dest: &mut RawStridedMut<'_, T>,
764 src: &RawStridedRef<'_, T>,
765 alpha: T,
766 beta: T,
767 f: F,
768 exec: Exec<'_>,
769 ) -> Result<()>
770 where
771 T: Copy + Send + Sync + Add<Output = T> + Mul<Output = T> + Zero + One + PartialEq,
772 F: Fn(T) -> T + Send + Sync,
773 {
774 if beta.is_zero() {
775 // Write-only: never form a read of the old destination.
776 if alpha.is_one() {
777 self.replay(dest, src, |dst: &mut T, value: T| *dst = f(value), exec)
778 } else {
779 self.replay(
780 dest,
781 src,
782 |dst: &mut T, value: T| *dst = alpha * f(value),
783 exec,
784 )
785 }
786 } else {
787 self.replay(
788 dest,
789 src,
790 |dst: &mut T, value: T| *dst = alpha * f(value) + beta * *dst,
791 exec,
792 )
793 }
794 }
795
796 /// `dest = alpha * f(src)` into a potentially uninitialized destination.
797 ///
798 /// This is [`execute`](Self::execute) with `beta = 0`: the destination is
799 /// never read. On success every reachable logical destination element is
800 /// initialized; non-reachable holes in the backing allocation are not
801 /// written. Allocation-free for fused ranks at most
802 /// [`RAW_FUSED_RANK_LIMIT`](crate::RAW_FUSED_RANK_LIMIT). The visit-order
803 /// and callback contract is that of [`execute`](Self::execute).
804 ///
805 /// # Errors
806 ///
807 /// [`StridedError::PlanLayoutMismatch`] when the supplied views do not
808 /// carry the compiled layout, before any write.
809 ///
810 /// # Examples
811 ///
812 /// ```rust
813 /// use core::mem::MaybeUninit;
814 /// use strided_basic::{Exec, RawStridedMut, RawStridedRef, UpdatePlan};
815 ///
816 /// let dims = [2usize, 2];
817 /// let strides = [1isize, 2];
818 /// let plan = UpdatePlan::compile(&dims, &strides, &strides).unwrap();
819 /// let src = [1.0f64, 2.0, 3.0, 4.0];
820 /// let mut storage = [MaybeUninit::<f64>::uninit(); 4];
821 /// let mut dst = RawStridedMut::new(&mut storage, &dims, &strides, 0).unwrap();
822 /// let source = RawStridedRef::new(&src, &dims, &strides, 0).unwrap();
823 /// // dst = 2 * src
824 /// plan.execute_uninit(&mut dst, &source, 2.0, |x| x, Exec::serial()).unwrap();
825 /// drop(dst);
826 /// // SAFETY: every reachable destination slot was initialized above.
827 /// let values: Vec<f64> = storage.iter().map(|v| unsafe { v.assume_init() }).collect();
828 /// assert_eq!(values, [2.0, 4.0, 6.0, 8.0]);
829 /// ```
830 pub fn execute_uninit<T, F>(
831 &self,
832 dest: &mut RawStridedMut<'_, MaybeUninit<T>>,
833 src: &RawStridedRef<'_, T>,
834 alpha: T,
835 f: F,
836 exec: Exec<'_>,
837 ) -> Result<()>
838 where
839 T: Copy + Send + Sync + Mul<Output = T> + One + PartialEq,
840 F: Fn(T) -> T + Send + Sync,
841 {
842 if alpha.is_one() {
843 self.replay(
844 dest,
845 src,
846 |dst: &mut MaybeUninit<T>, value: T| {
847 dst.write(f(value));
848 },
849 exec,
850 )
851 } else {
852 self.replay(
853 dest,
854 src,
855 |dst: &mut MaybeUninit<T>, value: T| {
856 dst.write(alpha * f(value));
857 },
858 exec,
859 )
860 }
861 }
862}
863
864/// Replay `route` over a pair of raw views, splitting it across the budget
865/// of `exec` when the repository threshold allows it.
866///
867/// A tiled route walks its cache tiles and splits the box with the dimension
868/// splitter (see [`replay_fused_raw`] and [`replay_spilled_tiled`]). An
869/// untiled one splits the logical index space `0..total`
870/// (column-major over the traversal axes) is split into contiguous worker
871/// ranges, which divides the outer axes and, when there are fewer outer
872/// positions than workers, also chunks long inner runs (for example a rank-1
873/// contiguous copy). A serial token walks the route through
874/// [`replay_route_serial`], the walk [`crate::replay_map_raw_serial`]
875/// shares.
876///
877/// # Safety
878///
879/// - `route` must replay exactly the logical index space of the two views:
880/// either their dims and strides fused by `fuse_pair_traversal`
881/// ([`PairTraversal::with_route`]), or given by them
882/// ([`crate::raw_ops::with_given_route`]). The views' own bounds proofs
883/// ([`RawStridedRef::new`], [`RawStridedMut::new`], or the caller of their
884/// `new_unchecked`) then make every replayed offset in-bounds.
885/// - The product of the route's extents must not overflow `usize` (a checked
886/// count, zero included).
887/// - The route's tiles, when present, must be the decision of the route
888/// builder for its own axes.
889/// - When the route is tiled or `exec` is not serial, the destination strides
890/// must be injective over the route.
891/// - The destination and source must not overlap.
892///
893/// `ns_per_element` is the serial rate the replay prices itself at; both plan
894/// types pass their own ([`CopyPlan::ns_per_element_on`],
895/// `UpdatePlan::ns_per_element_on`), because the pricing follows the traversal and
896/// not the entry. The plan-free `replay_*_raw` entries pass the rate of
897/// `KernelClass::Copy` ([`crate::cost::KernelClass::ns_per_element`]).
898pub(crate) unsafe fn replay_fused<D, S, Apply>(
899 dest: &mut RawStridedMut<'_, D>,
900 src: &RawStridedRef<'_, S>,
901 route: Route<'_>,
902 mut apply: Apply,
903 ns_per_element: f64,
904 exec: Exec<'_>,
905) where
906 D: Copy + Send + Sync,
907 S: Copy + Send + Sync,
908 Apply: Fn(&mut D, S) + Sync,
909{
910 let src_ptr = src.data().as_ptr();
911 let src_base = src.offset();
912 let dst_base = dest.offset();
913 let dst_ptr = dest.data_mut().as_mut_ptr();
914 if exec.is_serial() {
915 // SAFETY: forwarded caller contract, on a serial token.
916 unsafe {
917 replay_route_serial(dst_ptr, dst_base, src_ptr, src_base, route, &mut apply);
918 }
919 return;
920 }
921 // SAFETY: forwarded caller contract: every logical index of `route` maps
922 // to in-bounds slots of both views, injectivity holds whenever the replay
923 // is tiled or the token can fan out, and the borrows do not overlap. Inline
924 // tiles address exactly the slots of their layout, in the same column-major
925 // order.
926 unsafe {
927 match route {
928 Route::Inline { layout, tiles } => replay_fused_raw(
929 dst_ptr,
930 dst_base,
931 src_ptr,
932 src_base,
933 layout,
934 tiles,
935 apply,
936 ns_per_element,
937 exec,
938 ),
939 Route::Spilled {
940 tiles: Some(tiles), ..
941 } => replay_spilled_tiled(
942 dst_ptr,
943 dst_base,
944 src_ptr,
945 src_base,
946 tiles,
947 apply,
948 exec,
949 ns_per_element,
950 ),
951 Route::Spilled { axes, tiles: None } => replay_spilled_raw(
952 dst_ptr,
953 dst_base,
954 src_ptr,
955 src_base,
956 axes,
957 apply,
958 ns_per_element,
959 exec,
960 ),
961 }
962 }
963}
964
965/// Pointer-level fused replay shared by [`CopyPlan`], [`UpdatePlan`], the
966/// plan-free `replay_*_raw` entries and the dynamic slice plans, which replay
967/// a fused window layout at a runtime base offset.
968///
969/// Without `tiles`, splits `0..total` across the budget of `exec` when the
970/// repository threshold allows more than one slot, otherwise runs the serial
971/// kernel directly. With `tiles`, the box is walked tile by tile; a token on
972/// which one fork pays splits it with the dimension splitter, and every leaf
973/// walks its sub-box with the same tiles anchored at its origin.
974///
975/// # Safety
976///
977/// Every logical index of `layout`, mapped through its destination strides
978/// from `dst_base` and its source strides from `src_base`, must be an
979/// in-bounds slot of the destination and source allocations, and the product
980/// of its extents must not overflow `usize`. `tiles`, when `Some`, must be
981/// `pair_tiles::<D, S>(layout)`. When `tiles` is `Some` or `exec` is not
982/// serial, the destination strides must be injective over `layout`; an
983/// untiled serial replay updates a repeated slot once per logical index, in
984/// order. The destination must not overlap the source, and nothing else may
985/// access the destination slots during the call.
986#[allow(clippy::too_many_arguments)]
987pub(crate) unsafe fn replay_fused_raw<D, S, Apply>(
988 dst_ptr: *mut D,
989 dst_base: isize,
990 src_ptr: *const S,
991 src_base: isize,
992 layout: &FusedPairLayout,
993 tiles: Option<&PairTiles>,
994 mut apply: Apply,
995 ns_per_element: f64,
996 exec: Exec<'_>,
997) where
998 D: Copy + Send + Sync,
999 S: Copy + Send + Sync,
1000 Apply: Fn(&mut D, S) + Sync,
1001{
1002 let total = fused_total(layout);
1003 if total == 0 {
1004 return;
1005 }
1006 if let Some(tiles) = tiles {
1007 // SAFETY: forwarded caller contract; `tiles` addresses exactly the
1008 // slots of `layout` and the destination is injective over them.
1009 unsafe {
1010 replay_tiled(
1011 dst_ptr,
1012 dst_base,
1013 src_ptr,
1014 src_base,
1015 tiles,
1016 &apply,
1017 ns_per_element,
1018 exec,
1019 )
1020 };
1021 return;
1022 }
1023 let exec = crate::cost::for_len_at_rate(exec, total, ns_per_element);
1024 if !exec.is_serial() {
1025 let dst_ptr = crate::threading::SendPtr(dst_ptr);
1026 let src_ptr = crate::threading::SendPtr(src_ptr as *mut S);
1027 crate::threading::parallel_for_each(0..total, exec, &|range| {
1028 // SAFETY: the caller contract makes every index in bounds; the
1029 // token is not serial, so the destination strides are injective
1030 // and the disjoint worker ranges write disjoint slots; the source
1031 // is only read.
1032 unsafe {
1033 apply_fused_range(
1034 dst_ptr.as_ptr(),
1035 dst_base,
1036 src_ptr.as_const(),
1037 src_base,
1038 layout,
1039 range.start,
1040 range.len(),
1041 &mut &apply,
1042 );
1043 }
1044 });
1045 return;
1046 }
1047 // SAFETY: forwarded caller contract over the full range `0..total`; one
1048 // sequential walk needs no injectivity.
1049 unsafe {
1050 apply_fused_range(
1051 dst_ptr, dst_base, src_ptr, src_base, layout, 0, total, &mut apply,
1052 );
1053 }
1054}
1055
1056/// Tiled replay of [`replay_fused_raw`]: serially one [`apply_tiled_box`] over
1057/// the whole box, or, when one fork pays, the dimension splitter of the view
1058/// path with one [`apply_tiled_box`] per leaf box.
1059///
1060/// The leaves walk the model's own blocks clipped to the leaf, as Strided.jl's
1061/// leaves rerun `_mapreduce_kernel!` with the same `blocks`; the halved blocks
1062/// the splitter normalizes internally only steer where it may cut.
1063///
1064/// # Safety
1065///
1066/// The [`replay_fused_raw`] contract for `tiles.layout`, with an injective
1067/// destination.
1068#[inline(never)]
1069#[allow(clippy::too_many_arguments)]
1070unsafe fn replay_tiled<D, S, Apply>(
1071 dst_ptr: *mut D,
1072 dst_base: isize,
1073 src_ptr: *const S,
1074 src_base: isize,
1075 tiles: &PairTiles,
1076 apply: &Apply,
1077 ns_per_element: f64,
1078 exec: Exec<'_>,
1079) where
1080 D: Copy + Send + Sync,
1081 S: Copy + Send + Sync,
1082 Apply: Fn(&mut D, S) + Sync,
1083{
1084 let layout = &tiles.layout;
1085 let rank = layout.rank;
1086 let total = fused_total(layout);
1087 // The plan's rate, not the row: a footprint past the class's L2 pays here too
1088 // (strided-rs#364).
1089 if !crate::cost::is_parallel_at_rate(total, ns_per_element, &exec) {
1090 // SAFETY: forwarded caller contract over the whole box.
1091 unsafe {
1092 apply_tiled_box(
1093 dst_ptr,
1094 dst_base,
1095 src_ptr,
1096 src_base,
1097 layout,
1098 &tiles.blocks,
1099 &mut &*apply,
1100 )
1101 };
1102 return;
1103 }
1104 let strides = [&layout.dst_strides[..rank], &layout.src_strides[..rank]];
1105 let costs = crate::fuse::compute_costs(&strides);
1106 let dst_ptr = crate::threading::SendPtr(dst_ptr);
1107 let src_ptr = crate::threading::SendPtr(src_ptr as *mut S);
1108 #[cfg(test)]
1109 let leaves = std::sync::Mutex::new(Vec::new());
1110 let result = crate::threading::mapreduce_threaded_at_rate(
1111 &layout.dims[..rank],
1112 &tiles.blocks[..rank],
1113 &strides,
1114 &[dst_base, src_base],
1115 &costs,
1116 ns_per_element,
1117 exec,
1118 &|box_dims, _, _, offsets| {
1119 #[cfg(test)]
1120 if let Ok(mut leaves) = leaves.lock() {
1121 leaves.push((offsets[0], offsets[1], box_dims.to_vec()));
1122 }
1123 let mut leaf = *layout;
1124 leaf.dims[..rank].copy_from_slice(box_dims);
1125 // SAFETY: the splitter hands disjoint sub-boxes of `layout` with
1126 // the offsets of their origins, so every logical index of a leaf
1127 // is one of `layout`; the injective destination makes the leaves
1128 // write disjoint slots, and the source is only read.
1129 unsafe {
1130 apply_tiled_box(
1131 dst_ptr.as_ptr(),
1132 offsets[0],
1133 src_ptr.as_const(),
1134 offsets[1],
1135 &leaf,
1136 &tiles.blocks,
1137 &mut &*apply,
1138 )
1139 };
1140 Ok(())
1141 },
1142 );
1143 // INVARIANT: the splitter fails only on an extent product beyond `usize`,
1144 // which the caller contract excludes, and the leaves never fail.
1145 debug_assert!(result.is_ok());
1146 #[cfg(test)]
1147 crate::threading::record_tiled_leaves(leaves.into_inner().unwrap_or_default());
1148}
1149
1150/// Tiled replay of a spilled axis list: serially one
1151/// [`apply_spilled_tiled_box`] over the whole box, or, when one fork pays, the
1152/// dimension splitter of the view path with one box walk per leaf box.
1153///
1154/// The spilled counterpart of [`replay_tiled`], on the slice-backed
1155/// [`SpilledTiles`]: same splitter, same per-leaf clipping of the model's own
1156/// blocks.
1157///
1158/// # Safety
1159///
1160/// The [`replay_spilled_raw`] contract for `tiles.dims`, with an injective
1161/// destination.
1162#[allow(clippy::too_many_arguments)]
1163#[inline(never)]
1164unsafe fn replay_spilled_tiled<D, S, Apply>(
1165 dst_ptr: *mut D,
1166 dst_base: isize,
1167 src_ptr: *const S,
1168 src_base: isize,
1169 tiles: &SpilledTiles,
1170 mut apply: Apply,
1171 exec: Exec<'_>,
1172 ns_per_element: f64,
1173) where
1174 D: Copy + Send + Sync,
1175 S: Copy + Send + Sync,
1176 Apply: Fn(&mut D, S) + Sync,
1177{
1178 let total = tiles.dims().iter().product::<usize>();
1179 if !crate::cost::is_parallel_at_rate(total, ns_per_element, &exec) {
1180 // SAFETY: forwarded caller contract over the whole box.
1181 unsafe {
1182 apply_spilled_tiled_box(
1183 dst_ptr,
1184 dst_base,
1185 src_ptr,
1186 src_base,
1187 tiles,
1188 tiles.dims(),
1189 &mut apply,
1190 )
1191 };
1192 return;
1193 }
1194 let strides = [tiles.dst(), tiles.src()];
1195 let costs = crate::fuse::compute_costs(&strides);
1196 let dst_ptr = crate::threading::SendPtr(dst_ptr);
1197 let src_ptr = crate::threading::SendPtr(src_ptr as *mut S);
1198 #[cfg(test)]
1199 let leaves = std::sync::Mutex::new(Vec::new());
1200 let result = crate::threading::mapreduce_threaded_at_rate(
1201 tiles.dims(),
1202 tiles.blocks(),
1203 &strides,
1204 &[dst_base, src_base],
1205 &costs,
1206 ns_per_element,
1207 exec,
1208 &|box_dims, _, _, offsets| {
1209 #[cfg(test)]
1210 if let Ok(mut leaves) = leaves.lock() {
1211 leaves.push((offsets[0], offsets[1], box_dims.to_vec()));
1212 }
1213 // SAFETY: the splitter hands disjoint sub-boxes of `tiles.dims`
1214 // with the offsets of their origins, so every logical index of a
1215 // leaf is one of the tiles' slots; the injective destination makes
1216 // the leaves write disjoint slots, and the source is only read.
1217 unsafe {
1218 apply_spilled_tiled_box(
1219 dst_ptr.as_ptr(),
1220 offsets[0],
1221 src_ptr.as_const(),
1222 offsets[1],
1223 tiles,
1224 box_dims,
1225 &mut &apply,
1226 )
1227 };
1228 Ok(())
1229 },
1230 );
1231 // INVARIANT: the splitter fails only on an extent product beyond `usize`,
1232 // which the caller contract excludes, and the leaves never fail.
1233 debug_assert!(result.is_ok());
1234 #[cfg(test)]
1235 crate::threading::record_tiled_leaves(leaves.into_inner().unwrap_or_default());
1236}
1237
1238/// Pointer-level replay of a spilled axis list.
1239///
1240/// Mirrors [`replay_fused_raw`] including its worker split; kept separate so
1241/// that the inline replay keeps its fixed-rank shape.
1242///
1243/// # Safety
1244///
1245/// The [`replay_fused_raw`] contract, for `axes`.
1246#[allow(clippy::too_many_arguments)]
1247pub(crate) unsafe fn replay_spilled_raw<D, S, Apply>(
1248 dst_ptr: *mut D,
1249 dst_base: isize,
1250 src_ptr: *const S,
1251 src_base: isize,
1252 axes: &[FusedAxis],
1253 mut apply: Apply,
1254 ns_per_element: f64,
1255 exec: Exec<'_>,
1256) where
1257 D: Copy + Send + Sync,
1258 S: Copy + Send + Sync,
1259 Apply: Fn(&mut D, S) + Sync,
1260{
1261 let total = axes.iter().map(|axis| axis.dim).product::<usize>();
1262 if total == 0 {
1263 return;
1264 }
1265 let exec = crate::cost::for_len_at_rate(exec, total, ns_per_element);
1266 if !exec.is_serial() {
1267 let dst_ptr = crate::threading::SendPtr(dst_ptr);
1268 let src_ptr = crate::threading::SendPtr(src_ptr as *mut S);
1269 crate::threading::parallel_for_each(0..total, exec, &|range| {
1270 // SAFETY: as in `replay_fused_raw`: in-bounds indices, injective
1271 // destination for a non-serial token, disjoint worker ranges.
1272 unsafe {
1273 apply_spilled_range(
1274 dst_ptr.as_ptr(),
1275 dst_base,
1276 src_ptr.as_const(),
1277 src_base,
1278 axes,
1279 range.start,
1280 range.len(),
1281 &mut &apply,
1282 );
1283 }
1284 });
1285 return;
1286 }
1287 // SAFETY: forwarded caller contract over the full range `0..total`; one
1288 // sequential walk needs no injectivity.
1289 unsafe {
1290 apply_spilled_range(
1291 dst_ptr, dst_base, src_ptr, src_base, axes, 0, total, &mut apply,
1292 );
1293 }
1294}
1295
1296#[cfg(test)]
1297#[path = "copy_plan/tests/tests.rs"]
1298mod tests;
1299
1300#[cfg(test)]
1301#[path = "copy_plan/tests/parallel_tests.rs"]
1302mod parallel_tests;