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#[allow(clippy::too_many_arguments)]
382pub(crate) unsafe fn apply_fused_range<D, S, Apply>(
383 dst_ptr: *mut D,
384 dst_base: isize,
385 src_ptr: *const S,
386 src_base: isize,
387 layout: &FusedPairLayout,
388 start: usize,
389 len: usize,
390 apply: &Apply,
391) where
392 D: Copy,
393 S: Copy,
394 Apply: Fn(&mut D, S),
395{
396 if len == 0 {
397 return;
398 }
399 let rank = layout.rank;
400 let inner_len = layout.dims[0];
401 let inner_dst = layout.dst_strides[0];
402 let inner_src = layout.src_strides[0];
403
404 // Decode the start coordinate once per range. `dst_offset`/`src_offset`
405 // track the offset of the current run start (outer coordinates plus the
406 // inner coordinate `inner_start`); every value is a reachable offset.
407 let mut index = [0usize; RAW_FUSED_RANK_LIMIT];
408 let mut rest = start;
409 let mut dst_outer = dst_base;
410 let mut src_outer = src_base;
411 for axis in 0..rank {
412 let dim = layout.dims[axis];
413 index[axis] = rest % dim;
414 rest /= dim;
415 if axis > 0 {
416 dst_outer += index[axis] as isize * layout.dst_strides[axis];
417 src_outer += index[axis] as isize * layout.src_strides[axis];
418 }
419 }
420 let mut inner_start = index[0];
421 let mut remaining = len;
422 loop {
423 let run = (inner_len - inner_start).min(remaining);
424 let dst_run = dst_outer + inner_start as isize * inner_dst;
425 let src_run = src_outer + inner_start as isize * inner_src;
426 // SAFETY: the run covers logical indices inside the caller's range, so
427 // by this function's contract every slot touched below is in-bounds,
428 // exclusively owned by this call (destination) and unaliased.
429 unsafe {
430 apply_run(
431 dst_ptr, dst_run, inner_dst, src_ptr, src_run, inner_src, run, apply,
432 )
433 };
434 remaining -= run;
435 if remaining == 0 {
436 return;
437 }
438 inner_start = 0;
439 // Advance an axis only when another position along it follows, and
440 // rewind it from its last position, so every intermediate base is a
441 // reachable offset of a validated layout (issue #243 follow-up): a
442 // layout ending within one stride of `isize::MAX` must not overflow.
443 // `remaining > 0` guarantees a following run exists, so the loop
444 // always finds an axis to advance before running out of rank.
445 let mut axis = 1;
446 while axis < rank {
447 if index[axis] + 1 < layout.dims[axis] {
448 index[axis] += 1;
449 dst_outer += layout.dst_strides[axis];
450 src_outer += layout.src_strides[axis];
451 break;
452 }
453 let last = (layout.dims[axis] - 1) as isize;
454 dst_outer -= last * layout.dst_strides[axis];
455 src_outer -= last * layout.src_strides[axis];
456 index[axis] = 0;
457 axis += 1;
458 }
459 }
460}
461
462/// Replay logical indices `start..start + len` of a spilled fused axis list, in
463/// column-major order of the axes (axis 0 fastest).
464///
465/// The carry loop is the one [`apply_fused_range`] uses, over interleaved axes
466/// with its carry state in one rank-bounded `Vec`: no allocation scales with
467/// the tensor size and no per-element coordinate decode happens.
468///
469/// # Safety
470///
471/// The [`apply_fused_range`] contract holds for `axes`.
472///
473/// Kept out of line: inlining this second carry loop into the inline replay
474/// measurably slows that one down.
475#[allow(clippy::too_many_arguments)]
476#[inline(never)]
477pub(crate) unsafe fn apply_spilled_range<D, S, Apply>(
478 dst_ptr: *mut D,
479 dst_base: isize,
480 src_ptr: *const S,
481 src_base: isize,
482 axes: &[FusedAxis],
483 start: usize,
484 len: usize,
485 apply: &Apply,
486) where
487 D: Copy,
488 S: Copy,
489 Apply: Fn(&mut D, S),
490{
491 if len == 0 {
492 return;
493 }
494 let rank = axes.len();
495 let inner_len = axes[0].dim;
496 let inner_dst = axes[0].dst;
497 let inner_src = axes[0].src;
498
499 let mut index = vec![0usize; rank];
500 let mut rest = start;
501 let mut dst_outer = dst_base;
502 let mut src_outer = src_base;
503 for axis in 0..rank {
504 let dim = axes[axis].dim;
505 index[axis] = rest % dim;
506 rest /= dim;
507 if axis > 0 {
508 dst_outer += index[axis] as isize * axes[axis].dst;
509 src_outer += index[axis] as isize * axes[axis].src;
510 }
511 }
512 let mut inner_start = index[0];
513 let mut remaining = len;
514 loop {
515 let run = (inner_len - inner_start).min(remaining);
516 let dst_run = dst_outer + inner_start as isize * inner_dst;
517 let src_run = src_outer + inner_start as isize * inner_src;
518 // SAFETY: the run covers logical indices inside the caller's range, so
519 // by the caller's contract every slot touched below is in-bounds,
520 // exclusively owned by this call (destination) and unaliased.
521 unsafe {
522 apply_run(
523 dst_ptr, dst_run, inner_dst, src_ptr, src_run, inner_src, run, apply,
524 )
525 };
526 remaining -= run;
527 if remaining == 0 {
528 return;
529 }
530 inner_start = 0;
531 // Same incremental carry as the inline replay: offsets only ever hold
532 // reachable positions, and `remaining > 0` guarantees an axis advances.
533 let mut axis = 1;
534 while axis < rank {
535 if index[axis] + 1 < axes[axis].dim {
536 index[axis] += 1;
537 dst_outer += axes[axis].dst;
538 src_outer += axes[axis].src;
539 break;
540 }
541 let last = (axes[axis].dim - 1) as isize;
542 dst_outer -= last * axes[axis].dst;
543 src_outer -= last * axes[axis].src;
544 index[axis] = 0;
545 axis += 1;
546 }
547 }
548}
549
550/// One run along the fused inner axis.
551///
552/// # Safety
553///
554/// Every `dst_offset + k * dst_stride` and `src_offset + k * src_stride` for
555/// `k < len` must be an in-bounds slot as described in [`apply_fused_range`],
556/// with exclusive access to the destination slots.
557#[allow(clippy::too_many_arguments)]
558#[inline(always)]
559unsafe fn apply_run<D, S, Apply>(
560 dst_ptr: *mut D,
561 dst_offset: isize,
562 dst_stride: isize,
563 src_ptr: *const S,
564 src_offset: isize,
565 src_stride: isize,
566 len: usize,
567 apply: &Apply,
568) where
569 D: Copy,
570 S: Copy,
571 Apply: Fn(&mut D, S),
572{
573 if dst_stride == 1 {
574 // SAFETY: a unit destination stride makes the run `len` consecutive
575 // in-bounds slots starting at `dst_offset`, exclusively owned here.
576 let dst_run = unsafe { core::slice::from_raw_parts_mut(dst_ptr.offset(dst_offset), len) };
577 if src_stride == 1 {
578 // A `copy_nonoverlapping` per run is not used for plain copies:
579 // it measured slower than this element loop for short runs
580 // (one `memcpy` call each) and for long cache-resident copies.
581 // SAFETY: `len` consecutive in-bounds source slots, which the
582 // exclusive destination run cannot overlap.
583 let src_run = unsafe { core::slice::from_raw_parts(src_ptr.offset(src_offset), len) };
584 for (dst, &value) in dst_run.iter_mut().zip(src_run) {
585 apply(dst, value);
586 }
587 return;
588 }
589 if src_stride == -1 {
590 // INVARIANT: the range walks never pass an empty run, and both
591 // strides are nonzero, so the validated reach `len - 1` fits
592 // `isize`; casting `len` itself would wrap for a run of
593 // `isize::MAX + 1` elements. (A `saturating_sub` here measurably
594 // slowed short unit-stride runs by changing the code layout of
595 // the whole inlined walk.)
596 let last = (len - 1) as isize;
597 // SAFETY: the run reads `src_offset - (len - 1) ..= src_offset`,
598 // all in-bounds; the lowest one is the run's last source slot.
599 let src_run =
600 unsafe { core::slice::from_raw_parts(src_ptr.offset(src_offset - last), len) };
601 for (dst, &value) in dst_run.iter_mut().zip(src_run.iter().rev()) {
602 apply(dst, value);
603 }
604 return;
605 }
606 // SAFETY: the run start is an in-bounds source slot.
607 let src_start = unsafe { src_ptr.offset(src_offset) };
608 for (position, dst) in dst_run.iter_mut().enumerate() {
609 // SAFETY: `position < len`, so this is a run source slot.
610 let value = unsafe { *src_start.offset(position as isize * src_stride) };
611 apply(dst, value);
612 }
613 return;
614 }
615 // SAFETY: the run start is an in-bounds slot of each allocation.
616 let dst_start = unsafe { dst_ptr.offset(dst_offset) };
617 let src_start = unsafe { src_ptr.offset(src_offset) };
618 // The bound stays `usize`: a checked broadcast run may hold more than
619 // `isize::MAX` elements, and `len as isize` would wrap to an empty loop.
620 for position in 0..len {
621 // INVARIANT: a nonzero stride bounds the run by its validated reach,
622 // so `position` fits `isize` exactly; a longer run is possible only
623 // along a zero stride, where the wrapped cast is multiplied by zero.
624 let position = position as isize;
625 // SAFETY: `position < len`, so both are slots of this run.
626 unsafe {
627 let value = *src_start.offset(position * src_stride);
628 apply(&mut *dst_start.offset(position * dst_stride), value);
629 }
630 }
631}
632
633fn ensure_same_dims(dst: &[usize], src: &[usize]) -> Result<()> {
634 if dst != src {
635 return Err(crate::StridedError::ShapeMismatch(
636 dst.to_vec(),
637 src.to_vec(),
638 ));
639 }
640 // Reject an element count beyond usize (a huge stride-0 broadcast)
641 // instead of replaying it.
642 crate::kernel::total_len(dst)?;
643 Ok(())
644}
645
646/// `dest = scale * src` over borrowed raw strided layouts.
647///
648/// # Errors
649///
650/// Returns [`crate::StridedError::ShapeMismatch`] when `dest` and `src` do
651/// not describe the same extents, or [`crate::StridedError::OffsetOverflow`]
652/// when the element count does not fit `usize`. Nothing is written on error.
653pub fn copy_scale_raw<T>(
654 dest: &mut RawStridedMut<'_, T>,
655 src: &RawStridedRef<'_, T>,
656 scale: T,
657) -> Result<()>
658where
659 T: Copy + Mul<T, Output = T> + ElementOpApply + Send + Sync,
660{
661 ensure_same_dims(dest.dims(), src.dims())?;
662 match fuse_pair_traversal(dest.dims(), dest.strides(), src.strides()) {
663 PairTraversal::Inline(layout) => {
664 apply_fused_pair(dest, src, &layout, |dst: &mut T, value: T| {
665 *dst = scale * value
666 })
667 }
668 PairTraversal::Spilled(axes) => {
669 apply_spilled_pair(dest, src, &axes, |dst: &mut T, value: T| {
670 *dst = scale * value
671 })
672 }
673 }
674 Ok(())
675}
676
677/// `dest = scale * conj(src)` over borrowed raw strided layouts.
678///
679/// # Errors
680///
681/// Returns [`crate::StridedError::ShapeMismatch`] when `dest` and `src` do
682/// not describe the same extents, or [`crate::StridedError::OffsetOverflow`]
683/// when the element count does not fit `usize`. Nothing is written on error.
684pub fn copy_scale_conj_raw<T>(
685 dest: &mut RawStridedMut<'_, T>,
686 src: &RawStridedRef<'_, T>,
687 scale: T,
688) -> Result<()>
689where
690 T: Copy + Mul<T, Output = T> + ElementOpApply + Send + Sync,
691{
692 ensure_same_dims(dest.dims(), src.dims())?;
693 match fuse_pair_traversal(dest.dims(), dest.strides(), src.strides()) {
694 PairTraversal::Inline(layout) => {
695 apply_fused_pair(dest, src, &layout, |dst: &mut T, value: T| {
696 *dst = scale * value.conj()
697 })
698 }
699 PairTraversal::Spilled(axes) => {
700 apply_spilled_pair(dest, src, &axes, |dst: &mut T, value: T| {
701 *dst = scale * value.conj()
702 })
703 }
704 }
705 Ok(())
706}
707
708/// `dest = alpha * src + dest` over borrowed raw strided layouts.
709///
710/// # Errors
711///
712/// Returns [`crate::StridedError::ShapeMismatch`] when `dest` and `src` do
713/// not describe the same extents, or [`crate::StridedError::OffsetOverflow`]
714/// when the element count does not fit `usize`. Nothing is written on error.
715pub fn axpy_raw<T>(
716 dest: &mut RawStridedMut<'_, T>,
717 src: &RawStridedRef<'_, T>,
718 alpha: T,
719) -> Result<()>
720where
721 T: Copy + Add<T, Output = T> + Mul<T, Output = T> + ElementOpApply + Send + Sync,
722{
723 ensure_same_dims(dest.dims(), src.dims())?;
724 match fuse_pair_traversal(dest.dims(), dest.strides(), src.strides()) {
725 PairTraversal::Inline(layout) => {
726 apply_fused_pair(dest, src, &layout, |dst: &mut T, value: T| {
727 *dst = *dst + alpha * value
728 })
729 }
730 PairTraversal::Spilled(axes) => {
731 apply_spilled_pair(dest, src, &axes, |dst: &mut T, value: T| {
732 *dst = *dst + alpha * value
733 })
734 }
735 }
736 Ok(())
737}
738
739/// `dest = alpha * conj(src) + dest` over borrowed raw strided layouts.
740///
741/// # Errors
742///
743/// Returns [`crate::StridedError::ShapeMismatch`] when `dest` and `src` do
744/// not describe the same extents, or [`crate::StridedError::OffsetOverflow`]
745/// when the element count does not fit `usize`. Nothing is written on error.
746pub fn axpy_conj_raw<T>(
747 dest: &mut RawStridedMut<'_, T>,
748 src: &RawStridedRef<'_, T>,
749 alpha: T,
750) -> Result<()>
751where
752 T: Copy + Add<T, Output = T> + Mul<T, Output = T> + ElementOpApply + Send + Sync,
753{
754 ensure_same_dims(dest.dims(), src.dims())?;
755 match fuse_pair_traversal(dest.dims(), dest.strides(), src.strides()) {
756 PairTraversal::Inline(layout) => {
757 apply_fused_pair(dest, src, &layout, |dst: &mut T, value: T| {
758 *dst = *dst + alpha * value.conj()
759 })
760 }
761 PairTraversal::Spilled(axes) => {
762 apply_spilled_pair(dest, src, &axes, |dst: &mut T, value: T| {
763 *dst = *dst + alpha * value.conj()
764 })
765 }
766 }
767 Ok(())
768}
769
770/// Checked replay of the given axes of two views: the shared body of the
771/// `replay_*_raw` entries.
772///
773/// The element count is checked before anything is built. The unfused
774/// traversal keeps every given extent, and the replay totals (`fused_total`,
775/// `replay_spilled_raw`) take an unchecked product, so the zero-first count
776/// of `kernel::total_len` has to keep an empty layout whose nonzero prefix
777/// overflows, such as `[usize::MAX, 2, 0]`, away from them.
778fn replay_given<D, S, Apply>(
779 dest: &mut RawStridedMut<'_, D>,
780 src: &RawStridedRef<'_, S>,
781 apply: Apply,
782 exec: Exec<'_>,
783) -> Result<()>
784where
785 D: Copy + Send + Sync,
786 S: Copy + Send + Sync,
787 Apply: Fn(&mut D, S) + Sync,
788{
789 ensure_same_dims(dest.dims(), src.dims())?;
790 let total = crate::kernel::total_len(dest.dims())?;
791 if total == 0 {
792 return Ok(());
793 }
794 let traversal = PairTraversal::given(dest.dims(), dest.strides(), src.strides());
795 let mut exec = crate::cost::for_len(exec, KernelClass::Copy, total);
796 if !exec.is_serial()
797 && !crate::layout_check::is_injective_layout_without_alloc(dest.dims(), dest.strides())
798 {
799 // A destination not proven injective replays as one sequential walk,
800 // which is also its defined semantics; the budget-one token cannot be
801 // widened again by the replay's own width rule.
802 exec = exec.limit(NonZeroUsize::MIN);
803 }
804 // SAFETY: `traversal` is built from exactly the views' dims and strides
805 // (`ensure_same_dims` proved the dims agree), so the views' bounds proofs
806 // cover every replayed offset; `total_len` checked the nonzero product;
807 // a non-serial `exec` is left only for a destination proven injective;
808 // the exclusive and shared borrows cannot overlap.
809 unsafe { crate::copy_plan::replay_fused(dest, src, &traversal, apply, exec) };
810 Ok(())
811}
812
813/// `dest = src`, replaying the axes of the two views exactly as given.
814///
815/// The views carry already-fused dims: no axis is reordered, dropped or
816/// merged, and no plan is compiled. Axis 0 is the inner run. Bounds were validated when the views were built
817/// ([`RawStridedRef::new`], [`RawStridedMut::new`]). On a successful call the
818/// replay itself (validation, traversal and dispatch) allocates nothing for a
819/// rank at most [`RAW_FUSED_RANK_LIMIT`]; above it, the axis list and the cursor
820/// of each replayed range are stored in rank-sized buffers. An error may
821/// allocate its payload.
822///
823/// The width comes from the repository rule on `exec`. A parallel replay runs
824/// only on a destination proven injective without allocating; any other
825/// destination is replayed serially in column-major order of the given axes.
826///
827/// # Errors
828///
829/// [`StridedError::ShapeMismatch`](crate::StridedError::ShapeMismatch) when the
830/// two views have different dims, and
831/// [`StridedError::OffsetOverflow`](crate::StridedError::OffsetOverflow) when the
832/// element count overflows `usize`; both before any write.
833///
834/// # Examples
835///
836/// Copy the outer band `1..3` of a stored `2 x 3` block into a transposed
837/// destination:
838///
839/// ```rust
840/// use strided_basic::{replay_copy_raw, Exec, RawStridedMut, RawStridedRef};
841///
842/// let stored = [0.0f64, 1.0, 2.0, 3.0, 4.0, 5.0]; // column-major 2 x 3
843/// let band = [2usize, 2];
844/// let src = RawStridedRef::new(&stored, &band, &[1, 2], 2).unwrap();
845/// let mut out = [0.0f64; 4];
846/// let mut dst = RawStridedMut::new(&mut out, &band, &[2, 1], 0).unwrap();
847/// replay_copy_raw(&mut dst, &src, Exec::serial()).unwrap();
848/// assert_eq!(out, [2.0, 4.0, 3.0, 5.0]);
849/// ```
850pub fn replay_copy_raw<T>(
851 dest: &mut RawStridedMut<'_, T>,
852 src: &RawStridedRef<'_, T>,
853 exec: Exec<'_>,
854) -> Result<()>
855where
856 T: Copy + Send + Sync,
857{
858 replay_given(dest, src, |dst: &mut T, value: T| *dst = value, exec)
859}
860
861/// [`replay_copy_raw`] into a potentially uninitialized destination.
862///
863/// On success every reachable destination element is initialized and no
864/// other slot is written. The destination is never read.
865///
866/// # Errors
867///
868/// As [`replay_copy_raw`].
869///
870/// # Examples
871///
872/// ```rust
873/// use core::mem::MaybeUninit;
874/// use strided_basic::{replay_copy_raw_uninit, Exec, RawStridedMut, RawStridedRef};
875///
876/// let src = [1.0f64, 2.0, 3.0];
877/// let mut storage = [MaybeUninit::<f64>::uninit(); 3];
878/// let mut dst = RawStridedMut::new(&mut storage, &[3], &[1], 0).unwrap();
879/// let source = RawStridedRef::new(&src, &[3], &[-1], 2).unwrap();
880/// replay_copy_raw_uninit(&mut dst, &source, Exec::serial()).unwrap();
881/// drop(dst);
882/// // SAFETY: every reachable destination slot was initialized above.
883/// let values: Vec<f64> = storage.iter().map(|v| unsafe { v.assume_init() }).collect();
884/// assert_eq!(values, [3.0, 2.0, 1.0]);
885/// ```
886pub fn replay_copy_raw_uninit<T>(
887 dest: &mut RawStridedMut<'_, MaybeUninit<T>>,
888 src: &RawStridedRef<'_, T>,
889 exec: Exec<'_>,
890) -> Result<()>
891where
892 T: Copy + Send + Sync,
893{
894 replay_given(
895 dest,
896 src,
897 |dst: &mut MaybeUninit<T>, value: T| {
898 dst.write(value);
899 },
900 exec,
901 )
902}
903
904/// `f(&mut dest[i], src[i])` for every element, replaying the axes of the two
905/// views exactly as given.
906///
907/// Traversal, width and errors are those of [`replay_copy_raw`], and so is the
908/// allocation guarantee, which covers the replay only: allocations made by `f`
909/// are its own. `f` runs once per logical element with exactly its arithmetic,
910/// so an accumulate such as `|d, s| *d += s` is exact. The order in which
911/// elements are visited is unspecified, and on a parallel replay `f` runs
912/// concurrently on disjoint slots: the result is defined only for an `f` whose
913/// effect depends on the supplied slot values alone. On a destination that is
914/// not proven injective, the elements are visited serially in column-major
915/// order of the given axes.
916///
917/// # Errors
918///
919/// As [`replay_copy_raw`].
920///
921/// # Examples
922///
923/// ```rust
924/// use strided_basic::{replay_map_raw, Exec, RawStridedMut, RawStridedRef};
925///
926/// let src = [1.0f64, 2.0, 3.0, 4.0];
927/// let mut acc = [10.0f64, 20.0, 30.0, 40.0];
928/// let source = RawStridedRef::new(&src, &[2, 2], &[2, 1], 0).unwrap();
929/// let mut dst = RawStridedMut::new(&mut acc, &[2, 2], &[1, 2], 0).unwrap();
930/// replay_map_raw(&mut dst, &source, |d, s| *d += s, Exec::serial()).unwrap();
931/// assert_eq!(acc, [11.0, 23.0, 32.0, 44.0]);
932/// ```
933pub fn replay_map_raw<D, S, F>(
934 dest: &mut RawStridedMut<'_, D>,
935 src: &RawStridedRef<'_, S>,
936 f: F,
937 exec: Exec<'_>,
938) -> Result<()>
939where
940 D: Copy + Send + Sync,
941 S: Copy + Send + Sync,
942 F: Fn(&mut D, S) + Send + Sync,
943{
944 replay_given(dest, src, f, exec)
945}
946
947/// `dest[i] = f(src[i])` into a potentially uninitialized destination.
948///
949/// `f` cannot read the destination. On success every reachable destination
950/// element is initialized and no other slot is written. The visit-order,
951/// callback and allocation contract is that of [`replay_map_raw`].
952///
953/// # Errors
954///
955/// As [`replay_copy_raw`].
956///
957/// # Examples
958///
959/// ```rust
960/// use core::mem::MaybeUninit;
961/// use strided_basic::{replay_map_raw_uninit, Exec, RawStridedMut, RawStridedRef};
962///
963/// let src = [1i32, 2, 3];
964/// let mut storage = [MaybeUninit::<f64>::uninit(); 3];
965/// let mut dst = RawStridedMut::new(&mut storage, &[3], &[1], 0).unwrap();
966/// let source = RawStridedRef::new(&src, &[3], &[1], 0).unwrap();
967/// replay_map_raw_uninit(&mut dst, &source, |s| f64::from(s) * 0.5, Exec::serial()).unwrap();
968/// drop(dst);
969/// // SAFETY: every reachable destination slot was initialized above.
970/// let values: Vec<f64> = storage.iter().map(|v| unsafe { v.assume_init() }).collect();
971/// assert_eq!(values, [0.5, 1.0, 1.5]);
972/// ```
973pub fn replay_map_raw_uninit<D, S, F>(
974 dest: &mut RawStridedMut<'_, MaybeUninit<D>>,
975 src: &RawStridedRef<'_, S>,
976 f: F,
977 exec: Exec<'_>,
978) -> Result<()>
979where
980 D: Copy + Send + Sync,
981 S: Copy + Send + Sync,
982 F: Fn(S) -> D + Send + Sync,
983{
984 replay_given(
985 dest,
986 src,
987 move |dst: &mut MaybeUninit<D>, value: S| {
988 dst.write(f(value));
989 },
990 exec,
991 )
992}
993
994#[cfg(test)]
995#[path = "raw_ops/tests/tests.rs"]
996mod tests;
997
998#[cfg(test)]
999#[path = "raw_ops/tests/replay_tests.rs"]
1000mod replay_tests;