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`], one
7//! rank-bounded spill above that), and run plain loops - no view plan, no
8//! cache, and no per-element allocation on any call path. Higher *original*
9//! ranks are normalized and fused before that choice is made, so they no
10//! longer leave the fused replay.
11
12use crate::cost::KernelClass;
13use crate::{ElementOpApply, Exec, RawStridedMut, RawStridedRef, Result};
14use core::mem::MaybeUninit;
15use core::num::NonZeroUsize;
16use core::ops::{Add, Mul};
17
18/// Rank up to which a fused loop nest is stored inline.
19///
20/// The stateless [`copy_scale_raw`] family and [`crate::CopyPlan`] fuse any rank:
21/// layouts whose *fused* rank is at most this limit replay from that inline
22/// storage, and higher fused ranks spill to storage bounded by their rank.
23///
24/// Replay is allocation-free for an original rank at most this limit. A higher
25/// *original* rank needs one transient scratch buffer even when the fused layout
26/// still fits inline, because fusion happens before the representation is
27/// chosen; the replay itself is still allocation-free in that case.
28pub const RAW_FUSED_RANK_LIMIT: usize = 8;
29
30/// One fused axis, used while sorting and merging axes and when a layout has to
31/// spill beyond [`RAW_FUSED_RANK_LIMIT`].
32#[derive(Clone, Copy, Debug)]
33pub(crate) struct FusedAxis {
34 pub(crate) dim: usize,
35 pub(crate) dst: isize,
36 pub(crate) src: isize,
37}
38
39const EMPTY_AXIS: FusedAxis = FusedAxis {
40 dim: 1,
41 dst: 0,
42 src: 0,
43};
44
45/// Stack-allocated fused stride pair (axes ordered by destination stride,
46/// adjacent contiguous axes merged). Built once and replayed by both the
47/// per-call raw kernels and the prepared [`crate::CopyPlan`].
48///
49/// This is the representation every call site replays through, so it keeps the
50/// exact shape, size and `Copy`-ness it had before high-rank fusion existed.
51#[derive(Clone, Copy, Debug)]
52pub(crate) struct FusedPairLayout {
53 pub(crate) rank: usize,
54 pub(crate) dims: [usize; RAW_FUSED_RANK_LIMIT],
55 dst_strides: [isize; RAW_FUSED_RANK_LIMIT],
56 src_strides: [isize; RAW_FUSED_RANK_LIMIT],
57}
58
59impl FusedPairLayout {
60 /// An empty rank-zero layout (one element at the base offset).
61 ///
62 /// Used as the neutral value when an inline `TinyVec<[CopyPlan; N]>` is
63 /// default-initialized; it is never executed as a real plan.
64 fn empty() -> Self {
65 Self {
66 rank: 0,
67 dims: [1; RAW_FUSED_RANK_LIMIT],
68 dst_strides: [0; RAW_FUSED_RANK_LIMIT],
69 src_strides: [0; RAW_FUSED_RANK_LIMIT],
70 }
71 }
72
73 fn from_axes(axes: &[FusedAxis]) -> Self {
74 debug_assert!(axes.len() <= RAW_FUSED_RANK_LIMIT);
75 let mut layout = Self {
76 rank: axes.len(),
77 dims: [1; RAW_FUSED_RANK_LIMIT],
78 dst_strides: [0; RAW_FUSED_RANK_LIMIT],
79 src_strides: [0; RAW_FUSED_RANK_LIMIT],
80 };
81 for (slot, axis) in layout.dims[..axes.len()].iter_mut().zip(axes) {
82 *slot = axis.dim;
83 }
84 for (slot, axis) in layout.dst_strides[..axes.len()].iter_mut().zip(axes) {
85 *slot = axis.dst;
86 }
87 for (slot, axis) in layout.src_strides[..axes.len()].iter_mut().zip(axes) {
88 *slot = axis.src;
89 }
90 layout
91 }
92}
93
94/// A fused pair traversal of any rank.
95///
96/// Fused ranks at most [`RAW_FUSED_RANK_LIMIT`] use the inline layout; longer
97/// layouts keep their axes in one `Vec`. That storage is sized by the original
98/// rank (the fusion scratch is reused, and `truncate` keeps its capacity), never
99/// by the tensor's element count.
100#[derive(Clone, Debug)]
101pub(crate) enum PairTraversal {
102 Inline(FusedPairLayout),
103 Spilled(Vec<FusedAxis>),
104}
105
106impl Default for FusedPairLayout {
107 fn default() -> Self {
108 Self::empty()
109 }
110}
111
112impl Default for PairTraversal {
113 fn default() -> Self {
114 Self::empty()
115 }
116}
117
118impl PairTraversal {
119 /// The empty inline layout, used as a neutral default.
120 #[inline]
121 fn empty() -> Self {
122 Self::Inline(FusedPairLayout::empty())
123 }
124
125 /// The inline layout, or `None` when the traversal spilled.
126 #[inline]
127 pub(crate) fn inline(&self) -> Option<&FusedPairLayout> {
128 match self {
129 Self::Inline(layout) => Some(layout),
130 Self::Spilled(_) => None,
131 }
132 }
133
134 /// Number of fused axes.
135 #[cfg(test)]
136 pub(crate) fn rank(&self) -> usize {
137 match self {
138 Self::Inline(layout) => layout.rank,
139 Self::Spilled(axes) => axes.len(),
140 }
141 }
142}
143
144/// Sort `dims`/`dst_strides`/`src_strides` by destination stride, drop size-1
145/// axes, and merge axes that are contiguous in both layouts.
146///
147/// Returns the fused rank written to `scratch[..rank]`. A zero extent collapses
148/// to a single zero-length axis, which every replay treats as an empty range.
149fn fuse_axes(
150 scratch: &mut [FusedAxis],
151 dims: &[usize],
152 dst_strides: &[isize],
153 src_strides: &[isize],
154) -> usize {
155 debug_assert!(scratch.len() >= dims.len());
156 let mut rank = 0usize;
157 for axis in 0..dims.len() {
158 if dims[axis] == 1 {
159 continue;
160 }
161 if dims[axis] == 0 {
162 scratch[0] = FusedAxis {
163 dim: 0,
164 dst: 0,
165 src: 0,
166 };
167 return 1;
168 }
169 let entry = FusedAxis {
170 dim: dims[axis],
171 dst: dst_strides[axis],
172 src: src_strides[axis],
173 };
174 let mut position = rank;
175 while position > 0 && scratch[position - 1].dst > entry.dst {
176 scratch[position] = scratch[position - 1];
177 position -= 1;
178 }
179 scratch[position] = entry;
180 rank += 1;
181 }
182 if rank == 0 {
183 scratch[0] = EMPTY_AXIS;
184 return 1;
185 }
186 let mut fused = 0usize;
187 for axis in 1..rank {
188 // A merged extent that overflows (possible for a stride-0 broadcast
189 // whose element count exceeds usize) leaves the axes unfused.
190 let merged = isize::try_from(scratch[fused].dim)
191 .ok()
192 .filter(|&extent| {
193 scratch[fused].dst.checked_mul(extent) == Some(scratch[axis].dst)
194 && scratch[fused].src.checked_mul(extent) == Some(scratch[axis].src)
195 })
196 .and_then(|_| scratch[fused].dim.checked_mul(scratch[axis].dim));
197 if let Some(merged) = merged {
198 scratch[fused].dim = merged;
199 } else {
200 fused += 1;
201 scratch[fused] = scratch[axis];
202 }
203 }
204 fused + 1
205}
206
207/// Fuse a raw stride pair into a traversal of any rank.
208///
209/// Inline when the fused rank is at most [`RAW_FUSED_RANK_LIMIT`], otherwise one
210/// rank-bounded spill. An original rank above the limit uses a transient scratch
211/// buffer even when the fused layout still fits inline, so that fusion happens
212/// before the representation is chosen.
213pub(crate) fn fuse_pair_traversal(
214 dims: &[usize],
215 dst_strides: &[isize],
216 src_strides: &[isize],
217) -> PairTraversal {
218 if dims.len() <= RAW_FUSED_RANK_LIMIT {
219 let mut scratch = [EMPTY_AXIS; RAW_FUSED_RANK_LIMIT];
220 let rank = fuse_axes(&mut scratch, dims, dst_strides, src_strides);
221 debug_assert!(rank <= RAW_FUSED_RANK_LIMIT);
222 return PairTraversal::Inline(FusedPairLayout::from_axes(&scratch[..rank]));
223 }
224 let mut scratch = vec![EMPTY_AXIS; dims.len()];
225 let rank = fuse_axes(&mut scratch, dims, dst_strides, src_strides);
226 scratch.truncate(rank);
227 if rank <= RAW_FUSED_RANK_LIMIT {
228 PairTraversal::Inline(FusedPairLayout::from_axes(&scratch))
229 } else {
230 PairTraversal::Spilled(scratch)
231 }
232}
233
234impl PairTraversal {
235 /// The given axes as a traversal, in their given order: nothing is
236 /// sorted, merged or dropped. Rank zero becomes the one-element
237 /// `EMPTY_AXIS` layout that [`fuse_axes`] also produces.
238 ///
239 /// The three slices must have equal length, and the extents a checked,
240 /// nonzero product (the replay totals multiply them unchecked).
241 pub(crate) fn given(dims: &[usize], dst_strides: &[isize], src_strides: &[isize]) -> Self {
242 debug_assert!(dims.len() == dst_strides.len() && dims.len() == src_strides.len());
243 let rank = dims.len();
244 if rank > RAW_FUSED_RANK_LIMIT {
245 return Self::Spilled(
246 dims.iter()
247 .zip(dst_strides)
248 .zip(src_strides)
249 .map(|((&dim, &dst), &src)| FusedAxis { dim, dst, src })
250 .collect(),
251 );
252 }
253 let mut layout = FusedPairLayout::empty();
254 layout.rank = rank.max(1);
255 layout.dims[..rank].copy_from_slice(dims);
256 layout.dst_strides[..rank].copy_from_slice(dst_strides);
257 layout.src_strides[..rank].copy_from_slice(src_strides);
258 Self::Inline(layout)
259 }
260}
261
262/// Fuse a raw stride pair into the inline representation.
263///
264/// Returns `None` when the fused rank exceeds [`RAW_FUSED_RANK_LIMIT`]. Used by
265/// the window plans, whose non-fused replay is compiled alongside the plan.
266pub(crate) fn fuse_pair_layout(
267 dims: &[usize],
268 dst_strides: &[isize],
269 src_strides: &[isize],
270) -> Option<FusedPairLayout> {
271 match fuse_pair_traversal(dims, dst_strides, src_strides) {
272 PairTraversal::Inline(layout) => Some(layout),
273 PairTraversal::Spilled(_) => None,
274 }
275}
276
277/// Number of logical elements covered by a fused layout.
278///
279/// Every constructor of a [`FusedPairLayout`] starts from dims whose product
280/// was checked by [`crate::kernel::total_len`], and fusion only merges axes
281/// with a checked product, so the product cannot overflow.
282#[inline]
283pub(crate) fn fused_total(layout: &FusedPairLayout) -> usize {
284 layout.dims[..layout.rank].iter().product()
285}
286
287/// Number of logical elements covered by a spilled axis list.
288#[inline]
289fn spilled_total(axes: &[FusedAxis]) -> usize {
290 axes.iter().map(|axis| axis.dim).product()
291}
292
293/// Serial replay of a fused pair layout over borrowed raw views.
294///
295/// The destination layout need not be injective: runs are replayed in order,
296/// so accumulating callers such as [`axpy_raw`] keep their sequential
297/// semantics. Parallel replay goes through `copy_plan::replay_fused`, which
298/// the plans and the `replay_*_raw` entries call only with a destination
299/// proven injective or a serial token.
300pub(crate) fn apply_fused_pair<D, S, Apply>(
301 dst: &mut RawStridedMut<'_, D>,
302 src: &RawStridedRef<'_, S>,
303 layout: &FusedPairLayout,
304 apply: Apply,
305) where
306 D: Copy,
307 S: Copy,
308 Apply: Fn(&mut D, S),
309{
310 let total = fused_total(layout);
311 if total == 0 {
312 return;
313 }
314 let src_ptr = src.data().as_ptr();
315 let src_base = src.offset();
316 let dst_base = dst.offset();
317 let dst_ptr = dst.data_mut().as_mut_ptr();
318 // SAFETY: `RawStridedRef`/`RawStridedMut` guarantee (by `new`, or by the
319 // caller of `new_unchecked`) that every offset reachable from their offset
320 // through their dims/strides lies inside their data. Callers pass a layout
321 // fused from exactly those dims/strides, so every logical index in
322 // `0..total` maps to in-bounds source and destination slots. The shared
323 // and exclusive borrows cannot overlap, and this is the only writer.
324 unsafe {
325 apply_fused_range(
326 dst_ptr, dst_base, src_ptr, src_base, layout, 0, total, &apply,
327 );
328 }
329}
330
331/// Serial replay of a spilled fused axis list over borrowed raw views.
332///
333/// Kept out of line and separate from [`apply_fused_pair`] so that the inline
334/// entry points keep the code shape they had before high-rank fusion existed:
335/// fused ranks above [`RAW_FUSED_RANK_LIMIT`] are the rare case, and inlining
336/// this second carry loop into them measurably slowed the inline path (extra
337/// register pressure in a loop that runs once per short run).
338#[inline(never)]
339pub(crate) fn apply_spilled_pair<D, S, Apply>(
340 dst: &mut RawStridedMut<'_, D>,
341 src: &RawStridedRef<'_, S>,
342 axes: &[FusedAxis],
343 apply: Apply,
344) where
345 D: Copy,
346 S: Copy,
347 Apply: Fn(&mut D, S),
348{
349 let total = spilled_total(axes);
350 if total == 0 {
351 return;
352 }
353 let src_ptr = src.data().as_ptr();
354 let src_base = src.offset();
355 let dst_base = dst.offset();
356 let dst_ptr = dst.data_mut().as_mut_ptr();
357 // SAFETY: same contract as `apply_fused_pair`, for the axis list fused from
358 // the same dims/strides.
359 unsafe {
360 apply_spilled_range(dst_ptr, dst_base, src_ptr, src_base, axes, 0, total, &apply);
361 }
362}
363
364/// Replay logical indices `start..start + len` of a fused pair layout, in
365/// column-major order of the fused axes (axis 0 fastest).
366///
367/// The start coordinate is decoded once; runs along axis 0 then advance the
368/// outer coordinates incrementally, so no per-element range checks or
369/// coordinate rebuilds remain in the hot loop.
370///
371/// # Safety
372///
373/// - `start + len` must not exceed [`fused_total`] of `layout`.
374/// - For every logical index `i` in the range, `dst_base` plus the fused
375/// destination offset of `i` must be an in-bounds, writable slot of the
376/// allocation behind `dst_ptr`, and likewise `src_base` plus the source
377/// offset must be an in-bounds, readable slot behind `src_ptr`.
378/// - No other thread may access the destination slots of this range while it
379/// runs, and the source slots must not be written concurrently. Destination
380/// and source slots must not overlap.
381// Range leaf: both bases, the layout, the range and the closure, called once per worker
382// range.
383#[allow(clippy::too_many_arguments)]
384pub(crate) unsafe fn apply_fused_range<D, S, Apply>(
385 dst_ptr: *mut D,
386 dst_base: isize,
387 src_ptr: *const S,
388 src_base: isize,
389 layout: &FusedPairLayout,
390 start: usize,
391 len: usize,
392 apply: &Apply,
393) where
394 D: Copy,
395 S: Copy,
396 Apply: Fn(&mut D, S),
397{
398 if len == 0 {
399 return;
400 }
401 let rank = layout.rank;
402 let inner_len = layout.dims[0];
403 let inner_dst = layout.dst_strides[0];
404 let inner_src = layout.src_strides[0];
405
406 // Decode the start coordinate once per range. `dst_offset`/`src_offset`
407 // track the offset of the current run start (outer coordinates plus the
408 // inner coordinate `inner_start`); every value is a reachable offset.
409 let mut index = [0usize; RAW_FUSED_RANK_LIMIT];
410 let mut rest = start;
411 let mut dst_outer = dst_base;
412 let mut src_outer = src_base;
413 // The axis indexes `index`, `layout.dims` and both stride tables at once.
414 #[allow(clippy::needless_range_loop)]
415 for axis in 0..rank {
416 let dim = layout.dims[axis];
417 index[axis] = rest % dim;
418 rest /= dim;
419 if axis > 0 {
420 dst_outer += index[axis] as isize * layout.dst_strides[axis];
421 src_outer += index[axis] as isize * layout.src_strides[axis];
422 }
423 }
424 let mut inner_start = index[0];
425 let mut remaining = len;
426 loop {
427 let run = (inner_len - inner_start).min(remaining);
428 let dst_run = dst_outer + inner_start as isize * inner_dst;
429 let src_run = src_outer + inner_start as isize * inner_src;
430 // SAFETY: the run covers logical indices inside the caller's range, so
431 // by this function's contract every slot touched below is in-bounds,
432 // exclusively owned by this call (destination) and unaliased.
433 unsafe {
434 apply_run(
435 dst_ptr, dst_run, inner_dst, src_ptr, src_run, inner_src, run, apply,
436 )
437 };
438 remaining -= run;
439 if remaining == 0 {
440 return;
441 }
442 inner_start = 0;
443 // Advance an axis only when another position along it follows, and
444 // rewind it from its last position, so every intermediate base is a
445 // reachable offset of a validated layout (issue #243 follow-up): a
446 // layout ending within one stride of `isize::MAX` must not overflow.
447 // `remaining > 0` guarantees a following run exists, so the loop
448 // always finds an axis to advance before running out of rank.
449 let mut axis = 1;
450 while axis < rank {
451 if index[axis] + 1 < layout.dims[axis] {
452 index[axis] += 1;
453 dst_outer += layout.dst_strides[axis];
454 src_outer += layout.src_strides[axis];
455 break;
456 }
457 let last = (layout.dims[axis] - 1) as isize;
458 dst_outer -= last * layout.dst_strides[axis];
459 src_outer -= last * layout.src_strides[axis];
460 index[axis] = 0;
461 axis += 1;
462 }
463 }
464}
465
466/// Replay logical indices `start..start + len` of a spilled fused axis list, in
467/// column-major order of the axes (axis 0 fastest).
468///
469/// The carry loop is the one [`apply_fused_range`] uses, over interleaved axes
470/// with its carry state in one rank-bounded `Vec`: no allocation scales with
471/// the tensor size and no per-element coordinate decode happens.
472///
473/// # Safety
474///
475/// The [`apply_fused_range`] contract holds for `axes`.
476///
477/// Kept out of line: inlining this second carry loop into the inline replay
478/// measurably slows that one down.
479// Same shape as `apply_fused_range` for the spilled layout, per worker range.
480#[allow(clippy::too_many_arguments)]
481#[inline(never)]
482pub(crate) unsafe fn apply_spilled_range<D, S, Apply>(
483 dst_ptr: *mut D,
484 dst_base: isize,
485 src_ptr: *const S,
486 src_base: isize,
487 axes: &[FusedAxis],
488 start: usize,
489 len: usize,
490 apply: &Apply,
491) where
492 D: Copy,
493 S: Copy,
494 Apply: Fn(&mut D, S),
495{
496 if len == 0 {
497 return;
498 }
499 let rank = axes.len();
500 let inner_len = axes[0].dim;
501 let inner_dst = axes[0].dst;
502 let inner_src = axes[0].src;
503
504 let mut index = vec![0usize; rank];
505 let mut rest = start;
506 let mut dst_outer = dst_base;
507 let mut src_outer = src_base;
508 for axis in 0..rank {
509 let dim = axes[axis].dim;
510 index[axis] = rest % dim;
511 rest /= dim;
512 if axis > 0 {
513 dst_outer += index[axis] as isize * axes[axis].dst;
514 src_outer += index[axis] as isize * axes[axis].src;
515 }
516 }
517 let mut inner_start = index[0];
518 let mut remaining = len;
519 loop {
520 let run = (inner_len - inner_start).min(remaining);
521 let dst_run = dst_outer + inner_start as isize * inner_dst;
522 let src_run = src_outer + inner_start as isize * inner_src;
523 // SAFETY: the run covers logical indices inside the caller's range, so
524 // by the caller's contract every slot touched below is in-bounds,
525 // exclusively owned by this call (destination) and unaliased.
526 unsafe {
527 apply_run(
528 dst_ptr, dst_run, inner_dst, src_ptr, src_run, inner_src, run, apply,
529 )
530 };
531 remaining -= run;
532 if remaining == 0 {
533 return;
534 }
535 inner_start = 0;
536 // Same incremental carry as the inline replay: offsets only ever hold
537 // reachable positions, and `remaining > 0` guarantees an axis advances.
538 let mut axis = 1;
539 while axis < rank {
540 if index[axis] + 1 < axes[axis].dim {
541 index[axis] += 1;
542 dst_outer += axes[axis].dst;
543 src_outer += axes[axis].src;
544 break;
545 }
546 let last = (axes[axis].dim - 1) as isize;
547 dst_outer -= last * axes[axis].dst;
548 src_outer -= last * axes[axis].src;
549 index[axis] = 0;
550 axis += 1;
551 }
552 }
553}
554
555/// One run along the fused inner axis.
556///
557/// # Safety
558///
559/// Every `dst_offset + k * dst_stride` and `src_offset + k * src_stride` for
560/// `k < len` must be an in-bounds slot as described in [`apply_fused_range`],
561/// with exclusive access to the destination slots.
562// Run leaf: both base/offset/stride triples, the length and the closure, per run.
563#[allow(clippy::too_many_arguments)]
564#[inline(always)]
565unsafe fn apply_run<D, S, Apply>(
566 dst_ptr: *mut D,
567 dst_offset: isize,
568 dst_stride: isize,
569 src_ptr: *const S,
570 src_offset: isize,
571 src_stride: isize,
572 len: usize,
573 apply: &Apply,
574) where
575 D: Copy,
576 S: Copy,
577 Apply: Fn(&mut D, S),
578{
579 if dst_stride == 1 {
580 // SAFETY: a unit destination stride makes the run `len` consecutive
581 // in-bounds slots starting at `dst_offset`, exclusively owned here.
582 let dst_run = unsafe { core::slice::from_raw_parts_mut(dst_ptr.offset(dst_offset), len) };
583 if src_stride == 1 {
584 // A `copy_nonoverlapping` per run is not used for plain copies:
585 // it measured slower than this element loop for short runs
586 // (one `memcpy` call each) and for long cache-resident copies.
587 // SAFETY: `len` consecutive in-bounds source slots, which the
588 // exclusive destination run cannot overlap.
589 let src_run = unsafe { core::slice::from_raw_parts(src_ptr.offset(src_offset), len) };
590 for (dst, &value) in dst_run.iter_mut().zip(src_run) {
591 apply(dst, value);
592 }
593 return;
594 }
595 if src_stride == -1 {
596 // INVARIANT: the range walks never pass an empty run, and both
597 // strides are nonzero, so the validated reach `len - 1` fits
598 // `isize`; casting `len` itself would wrap for a run of
599 // `isize::MAX + 1` elements. (A `saturating_sub` here measurably
600 // slowed short unit-stride runs by changing the code layout of
601 // the whole inlined walk.)
602 let last = (len - 1) as isize;
603 // SAFETY: the run reads `src_offset - (len - 1) ..= src_offset`,
604 // all in-bounds; the lowest one is the run's last source slot.
605 let src_run =
606 unsafe { core::slice::from_raw_parts(src_ptr.offset(src_offset - last), len) };
607 for (dst, &value) in dst_run.iter_mut().zip(src_run.iter().rev()) {
608 apply(dst, value);
609 }
610 return;
611 }
612 // SAFETY: the run start is an in-bounds source slot.
613 let src_start = unsafe { src_ptr.offset(src_offset) };
614 for (position, dst) in dst_run.iter_mut().enumerate() {
615 // SAFETY: `position < len`, so this is a run source slot.
616 let value = unsafe { *src_start.offset(position as isize * src_stride) };
617 apply(dst, value);
618 }
619 return;
620 }
621 // SAFETY: the run start is an in-bounds slot of each allocation.
622 let dst_start = unsafe { dst_ptr.offset(dst_offset) };
623 let src_start = unsafe { src_ptr.offset(src_offset) };
624 // The bound stays `usize`: a checked broadcast run may hold more than
625 // `isize::MAX` elements, and `len as isize` would wrap to an empty loop.
626 for position in 0..len {
627 // INVARIANT: a nonzero stride bounds the run by its validated reach,
628 // so `position` fits `isize` exactly; a longer run is possible only
629 // along a zero stride, where the wrapped cast is multiplied by zero.
630 let position = position as isize;
631 // SAFETY: `position < len`, so both are slots of this run.
632 unsafe {
633 let value = *src_start.offset(position * src_stride);
634 apply(&mut *dst_start.offset(position * dst_stride), value);
635 }
636 }
637}
638
639fn ensure_same_dims(dst: &[usize], src: &[usize]) -> Result<()> {
640 if dst != src {
641 return Err(crate::StridedError::ShapeMismatch(
642 dst.to_vec(),
643 src.to_vec(),
644 ));
645 }
646 // Reject an element count beyond usize (a huge stride-0 broadcast)
647 // instead of replaying it.
648 crate::kernel::total_len(dst)?;
649 Ok(())
650}
651
652/// `dest = scale * src` over borrowed raw strided layouts.
653///
654/// # Errors
655///
656/// Returns [`crate::StridedError::ShapeMismatch`] when `dest` and `src` do
657/// not describe the same extents, or [`crate::StridedError::OffsetOverflow`]
658/// when the element count does not fit `usize`. Nothing is written on error.
659pub fn copy_scale_raw<T>(
660 dest: &mut RawStridedMut<'_, T>,
661 src: &RawStridedRef<'_, T>,
662 scale: T,
663) -> Result<()>
664where
665 T: Copy + Mul<T, Output = T> + ElementOpApply + Send + Sync,
666{
667 ensure_same_dims(dest.dims(), src.dims())?;
668 match fuse_pair_traversal(dest.dims(), dest.strides(), src.strides()) {
669 PairTraversal::Inline(layout) => {
670 apply_fused_pair(dest, src, &layout, |dst: &mut T, value: T| {
671 *dst = scale * value
672 })
673 }
674 PairTraversal::Spilled(axes) => {
675 apply_spilled_pair(dest, src, &axes, |dst: &mut T, value: T| {
676 *dst = scale * value
677 })
678 }
679 }
680 Ok(())
681}
682
683/// `dest = scale * conj(src)` over borrowed raw strided layouts.
684///
685/// # Errors
686///
687/// Returns [`crate::StridedError::ShapeMismatch`] when `dest` and `src` do
688/// not describe the same extents, or [`crate::StridedError::OffsetOverflow`]
689/// when the element count does not fit `usize`. Nothing is written on error.
690pub fn copy_scale_conj_raw<T>(
691 dest: &mut RawStridedMut<'_, T>,
692 src: &RawStridedRef<'_, T>,
693 scale: T,
694) -> Result<()>
695where
696 T: Copy + Mul<T, Output = T> + ElementOpApply + Send + Sync,
697{
698 ensure_same_dims(dest.dims(), src.dims())?;
699 match fuse_pair_traversal(dest.dims(), dest.strides(), src.strides()) {
700 PairTraversal::Inline(layout) => {
701 apply_fused_pair(dest, src, &layout, |dst: &mut T, value: T| {
702 *dst = scale * value.conj()
703 })
704 }
705 PairTraversal::Spilled(axes) => {
706 apply_spilled_pair(dest, src, &axes, |dst: &mut T, value: T| {
707 *dst = scale * value.conj()
708 })
709 }
710 }
711 Ok(())
712}
713
714/// `dest = alpha * src + dest` over borrowed raw strided layouts.
715///
716/// # Errors
717///
718/// Returns [`crate::StridedError::ShapeMismatch`] when `dest` and `src` do
719/// not describe the same extents, or [`crate::StridedError::OffsetOverflow`]
720/// when the element count does not fit `usize`. Nothing is written on error.
721pub fn axpy_raw<T>(
722 dest: &mut RawStridedMut<'_, T>,
723 src: &RawStridedRef<'_, T>,
724 alpha: T,
725) -> Result<()>
726where
727 T: Copy + Add<T, Output = T> + Mul<T, Output = T> + ElementOpApply + Send + Sync,
728{
729 ensure_same_dims(dest.dims(), src.dims())?;
730 match fuse_pair_traversal(dest.dims(), dest.strides(), src.strides()) {
731 PairTraversal::Inline(layout) => {
732 apply_fused_pair(dest, src, &layout, |dst: &mut T, value: T| {
733 *dst = *dst + alpha * value
734 })
735 }
736 PairTraversal::Spilled(axes) => {
737 apply_spilled_pair(dest, src, &axes, |dst: &mut T, value: T| {
738 *dst = *dst + alpha * value
739 })
740 }
741 }
742 Ok(())
743}
744
745/// `dest = alpha * conj(src) + dest` over borrowed raw strided layouts.
746///
747/// # Errors
748///
749/// Returns [`crate::StridedError::ShapeMismatch`] when `dest` and `src` do
750/// not describe the same extents, or [`crate::StridedError::OffsetOverflow`]
751/// when the element count does not fit `usize`. Nothing is written on error.
752pub fn axpy_conj_raw<T>(
753 dest: &mut RawStridedMut<'_, T>,
754 src: &RawStridedRef<'_, T>,
755 alpha: T,
756) -> Result<()>
757where
758 T: Copy + Add<T, Output = T> + Mul<T, Output = T> + ElementOpApply + Send + Sync,
759{
760 ensure_same_dims(dest.dims(), src.dims())?;
761 match fuse_pair_traversal(dest.dims(), dest.strides(), src.strides()) {
762 PairTraversal::Inline(layout) => {
763 apply_fused_pair(dest, src, &layout, |dst: &mut T, value: T| {
764 *dst = *dst + alpha * value.conj()
765 })
766 }
767 PairTraversal::Spilled(axes) => {
768 apply_spilled_pair(dest, src, &axes, |dst: &mut T, value: T| {
769 *dst = *dst + alpha * value.conj()
770 })
771 }
772 }
773 Ok(())
774}
775
776/// Checked replay of the given axes of two views: the shared body of the
777/// `replay_*_raw` entries.
778///
779/// The element count is checked before anything is built. The unfused
780/// traversal keeps every given extent, and the replay totals (`fused_total`,
781/// `replay_spilled_raw`) take an unchecked product, so the zero-first count
782/// of `kernel::total_len` has to keep an empty layout whose nonzero prefix
783/// overflows, such as `[usize::MAX, 2, 0]`, away from them.
784fn replay_given<D, S, Apply>(
785 dest: &mut RawStridedMut<'_, D>,
786 src: &RawStridedRef<'_, S>,
787 apply: Apply,
788 exec: Exec<'_>,
789) -> Result<()>
790where
791 D: Copy + Send + Sync,
792 S: Copy + Send + Sync,
793 Apply: Fn(&mut D, S) + Sync,
794{
795 ensure_same_dims(dest.dims(), src.dims())?;
796 let total = crate::kernel::total_len(dest.dims())?;
797 if total == 0 {
798 return Ok(());
799 }
800 let traversal = PairTraversal::given(dest.dims(), dest.strides(), src.strides());
801 let mut exec = crate::cost::for_len(exec, KernelClass::Copy, total);
802 if !exec.is_serial()
803 && !crate::layout_check::is_injective_layout_without_alloc(dest.dims(), dest.strides())
804 {
805 // A destination not proven injective replays as one sequential walk,
806 // which is also its defined semantics; the budget-one token cannot be
807 // widened again by the replay's own width rule.
808 exec = exec.limit(NonZeroUsize::MIN);
809 }
810 // SAFETY: `traversal` is built from exactly the views' dims and strides
811 // (`ensure_same_dims` proved the dims agree), so the views' bounds proofs
812 // cover every replayed offset; `total_len` checked the nonzero product;
813 // a non-serial `exec` is left only for a destination proven injective;
814 // the exclusive and shared borrows cannot overlap.
815 unsafe { crate::copy_plan::replay_fused(dest, src, &traversal, apply, exec) };
816 Ok(())
817}
818
819/// `dest = src`, replaying the axes of the two views exactly as given.
820///
821/// The views carry already-fused dims: no axis is reordered, dropped or
822/// merged, and no plan is compiled. Axis 0 is the inner run. Bounds were validated when the views were built
823/// ([`RawStridedRef::new`], [`RawStridedMut::new`]). On a successful call the
824/// replay itself (validation, traversal and dispatch) allocates nothing for a
825/// rank at most [`RAW_FUSED_RANK_LIMIT`]; above it, the axis list and the cursor
826/// of each replayed range are stored in rank-sized buffers. An error may
827/// allocate its payload.
828///
829/// The width comes from the repository rule on `exec`. A parallel replay runs
830/// only on a destination proven injective without allocating; any other
831/// destination is replayed serially in column-major order of the given axes.
832///
833/// # Errors
834///
835/// [`StridedError::ShapeMismatch`](crate::StridedError::ShapeMismatch) when the
836/// two views have different dims, and
837/// [`StridedError::OffsetOverflow`](crate::StridedError::OffsetOverflow) when the
838/// element count overflows `usize`; both before any write.
839///
840/// # Examples
841///
842/// Copy the outer band `1..3` of a stored `2 x 3` block into a transposed
843/// destination:
844///
845/// ```rust
846/// use strided_basic::{replay_copy_raw, Exec, RawStridedMut, RawStridedRef};
847///
848/// let stored = [0.0f64, 1.0, 2.0, 3.0, 4.0, 5.0]; // column-major 2 x 3
849/// let band = [2usize, 2];
850/// let src = RawStridedRef::new(&stored, &band, &[1, 2], 2).unwrap();
851/// let mut out = [0.0f64; 4];
852/// let mut dst = RawStridedMut::new(&mut out, &band, &[2, 1], 0).unwrap();
853/// replay_copy_raw(&mut dst, &src, Exec::serial()).unwrap();
854/// assert_eq!(out, [2.0, 4.0, 3.0, 5.0]);
855/// ```
856pub fn replay_copy_raw<T>(
857 dest: &mut RawStridedMut<'_, T>,
858 src: &RawStridedRef<'_, T>,
859 exec: Exec<'_>,
860) -> Result<()>
861where
862 T: Copy + Send + Sync,
863{
864 replay_given(dest, src, |dst: &mut T, value: T| *dst = value, exec)
865}
866
867/// [`replay_copy_raw`] into a potentially uninitialized destination.
868///
869/// On success every reachable destination element is initialized and no
870/// other slot is written. The destination is never read.
871///
872/// # Errors
873///
874/// As [`replay_copy_raw`].
875///
876/// # Examples
877///
878/// ```rust
879/// use core::mem::MaybeUninit;
880/// use strided_basic::{replay_copy_raw_uninit, Exec, RawStridedMut, RawStridedRef};
881///
882/// let src = [1.0f64, 2.0, 3.0];
883/// let mut storage = [MaybeUninit::<f64>::uninit(); 3];
884/// let mut dst = RawStridedMut::new(&mut storage, &[3], &[1], 0).unwrap();
885/// let source = RawStridedRef::new(&src, &[3], &[-1], 2).unwrap();
886/// replay_copy_raw_uninit(&mut dst, &source, Exec::serial()).unwrap();
887/// drop(dst);
888/// // SAFETY: every reachable destination slot was initialized above.
889/// let values: Vec<f64> = storage.iter().map(|v| unsafe { v.assume_init() }).collect();
890/// assert_eq!(values, [3.0, 2.0, 1.0]);
891/// ```
892pub fn replay_copy_raw_uninit<T>(
893 dest: &mut RawStridedMut<'_, MaybeUninit<T>>,
894 src: &RawStridedRef<'_, T>,
895 exec: Exec<'_>,
896) -> Result<()>
897where
898 T: Copy + Send + Sync,
899{
900 replay_given(
901 dest,
902 src,
903 |dst: &mut MaybeUninit<T>, value: T| {
904 dst.write(value);
905 },
906 exec,
907 )
908}
909
910/// `f(&mut dest[i], src[i])` for every element, replaying the axes of the two
911/// views exactly as given.
912///
913/// Traversal, width and errors are those of [`replay_copy_raw`], and so is the
914/// allocation guarantee, which covers the replay only: allocations made by `f`
915/// are its own. `f` runs once per logical element with exactly its arithmetic,
916/// so an accumulate such as `|d, s| *d += s` is exact. The order in which
917/// elements are visited is unspecified, and on a parallel replay `f` runs
918/// concurrently on disjoint slots: the result is defined only for an `f` whose
919/// effect depends on the supplied slot values alone. On a destination that is
920/// not proven injective, the elements are visited serially in column-major
921/// order of the given axes.
922///
923/// # Errors
924///
925/// As [`replay_copy_raw`].
926///
927/// # Examples
928///
929/// ```rust
930/// use strided_basic::{replay_map_raw, Exec, RawStridedMut, RawStridedRef};
931///
932/// let src = [1.0f64, 2.0, 3.0, 4.0];
933/// let mut acc = [10.0f64, 20.0, 30.0, 40.0];
934/// let source = RawStridedRef::new(&src, &[2, 2], &[2, 1], 0).unwrap();
935/// let mut dst = RawStridedMut::new(&mut acc, &[2, 2], &[1, 2], 0).unwrap();
936/// replay_map_raw(&mut dst, &source, |d, s| *d += s, Exec::serial()).unwrap();
937/// assert_eq!(acc, [11.0, 23.0, 32.0, 44.0]);
938/// ```
939pub fn replay_map_raw<D, S, F>(
940 dest: &mut RawStridedMut<'_, D>,
941 src: &RawStridedRef<'_, S>,
942 f: F,
943 exec: Exec<'_>,
944) -> Result<()>
945where
946 D: Copy + Send + Sync,
947 S: Copy + Send + Sync,
948 F: Fn(&mut D, S) + Send + Sync,
949{
950 replay_given(dest, src, f, exec)
951}
952
953/// `dest[i] = f(src[i])` into a potentially uninitialized destination.
954///
955/// `f` cannot read the destination. On success every reachable destination
956/// element is initialized and no other slot is written. The visit-order,
957/// callback and allocation contract is that of [`replay_map_raw`].
958///
959/// # Errors
960///
961/// As [`replay_copy_raw`].
962///
963/// # Examples
964///
965/// ```rust
966/// use core::mem::MaybeUninit;
967/// use strided_basic::{replay_map_raw_uninit, Exec, RawStridedMut, RawStridedRef};
968///
969/// let src = [1i32, 2, 3];
970/// let mut storage = [MaybeUninit::<f64>::uninit(); 3];
971/// let mut dst = RawStridedMut::new(&mut storage, &[3], &[1], 0).unwrap();
972/// let source = RawStridedRef::new(&src, &[3], &[1], 0).unwrap();
973/// replay_map_raw_uninit(&mut dst, &source, |s| f64::from(s) * 0.5, Exec::serial()).unwrap();
974/// drop(dst);
975/// // SAFETY: every reachable destination slot was initialized above.
976/// let values: Vec<f64> = storage.iter().map(|v| unsafe { v.assume_init() }).collect();
977/// assert_eq!(values, [0.5, 1.0, 1.5]);
978/// ```
979pub fn replay_map_raw_uninit<D, S, F>(
980 dest: &mut RawStridedMut<'_, MaybeUninit<D>>,
981 src: &RawStridedRef<'_, S>,
982 f: F,
983 exec: Exec<'_>,
984) -> Result<()>
985where
986 D: Copy + Send + Sync,
987 S: Copy + Send + Sync,
988 F: Fn(S) -> D + Send + Sync,
989{
990 replay_given(
991 dest,
992 src,
993 move |dst: &mut MaybeUninit<D>, value: S| {
994 dst.write(f(value));
995 },
996 exec,
997 )
998}
999
1000#[cfg(test)]
1001#[path = "raw_ops/tests/tests.rs"]
1002mod tests;
1003
1004#[cfg(test)]
1005#[path = "raw_ops/tests/replay_tests.rs"]
1006mod replay_tests;