1use core::{mem::MaybeUninit, ops::Add};
9
10use crate::copy_plan::{replay_fused_raw, CopyPlan, OverwriteWriter, ReadModifyWrite};
11use crate::cost::KernelClass;
12use crate::inline::InlineVec;
13use crate::raw_ops::pair_tiles;
14use crate::raw_ops::{fuse_pair_layout, FusedPairLayout};
15use crate::{Exec, RawStridedMut, RawStridedRef, Result, StridedError, RAW_FUSED_RANK_LIMIT};
16
17type AxisVec<T> = InlineVec<T>;
18
19#[derive(Clone, Debug, Eq, PartialEq)]
31pub struct GatherSpec {
32 pub offset_dims: Vec<usize>,
33 pub collapsed_slice_dims: Vec<usize>,
34 pub start_index_map: Vec<usize>,
35 pub index_vector_dim: usize,
36 pub slice_sizes: Vec<usize>,
37}
38
39pub trait GatherIndex: Copy + Send + Sync {
41 fn to_i64(self) -> i64;
42}
43
44impl GatherIndex for i32 {
45 #[inline]
46 fn to_i64(self) -> i64 {
47 i64::from(self)
48 }
49}
50
51impl GatherIndex for i64 {
52 #[inline]
53 fn to_i64(self) -> i64 {
54 self
55 }
56}
57
58#[derive(Clone, Debug)]
60pub struct GatherPlan {
61 operand_dims: AxisVec<usize>,
62 operand_strides: AxisVec<isize>,
63 index_dims: AxisVec<usize>,
64 index_strides: AxisVec<isize>,
65 dest_dims: AxisVec<usize>,
66 dest_strides: AxisVec<isize>,
67 spec: GatherSpec,
68 replay: GatherReplay,
69 total: usize,
70}
71
72#[derive(Clone, Copy, Debug, Default)]
73struct GatherReplayAxis {
74 dest_step: isize,
75 dest_reset: isize,
76 window_step: isize,
77 window_reset: isize,
78 index_batch_step: isize,
79 index_batch_reset: isize,
80}
81
82#[derive(Clone, Debug)]
83struct GatherReplay {
84 axes: AxisVec<GatherReplayAxis>,
85 index_component_offsets: AxisVec<isize>,
86 index_operand_strides: AxisVec<isize>,
87}
88
89struct GatherReplayState {
90 coords: AxisVec<usize>,
91 dest_offset: isize,
92 window_offset: isize,
93 index_batch_offset: isize,
94}
95
96#[derive(Clone, Copy, Debug, Default)]
97struct WindowReplayAxis {
98 source_step: isize,
99 source_reset: isize,
100 dest_step: isize,
101 dest_reset: isize,
102}
103
104#[derive(Clone, Copy, Debug, Default)]
106struct OffsetSpan {
107 min: isize,
108 max: isize,
109}
110
111impl OffsetSpan {
112 fn covers(&self, base: isize) -> Result<()> {
114 base.checked_add(self.min)
115 .ok_or(StridedError::OffsetOverflow)?;
116 base.checked_add(self.max)
117 .ok_or(StridedError::OffsetOverflow)?;
118 Ok(())
119 }
120}
121
122#[derive(Clone, Debug)]
123struct WindowReplay {
124 shape: AxisVec<usize>,
125 axes: AxisVec<WindowReplayAxis>,
126 source_span: OffsetSpan,
130 dest_span: OffsetSpan,
131}
132
133struct WindowReplayState {
134 coords: CoordScratch,
135 source_offset: isize,
136 dest_offset: isize,
137}
138
139#[derive(Clone, Debug)]
140struct ScatterReplay {
141 batch: WindowReplay,
142 window: WindowReplay,
143 index_component_offsets: AxisVec<isize>,
144}
145
146impl ScatterReplay {
147 #[allow(clippy::too_many_arguments)]
150 fn compile(
151 batch_shape: &[usize],
152 index_dims: &[usize],
153 index_strides: &[isize],
154 index_vector_dim: usize,
155 index_component_count: usize,
156 update_dims: &[usize],
157 update_strides: &[isize],
158 update_window_dims: &[usize],
159 is_update_window_dim: &[bool],
160 window_shape_updates: &[usize],
161 window_dims: &[usize],
162 dest_strides: &[isize],
163 ) -> Result<Self> {
164 let (
165 batch_source_strides,
166 batch_dest_strides,
167 window_source_strides,
168 window_dest_strides,
169 vector_stride,
170 ) = scatter_replay_strides(
171 index_dims,
172 index_strides,
173 index_vector_dim,
174 update_dims,
175 update_strides,
176 update_window_dims,
177 is_update_window_dim,
178 window_dims,
179 dest_strides,
180 );
181 let batch = WindowReplay::compile(batch_shape, &batch_source_strides, &batch_dest_strides)?;
182 let window = WindowReplay::compile(
183 window_shape_updates,
184 &window_source_strides,
185 &window_dest_strides,
186 )?;
187 let mut index_component_offsets = AxisVec::with_capacity(index_component_count);
188 for component in 0..index_component_count {
189 index_component_offsets.push(checked_offset_add(0, vector_stride, component)?);
190 }
191 Ok(Self {
192 batch,
193 window,
194 index_component_offsets,
195 })
196 }
197}
198
199#[allow(clippy::too_many_arguments)]
202fn scatter_replay_strides(
203 index_dims: &[usize],
204 index_strides: &[isize],
205 index_vector_dim: usize,
206 update_dims: &[usize],
207 update_strides: &[isize],
208 update_window_dims: &[usize],
209 is_update_window_dim: &[bool],
210 window_dims: &[usize],
211 dest_strides: &[isize],
212) -> (
213 AxisVec<isize>,
214 AxisVec<isize>,
215 AxisVec<isize>,
216 AxisVec<isize>,
217 isize,
218) {
219 let batch_source_strides = index_dims
220 .iter()
221 .zip(index_strides.iter())
222 .enumerate()
223 .filter_map(|(axis, (_, &stride))| (axis != index_vector_dim).then_some(stride))
224 .collect();
225 let batch_dest_strides = update_dims
226 .iter()
227 .zip(update_strides.iter())
228 .enumerate()
229 .filter_map(|(axis, (_, &stride))| (!is_update_window_dim[axis]).then_some(stride))
230 .collect();
231 let window_source_strides = update_window_dims
232 .iter()
233 .map(|&axis| update_strides[axis])
234 .collect();
235 let window_dest_strides = window_dims.iter().map(|&axis| dest_strides[axis]).collect();
236 let vector_stride = if index_vector_dim < index_dims.len() {
237 index_strides[index_vector_dim]
238 } else {
239 0
240 };
241 (
242 batch_source_strides,
243 batch_dest_strides,
244 window_source_strides,
245 window_dest_strides,
246 vector_stride,
247 )
248}
249
250impl WindowReplay {
251 fn compile(shape: &[usize], source_strides: &[isize], dest_strides: &[isize]) -> Result<Self> {
252 let source_span = validate_layout_span(shape, source_strides)?;
253 let dest_span = validate_layout_span(shape, dest_strides)?;
254 let mut fused_shape: AxisVec<usize> = AxisVec::with_capacity(shape.len());
255 let mut axes: AxisVec<WindowReplayAxis> = AxisVec::with_capacity(shape.len());
256 for (axis, &dim) in shape.iter().enumerate() {
257 let source_step = source_strides[axis];
258 let dest_step = dest_strides[axis];
259 if let Some(previous_axis) = fused_shape.len().checked_sub(1) {
260 let previous_extent = fused_shape[previous_axis];
261 let previous_extent =
262 isize::try_from(previous_extent).map_err(|_| StridedError::OffsetOverflow)?;
263 let expected_source = axes[previous_axis]
264 .source_step
265 .checked_mul(previous_extent)
266 .ok_or(StridedError::OffsetOverflow)?;
267 let expected_dest = axes[previous_axis]
268 .dest_step
269 .checked_mul(previous_extent)
270 .ok_or(StridedError::OffsetOverflow)?;
271 if source_step == expected_source && dest_step == expected_dest {
272 let fused_extent = fused_shape[previous_axis]
273 .checked_mul(dim)
274 .ok_or(StridedError::OffsetOverflow)?;
275 fused_shape[previous_axis] = fused_extent;
276 axes[previous_axis].source_reset =
277 checked_replay_reset(fused_extent, axes[previous_axis].source_step)?;
278 axes[previous_axis].dest_reset =
279 checked_replay_reset(fused_extent, axes[previous_axis].dest_step)?;
280 continue;
281 }
282 }
283 fused_shape.push(dim);
284 axes.push(WindowReplayAxis {
285 source_step,
286 source_reset: checked_replay_reset(dim, source_step)?,
287 dest_step,
288 dest_reset: checked_replay_reset(dim, dest_step)?,
289 });
290 }
291 Ok(Self {
292 shape: fused_shape,
293 axes,
294 source_span,
295 dest_span,
296 })
297 }
298
299 fn start(&self, source_base: isize, dest_base: isize) -> WindowReplayState {
303 WindowReplayState {
304 coords: CoordScratch::new(self.shape.len()),
305 source_offset: source_base,
306 dest_offset: dest_base,
307 }
308 }
309
310 fn decode(
311 &self,
312 mut linear: usize,
313 source_base: isize,
314 dest_base: isize,
315 ) -> Result<WindowReplayState> {
316 let mut coords = CoordScratch::new(self.shape.len());
317 let mut source_offset = source_base;
318 let mut dest_offset = dest_base;
319 for (axis, (&dim, coord)) in self
320 .shape
321 .iter()
322 .zip(coords.as_mut_slice().iter_mut())
323 .enumerate()
324 {
325 *coord = linear % dim;
326 linear /= dim;
327 let replay_axis = self.axes[axis];
328 source_offset = checked_offset_add(source_offset, replay_axis.source_step, *coord)?;
329 dest_offset = checked_offset_add(dest_offset, replay_axis.dest_step, *coord)?;
330 }
331 Ok(WindowReplayState {
332 coords,
333 source_offset,
334 dest_offset,
335 })
336 }
337
338 #[inline]
339 fn advance(&self, state: &mut WindowReplayState) {
340 for ((coord, &dim), replay_axis) in state
341 .coords
342 .as_mut_slice()
343 .iter_mut()
344 .zip(self.shape.iter())
345 .zip(self.axes.iter())
346 {
347 let next = *coord + 1;
348 if next < dim {
349 *coord = next;
350 state.source_offset += replay_axis.source_step;
351 state.dest_offset += replay_axis.dest_step;
352 return;
353 }
354 *coord = 0;
355 state.source_offset += replay_axis.source_reset;
356 state.dest_offset += replay_axis.dest_reset;
357 }
358 }
359}
360
361#[derive(Clone, Debug, Eq, PartialEq)]
367pub struct ScatterSpec {
368 pub update_window_dims: Vec<usize>,
369 pub inserted_window_dims: Vec<usize>,
370 pub scatter_dims_to_operand_dims: Vec<usize>,
371 pub index_vector_dim: usize,
372}
373
374#[derive(Clone, Debug)]
376pub struct DynamicSlicePlan {
377 operand_dims: AxisVec<usize>,
378 operand_strides: AxisVec<isize>,
379 start_dims: AxisVec<usize>,
380 start_strides: AxisVec<isize>,
381 dest_dims: AxisVec<usize>,
382 dest_strides: AxisVec<isize>,
383 slice_sizes: AxisVec<usize>,
384 total: usize,
385 window: Option<FusedPairLayout>,
390 replay: WindowReplay,
391}
392
393#[derive(Clone, Debug)]
399pub struct DynamicUpdateSlicePlan {
400 operand_dims: AxisVec<usize>,
401 operand_strides: AxisVec<isize>,
402 start_dims: AxisVec<usize>,
403 start_strides: AxisVec<isize>,
404 update_dims: AxisVec<usize>,
405 update_strides: AxisVec<isize>,
406 dest_dims: AxisVec<usize>,
407 dest_strides: AxisVec<isize>,
408 total: usize,
409 copy_plan: CopyPlan,
410 window: Option<FusedPairLayout>,
415 replay: WindowReplay,
416}
417
418enum UpdateWindow<'a, T> {
426 Empty,
428 RankOne { update: &'a [T], dest_start: usize },
431 Replay { dest_base: isize },
434}
435
436#[derive(Clone, Debug)]
442pub struct ScatterPlan {
443 operand_dims: AxisVec<usize>,
444 operand_strides: AxisVec<isize>,
445 index_dims: AxisVec<usize>,
446 index_strides: AxisVec<isize>,
447 update_dims: AxisVec<usize>,
448 update_strides: AxisVec<isize>,
449 dest_dims: AxisVec<usize>,
450 dest_strides: AxisVec<isize>,
451 spec: ScatterSpec,
452 window_shape: AxisVec<usize>,
453 batch_elems: usize,
454 window_elems: usize,
455 copy_plan: CopyPlan,
456 replay: ScatterReplay,
457}
458
459impl GatherPlan {
460 pub fn compile(
479 operand_dims: &[usize],
480 operand_strides: &[isize],
481 index_dims: &[usize],
482 index_strides: &[isize],
483 dest_dims: &[usize],
484 dest_strides: &[isize],
485 spec: GatherSpec,
486 ) -> Result<Self> {
487 if operand_dims.len() != operand_strides.len()
488 || index_dims.len() != index_strides.len()
489 || dest_dims.len() != dest_strides.len()
490 {
491 return Err(StridedError::StrideLengthMismatch);
492 }
493 checked_total_len(operand_dims)?;
494 checked_total_len(index_dims)?;
495 let total = checked_total_len(dest_dims)?;
496 validate_layout_span(operand_dims, operand_strides)?;
497 validate_layout_span(index_dims, index_strides)?;
498 validate_layout_span(dest_dims, dest_strides)?;
499 if !crate::layout_check::is_injective_layout(dest_dims, dest_strides) {
500 return Err(StridedError::NonInjectiveOutputLayout);
501 }
502
503 let operand_rank = operand_dims.len();
504 if spec.slice_sizes.len() != operand_rank {
505 return Err(StridedError::RankMismatch(
506 spec.slice_sizes.len(),
507 operand_rank,
508 ));
509 }
510 validate_unique_axes(&spec.collapsed_slice_dims, operand_rank)?;
511 validate_unique_axes(&spec.start_index_map, operand_rank)?;
512 if spec.index_vector_dim > index_dims.len() {
513 return Err(StridedError::InvalidAxis {
514 axis: spec.index_vector_dim,
515 rank: index_dims.len() + 1,
516 });
517 }
518
519 for (axis, (&window, &dim)) in spec.slice_sizes.iter().zip(operand_dims.iter()).enumerate()
520 {
521 if window > dim {
522 return Err(StridedError::InvalidAxis {
523 axis,
524 rank: operand_rank,
525 });
526 }
527 }
528 for &axis in &spec.collapsed_slice_dims {
529 if spec.slice_sizes[axis] != 1 {
530 return Err(StridedError::InvalidAxis {
531 axis,
532 rank: operand_rank,
533 });
534 }
535 }
536
537 let index_vector_size = if spec.index_vector_dim == index_dims.len() {
538 1
539 } else {
540 index_dims[spec.index_vector_dim]
541 };
542 if index_vector_size != spec.start_index_map.len() {
543 return Err(StridedError::RankMismatch(
544 index_vector_size,
545 spec.start_index_map.len(),
546 ));
547 }
548
549 let window_dims = operand_window_dims(operand_rank, &spec.collapsed_slice_dims);
550 if spec.offset_dims.len() != window_dims.len() {
551 return Err(StridedError::RankMismatch(
552 spec.offset_dims.len(),
553 window_dims.len(),
554 ));
555 }
556
557 let batch_shape = index_batch_shape(index_dims, spec.index_vector_dim);
558 let out_rank = batch_shape.len() + spec.offset_dims.len();
559 validate_unique_axes(&spec.offset_dims, out_rank)?;
560
561 let mut out_axis_to_operand_dim: AxisVec<Option<usize>> =
562 (0..out_rank).map(|_| None).collect();
563 for (offset_axis, &out_axis) in spec.offset_dims.iter().enumerate() {
564 out_axis_to_operand_dim[out_axis] = Some(window_dims[offset_axis]);
565 }
566
567 let mut expected_dest_dims: AxisVec<usize> = AxisVec::with_capacity(out_rank);
568 let mut batch_axis = 0usize;
569 for &operand_dim in &out_axis_to_operand_dim {
570 match operand_dim {
571 Some(axis) => expected_dest_dims.push(spec.slice_sizes[axis]),
572 None => {
573 expected_dest_dims.push(batch_shape[batch_axis]);
574 batch_axis += 1;
575 }
576 }
577 }
578 if dest_dims != &expected_dest_dims[..] {
579 return Err(StridedError::ShapeMismatch(
580 dest_dims.to_vec(),
581 expected_dest_dims.to_vec(),
582 ));
583 }
584
585 let batch_index_strides: AxisVec<isize> = index_dims
586 .iter()
587 .zip(index_strides.iter())
588 .enumerate()
589 .filter_map(|(axis, (_, &stride))| (axis != spec.index_vector_dim).then_some(stride))
590 .collect();
591 let mut batch_axis = 0usize;
592 let mut replay_axes = AxisVec::with_capacity(out_rank);
593 for (out_axis, &operand_dim) in out_axis_to_operand_dim.iter().enumerate() {
594 let (window_step, index_batch_step) = match operand_dim {
595 Some(axis) => (operand_strides[axis], 0),
596 None => {
597 let step = batch_index_strides[batch_axis];
598 batch_axis += 1;
599 (0, step)
600 }
601 };
602 replay_axes.push(GatherReplayAxis {
603 dest_step: dest_strides[out_axis],
604 dest_reset: checked_replay_reset(dest_dims[out_axis], dest_strides[out_axis])?,
605 window_step,
606 window_reset: checked_replay_reset(dest_dims[out_axis], window_step)?,
607 index_batch_step,
608 index_batch_reset: checked_replay_reset(dest_dims[out_axis], index_batch_step)?,
609 });
610 }
611
612 let vector_stride = if spec.index_vector_dim < index_dims.len() {
613 index_strides[spec.index_vector_dim]
614 } else {
615 0
616 };
617 let mut index_component_offsets = AxisVec::with_capacity(spec.start_index_map.len());
618 for component in 0..spec.start_index_map.len() {
619 index_component_offsets.push(checked_offset_add(0, vector_stride, component)?);
620 }
621
622 let index_operand_strides: AxisVec<isize> = spec
623 .start_index_map
624 .iter()
625 .map(|&axis| operand_strides[axis])
626 .collect();
627
628 Ok(Self {
629 operand_dims: operand_dims.into(),
630 operand_strides: operand_strides.into(),
631 index_dims: index_dims.into(),
632 index_strides: index_strides.into(),
633 dest_dims: dest_dims.into(),
634 dest_strides: dest_strides.into(),
635 spec,
636 replay: GatherReplay {
637 axes: replay_axes,
638 index_component_offsets,
639 index_operand_strides,
640 },
641 total,
642 })
643 }
644
645 #[inline]
646 pub fn spec(&self) -> &GatherSpec {
647 &self.spec
648 }
649
650 #[inline]
651 pub fn dest_dims(&self) -> &[usize] {
652 &self.dest_dims
653 }
654
655 pub fn execute<T, I>(
669 &self,
670 dest: &mut RawStridedMut<'_, T>,
671 operand: &RawStridedRef<'_, T>,
672 start_indices: &RawStridedRef<'_, I>,
673 exec: Exec<'_>,
674 ) -> Result<()>
675 where
676 T: Copy + Send + Sync,
677 I: GatherIndex,
678 {
679 self.execute_with_writer(dest, operand, start_indices, exec)
680 }
681
682 pub(crate) fn execute_uninit<T, I>(
685 &self,
686 dest: &mut RawStridedMut<'_, MaybeUninit<T>>,
687 operand: &RawStridedRef<'_, T>,
688 start_indices: &RawStridedRef<'_, I>,
689 exec: Exec<'_>,
690 ) -> Result<()>
691 where
692 T: Copy + Send + Sync,
693 I: GatherIndex,
694 {
695 self.execute_with_writer(dest, operand, start_indices, exec)
696 }
697
698 fn execute_with_writer<T, I, W>(
699 &self,
700 dest: &mut W,
701 operand: &RawStridedRef<'_, T>,
702 start_indices: &RawStridedRef<'_, I>,
703 exec: Exec<'_>,
704 ) -> Result<()>
705 where
706 T: Copy + Send + Sync,
707 I: GatherIndex,
708 W: OverwriteWriter<T>,
709 {
710 self.check_call(dest, operand, start_indices)?;
711 if self.total == 0 {
712 return Ok(());
713 }
714 if self.uses_rank_one_scalar_take_path() {
715 let exec = crate::cost::for_len_tree(exec, KernelClass::Copy, self.total);
716 if !exec.is_serial() {
717 return self.execute_rank_one_scalar_take_parallel(
718 dest,
719 operand,
720 start_indices,
721 exec,
722 );
723 }
724 return self.execute_rank_one_scalar_take(dest, operand, start_indices);
725 }
726 let exec = crate::cost::for_len_tree(exec, KernelClass::Copy, self.total);
727 if !exec.is_serial() {
728 return self.execute_parallel(dest, operand, start_indices, exec);
729 }
730
731 let mut state =
732 self.decode_replay_state(0, dest.offset(), operand.offset(), start_indices.offset())?;
733 let operand_data = operand.data();
734 let index_data = start_indices.data();
735
736 for _ in 0..self.total {
740 let mut source_offset = state.window_offset;
745 for ((&index_component_offset, &operand_stride), &operand_dim) in self
746 .replay
747 .index_component_offsets
748 .iter()
749 .zip(self.replay.index_operand_strides.iter())
750 .zip(self.spec.start_index_map.iter())
751 {
752 let index_offset = state.index_batch_offset + index_component_offset;
753 let start = unsafe { *index_data.as_ptr().offset(index_offset) }.to_i64();
756 let clamped = self.clamp_window_start(start, operand_dim);
757 source_offset += operand_stride * clamped as isize;
758 }
759
760 let value = unsafe { *operand_data.as_ptr().offset(source_offset) };
763 unsafe { dest.write_at(state.dest_offset, value) };
764 self.advance_replay_state(&mut state);
765 }
766 Ok(())
767 }
768
769 fn uses_rank_one_scalar_take_path(&self) -> bool {
770 self.operand_dims.len() == 1
771 && self.index_dims.len() == 1
772 && self.dest_dims.len() == 1
773 && self.operand_strides[0] == 1
774 && self.index_strides[0] == 1
775 && self.dest_strides[0] == 1
776 && self.spec.offset_dims.is_empty()
777 && self.spec.collapsed_slice_dims.as_slice() == [0]
778 && self.spec.start_index_map.as_slice() == [0]
779 && self.spec.index_vector_dim == 1
780 && self.spec.slice_sizes.as_slice() == [1]
781 }
782
783 fn execute_rank_one_scalar_take<T, I, W>(
784 &self,
785 dest: &mut W,
786 operand: &RawStridedRef<'_, T>,
787 start_indices: &RawStridedRef<'_, I>,
788 ) -> Result<()>
789 where
790 T: Copy,
791 I: GatherIndex,
792 W: OverwriteWriter<T>,
793 {
794 let mut dest_offset = dest.offset();
795 let mut index_offset = start_indices.offset();
796 let operand_offset = operand.offset();
797 let operand_data = operand.data();
798 let index_data = start_indices.data();
799
800 #[allow(clippy::explicit_counter_loop)]
805 for _ in 0..self.total {
806 unsafe {
808 let start = (*index_data.as_ptr().offset(index_offset)).to_i64();
809 let source_offset = operand_offset + self.clamp_window_start(start, 0) as isize;
810 dest.write_at(dest_offset, *operand_data.as_ptr().offset(source_offset));
811 }
812 dest_offset += 1;
813 index_offset += 1;
814 }
815 Ok(())
816 }
817
818 fn execute_rank_one_scalar_take_parallel<T, I, W>(
819 &self,
820 dest: &mut W,
821 operand: &RawStridedRef<'_, T>,
822 start_indices: &RawStridedRef<'_, I>,
823 exec: Exec<'_>,
824 ) -> Result<()>
825 where
826 T: Copy + Send + Sync,
827 I: GatherIndex,
828 W: OverwriteWriter<T>,
829 {
830 let dest_offset = dest.offset();
831 let operand_offset = operand.offset();
832 let index_offset = start_indices.offset();
833 let dest_ptr = crate::threading::SendPtr(unsafe { dest.data_ptr() });
835 let operand_ptr = crate::threading::SendPtr(operand.data().as_ptr() as *mut T);
836 let index_ptr = crate::threading::SendPtr(start_indices.data().as_ptr() as *mut I);
837
838 crate::threading::parallel_map_reduce(
839 0..self.total,
840 exec,
841 &|range| {
842 let dest_ptr = dest_ptr.as_ptr();
843 let operand_ptr = operand_ptr.as_const();
844 let index_ptr = index_ptr.as_const();
845 for position in range {
848 let position = position as isize;
849 unsafe {
852 let start = (*index_ptr.offset(index_offset + position)).to_i64();
853 let source_offset =
854 operand_offset + self.clamp_window_start(start, 0) as isize;
855 dest_ptr
856 .offset(dest_offset + position)
857 .write(operand_ptr.offset(source_offset).read());
858 }
859 }
860 Ok(())
861 },
862 &|left, right| left.and(right),
863 )
864 }
865
866 fn execute_parallel<T, I, W>(
867 &self,
868 dest: &mut W,
869 operand: &RawStridedRef<'_, T>,
870 start_indices: &RawStridedRef<'_, I>,
871 exec: Exec<'_>,
872 ) -> Result<()>
873 where
874 T: Copy + Send + Sync,
875 I: GatherIndex,
876 W: OverwriteWriter<T>,
877 {
878 let dest_offset_base = dest.offset();
879 let operand_offset_base = operand.offset();
880 let index_offset_base = start_indices.offset();
881 let dest_ptr = crate::threading::SendPtr(unsafe { dest.data_ptr() });
883 let operand_ptr = crate::threading::SendPtr(operand.data().as_ptr() as *mut T);
884 let index_ptr = crate::threading::SendPtr(start_indices.data().as_ptr() as *mut I);
885
886 crate::threading::parallel_map_reduce(
887 0..self.total,
888 exec,
889 &|range| {
890 let mut state = self.decode_replay_state(
891 range.start,
892 dest_offset_base,
893 operand_offset_base,
894 index_offset_base,
895 )?;
896 let dest_ptr = dest_ptr.as_ptr();
897 let operand_ptr = operand_ptr.as_const();
898 let index_ptr = index_ptr.as_const();
899
900 for _ in range {
905 let mut source_offset = state.window_offset;
909 for ((&index_component_offset, &operand_stride), &operand_dim) in self
910 .replay
911 .index_component_offsets
912 .iter()
913 .zip(self.replay.index_operand_strides.iter())
914 .zip(self.spec.start_index_map.iter())
915 {
916 let index_offset = state.index_batch_offset + index_component_offset;
917 let start = unsafe { (*index_ptr.offset(index_offset)).to_i64() };
920 let clamped = self.clamp_window_start(start, operand_dim);
921 source_offset += operand_stride * clamped as isize;
922 }
923
924 unsafe {
927 dest_ptr
928 .offset(state.dest_offset)
929 .write(operand_ptr.offset(source_offset).read());
930 }
931 self.advance_replay_state(&mut state);
932 }
933 Ok(())
934 },
935 &|left, right| left.and(right),
936 )
937 }
938
939 fn check_call<T, I, W>(
940 &self,
941 dest: &W,
942 operand: &RawStridedRef<'_, T>,
943 start_indices: &RawStridedRef<'_, I>,
944 ) -> Result<()>
945 where
946 W: OverwriteWriter<T>,
947 {
948 if dest.dims() != &self.dest_dims[..]
949 || dest.strides() != &self.dest_strides[..]
950 || operand.dims() != &self.operand_dims[..]
951 || operand.strides() != &self.operand_strides[..]
952 || start_indices.dims() != &self.index_dims[..]
953 || start_indices.strides() != &self.index_strides[..]
954 {
955 return Err(StridedError::PlanLayoutMismatch);
956 }
957 Ok(())
958 }
959
960 fn decode_replay_state(
961 &self,
962 mut linear: usize,
963 dest_offset_base: isize,
964 operand_offset_base: isize,
965 index_offset_base: isize,
966 ) -> Result<GatherReplayState> {
967 let mut coords = AxisVec::with_capacity(self.dest_dims.len());
968 let mut dest_offset = dest_offset_base;
969 let mut window_offset = operand_offset_base;
970 let mut index_batch_offset = index_offset_base;
971 for (axis, &dim) in self.dest_dims.iter().enumerate() {
972 let coord = linear % dim;
973 linear /= dim;
974 let replay_axis = self.replay.axes[axis];
975 coords.push(coord);
976 dest_offset = checked_offset_add(dest_offset, replay_axis.dest_step, coord)?;
977 window_offset = checked_offset_add(window_offset, replay_axis.window_step, coord)?;
978 index_batch_offset =
979 checked_offset_add(index_batch_offset, replay_axis.index_batch_step, coord)?;
980 }
981 Ok(GatherReplayState {
982 coords,
983 dest_offset,
984 window_offset,
985 index_batch_offset,
986 })
987 }
988
989 #[inline]
990 fn advance_replay_state(&self, state: &mut GatherReplayState) {
991 for (axis, replay_axis) in self.replay.axes.iter().enumerate() {
992 let coord = state.coords[axis];
993 if coord + 1 < self.dest_dims[axis] {
994 state.coords[axis] = coord + 1;
995 state.dest_offset += replay_axis.dest_step;
996 state.window_offset += replay_axis.window_step;
997 state.index_batch_offset += replay_axis.index_batch_step;
998 return;
999 }
1000 state.coords[axis] = 0;
1001 state.dest_offset += replay_axis.dest_reset;
1002 state.window_offset += replay_axis.window_reset;
1003 state.index_batch_offset += replay_axis.index_batch_reset;
1004 }
1005 }
1006
1007 #[inline]
1008 fn clamp_window_start(&self, start: i64, operand_dim: usize) -> usize {
1009 let dim_size = self.operand_dims[operand_dim];
1010 let window_size = self.spec.slice_sizes[operand_dim];
1011 let max_start = dim_size.saturating_sub(window_size) as i64;
1012 start.clamp(0, max_start) as usize
1013 }
1014}
1015
1016impl DynamicSlicePlan {
1017 pub fn compile(
1036 operand_dims: &[usize],
1037 operand_strides: &[isize],
1038 start_dims: &[usize],
1039 start_strides: &[isize],
1040 dest_dims: &[usize],
1041 dest_strides: &[isize],
1042 slice_sizes: &[usize],
1043 ) -> Result<Self> {
1044 if operand_dims.len() != operand_strides.len()
1045 || start_dims.len() != start_strides.len()
1046 || dest_dims.len() != dest_strides.len()
1047 {
1048 return Err(StridedError::StrideLengthMismatch);
1049 }
1050 if slice_sizes.len() != operand_dims.len() {
1051 return Err(StridedError::RankMismatch(
1052 slice_sizes.len(),
1053 operand_dims.len(),
1054 ));
1055 }
1056 validate_start_vector(start_dims, operand_dims.len())?;
1057 checked_total_len(operand_dims)?;
1058 checked_total_len(start_dims)?;
1059 let total = checked_total_len(dest_dims)?;
1060 validate_layout_span(operand_dims, operand_strides)?;
1061 validate_layout_span(start_dims, start_strides)?;
1062 validate_layout_span(dest_dims, dest_strides)?;
1063 if dest_dims != slice_sizes {
1064 return Err(StridedError::ShapeMismatch(
1065 dest_dims.to_vec(),
1066 slice_sizes.to_vec(),
1067 ));
1068 }
1069 if !crate::layout_check::is_injective_layout(dest_dims, dest_strides) {
1070 return Err(StridedError::NonInjectiveOutputLayout);
1071 }
1072 validate_window_sizes(operand_dims, slice_sizes)?;
1073 let replay = WindowReplay::compile(slice_sizes, operand_strides, dest_strides)?;
1074
1075 Ok(Self {
1076 operand_dims: operand_dims.into(),
1077 operand_strides: operand_strides.into(),
1078 start_dims: start_dims.into(),
1079 start_strides: start_strides.into(),
1080 dest_dims: dest_dims.into(),
1081 dest_strides: dest_strides.into(),
1082 slice_sizes: slice_sizes.into(),
1083 total,
1084 window: fuse_pair_layout(slice_sizes, dest_strides, operand_strides),
1085 replay,
1086 })
1087 }
1088
1089 pub fn execute<T, I>(
1099 &self,
1100 dest: &mut RawStridedMut<'_, T>,
1101 operand: &RawStridedRef<'_, T>,
1102 starts: &RawStridedRef<'_, I>,
1103 exec: Exec<'_>,
1104 ) -> Result<()>
1105 where
1106 T: Copy + Send + Sync,
1107 I: GatherIndex,
1108 {
1109 self.execute_with_writer(dest, operand, starts, exec)
1110 }
1111
1112 pub(crate) fn execute_uninit<T, I>(
1113 &self,
1114 dest: &mut RawStridedMut<'_, MaybeUninit<T>>,
1115 operand: &RawStridedRef<'_, T>,
1116 starts: &RawStridedRef<'_, I>,
1117 exec: Exec<'_>,
1118 ) -> Result<()>
1119 where
1120 T: Copy + Send + Sync,
1121 I: GatherIndex,
1122 {
1123 self.execute_with_writer(dest, operand, starts, exec)
1124 }
1125
1126 fn execute_with_writer<T, I, W>(
1127 &self,
1128 dest: &mut W,
1129 operand: &RawStridedRef<'_, T>,
1130 starts: &RawStridedRef<'_, I>,
1131 exec: Exec<'_>,
1132 ) -> Result<()>
1133 where
1134 T: Copy + Send + Sync,
1135 I: GatherIndex,
1136 W: OverwriteWriter<T>,
1137 {
1138 self.check_call(dest, operand, starts)?;
1139 if self.total == 0 {
1140 return Ok(());
1141 }
1142 if self.uses_rank_one_contiguous_path() {
1143 return self.execute_rank_one_contiguous(dest, operand, starts, exec);
1144 }
1145 if let Some(window) = &self.window {
1146 return self.execute_fused_window(dest, operand, starts, window, exec);
1147 }
1148 let replay = &self.replay;
1149 let exec = crate::cost::for_len_tree(exec, KernelClass::Copy, self.total);
1150 if !exec.is_serial() {
1151 return self.execute_parallel(dest, operand, starts, exec, replay);
1152 }
1153
1154 let mut starts_storage = CoordScratch::new(self.operand_dims.len());
1155 let clamped_starts = starts_storage.as_mut_slice();
1156 read_clamped_starts(
1157 starts,
1158 &self.operand_dims,
1159 &self.slice_sizes,
1160 clamped_starts,
1161 )?;
1162 let source_base =
1163 checked_strided_offset(operand.offset(), &self.operand_strides, clamped_starts)?;
1164 let mut state = replay.decode(0, source_base, dest.offset())?;
1165 let operand_data = operand.data();
1166
1167 for _ in 0..self.total {
1171 let value = unsafe { *operand_data.as_ptr().offset(state.source_offset) };
1173 unsafe { dest.write_at(state.dest_offset, value) };
1176 replay.advance(&mut state);
1177 }
1178 Ok(())
1179 }
1180
1181 fn execute_fused_window<T, I, W>(
1187 &self,
1188 dest: &mut W,
1189 operand: &RawStridedRef<'_, T>,
1190 starts: &RawStridedRef<'_, I>,
1191 window: &FusedPairLayout,
1192 exec: Exec<'_>,
1193 ) -> Result<()>
1194 where
1195 T: Copy + Send + Sync,
1196 I: GatherIndex,
1197 W: OverwriteWriter<T>,
1198 {
1199 let mut starts_storage = CoordScratch::new(self.operand_dims.len());
1200 let clamped_starts = starts_storage.as_mut_slice();
1201 read_clamped_starts(
1202 starts,
1203 &self.operand_dims,
1204 &self.slice_sizes,
1205 clamped_starts,
1206 )?;
1207 let source_base =
1208 checked_strided_offset(operand.offset(), &self.operand_strides, clamped_starts)?;
1209 let dest_base = dest.offset();
1210 let dest_ptr = unsafe { dest.data_ptr() }.cast::<MaybeUninit<T>>();
1212 let tiles = pair_tiles::<MaybeUninit<T>, T>(window);
1213 unsafe {
1224 replay_fused_raw(
1225 dest_ptr,
1226 dest_base,
1227 operand.data().as_ptr(),
1228 source_base,
1229 window,
1230 tiles.as_ref(),
1231 |slot: &mut MaybeUninit<T>, value: T| *slot = MaybeUninit::new(value),
1232 KernelClass::Copy.ns_per_element(),
1233 exec,
1234 );
1235 }
1236 Ok(())
1237 }
1238
1239 #[inline]
1240 fn uses_rank_one_contiguous_path(&self) -> bool {
1241 self.operand_dims.len() == 1 && self.operand_strides[0] == 1 && self.dest_strides[0] == 1
1242 }
1243
1244 fn execute_rank_one_contiguous<T, I, W>(
1245 &self,
1246 dest: &mut W,
1247 operand: &RawStridedRef<'_, T>,
1248 starts: &RawStridedRef<'_, I>,
1249 exec: Exec<'_>,
1250 ) -> Result<()>
1251 where
1252 T: Copy + Send + Sync,
1253 I: GatherIndex,
1254 W: OverwriteWriter<T>,
1255 {
1256 let mut clamped_starts = [0usize; 1];
1257 read_clamped_starts(
1258 starts,
1259 &self.operand_dims,
1260 &self.slice_sizes,
1261 &mut clamped_starts,
1262 )?;
1263 let source_start = checked_offset_add(operand.offset(), 1, clamped_starts[0])?;
1264 let source_start =
1265 usize::try_from(source_start).map_err(|_| StridedError::OffsetOverflow)?;
1266 let dest_start =
1267 usize::try_from(dest.offset()).map_err(|_| StridedError::OffsetOverflow)?;
1268 let source_end = source_start
1269 .checked_add(self.total)
1270 .ok_or(StridedError::OffsetOverflow)?;
1271 let source = operand
1272 .data()
1273 .get(source_start..source_end)
1274 .ok_or(StridedError::OffsetOverflow)?;
1275 let dest_ptr = unsafe { dest.data_ptr() };
1277 unsafe {
1288 crate::threading::copy_contiguous(
1291 source.as_ptr(),
1292 dest_ptr.add(dest_start),
1293 self.total,
1294 exec,
1295 );
1296 }
1297 Ok(())
1298 }
1299
1300 fn execute_parallel<T, I, W>(
1301 &self,
1302 dest: &mut W,
1303 operand: &RawStridedRef<'_, T>,
1304 starts: &RawStridedRef<'_, I>,
1305 exec: Exec<'_>,
1306 replay: &WindowReplay,
1307 ) -> Result<()>
1308 where
1309 T: Copy + Send + Sync,
1310 I: GatherIndex,
1311 W: OverwriteWriter<T>,
1312 {
1313 let mut clamped_starts: AxisVec<usize> = (0..self.operand_dims.len()).map(|_| 0).collect();
1314 read_clamped_starts(
1315 starts,
1316 &self.operand_dims,
1317 &self.slice_sizes,
1318 &mut clamped_starts,
1319 )?;
1320 let source_base =
1321 checked_strided_offset(operand.offset(), &self.operand_strides, &clamped_starts)?;
1322 let dest_base = dest.offset();
1323 let operand_ptr = crate::threading::SendPtr(operand.data().as_ptr() as *mut T);
1324 let dest_ptr = crate::threading::SendPtr(unsafe { dest.data_ptr() });
1326
1327 crate::threading::parallel_map_reduce(
1328 0..self.total,
1329 exec,
1330 &|range| {
1331 let mut state = replay.decode(range.start, source_base, dest_base)?;
1332 let operand_ptr = operand_ptr.as_const();
1333 let dest_ptr = dest_ptr.as_ptr();
1334
1335 for _ in range {
1339 unsafe {
1342 dest_ptr
1343 .offset(state.dest_offset)
1344 .write(operand_ptr.offset(state.source_offset).read());
1345 }
1346 replay.advance(&mut state);
1347 }
1348 Ok(())
1349 },
1350 &|left, right| left.and(right),
1351 )
1352 }
1353
1354 fn check_call<T, I, W>(
1355 &self,
1356 dest: &W,
1357 operand: &RawStridedRef<'_, T>,
1358 starts: &RawStridedRef<'_, I>,
1359 ) -> Result<()>
1360 where
1361 W: OverwriteWriter<T>,
1362 {
1363 if dest.dims() != &self.dest_dims[..]
1364 || dest.strides() != &self.dest_strides[..]
1365 || operand.dims() != &self.operand_dims[..]
1366 || operand.strides() != &self.operand_strides[..]
1367 || starts.dims() != &self.start_dims[..]
1368 || starts.strides() != &self.start_strides[..]
1369 {
1370 return Err(StridedError::PlanLayoutMismatch);
1371 }
1372 Ok(())
1373 }
1374}
1375
1376impl DynamicUpdateSlicePlan {
1377 #[allow(clippy::too_many_arguments)]
1398 pub fn compile(
1399 operand_dims: &[usize],
1400 operand_strides: &[isize],
1401 start_dims: &[usize],
1402 start_strides: &[isize],
1403 update_dims: &[usize],
1404 update_strides: &[isize],
1405 dest_dims: &[usize],
1406 dest_strides: &[isize],
1407 ) -> Result<Self> {
1408 if operand_dims.len() != operand_strides.len()
1409 || start_dims.len() != start_strides.len()
1410 || update_dims.len() != update_strides.len()
1411 || dest_dims.len() != dest_strides.len()
1412 {
1413 return Err(StridedError::StrideLengthMismatch);
1414 }
1415 if update_dims.len() != operand_dims.len() {
1416 return Err(StridedError::RankMismatch(
1417 update_dims.len(),
1418 operand_dims.len(),
1419 ));
1420 }
1421 validate_start_vector(start_dims, operand_dims.len())?;
1422 checked_total_len(operand_dims)?;
1423 checked_total_len(start_dims)?;
1424 let total = checked_total_len(update_dims)?;
1425 validate_layout_span(operand_dims, operand_strides)?;
1426 validate_layout_span(start_dims, start_strides)?;
1427 validate_layout_span(update_dims, update_strides)?;
1428 validate_layout_span(dest_dims, dest_strides)?;
1429 if dest_dims != operand_dims {
1430 return Err(StridedError::ShapeMismatch(
1431 dest_dims.to_vec(),
1432 operand_dims.to_vec(),
1433 ));
1434 }
1435 if !crate::layout_check::is_injective_layout(dest_dims, dest_strides) {
1436 return Err(StridedError::NonInjectiveOutputLayout);
1437 }
1438 validate_window_sizes(operand_dims, update_dims)?;
1439 let copy_plan = CopyPlan::compile(operand_dims, dest_strides, operand_strides)?;
1440 let replay = WindowReplay::compile(update_dims, update_strides, dest_strides)?;
1441
1442 Ok(Self {
1443 operand_dims: operand_dims.into(),
1444 operand_strides: operand_strides.into(),
1445 start_dims: start_dims.into(),
1446 start_strides: start_strides.into(),
1447 update_dims: update_dims.into(),
1448 update_strides: update_strides.into(),
1449 dest_dims: dest_dims.into(),
1450 dest_strides: dest_strides.into(),
1451 total,
1452 copy_plan,
1453 window: fuse_pair_layout(update_dims, dest_strides, update_strides),
1454 replay,
1455 })
1456 }
1457
1458 pub fn execute<T, I>(
1470 &self,
1471 dest: &mut RawStridedMut<'_, T>,
1472 operand: &RawStridedRef<'_, T>,
1473 update: &RawStridedRef<'_, T>,
1474 starts: &RawStridedRef<'_, I>,
1475 exec: Exec<'_>,
1476 ) -> Result<()>
1477 where
1478 T: Copy + Send + Sync,
1479 I: GatherIndex,
1480 {
1481 let mut exec = exec;
1482 self.check_call(dest, operand, update, starts)?;
1483 let window = self.preflight_update_window(dest, update, starts)?;
1484 self.copy_plan.execute(dest, operand, exec.reborrow())?;
1485 self.execute_update_with_writer(dest, update, &window, exec)
1486 }
1487
1488 pub(crate) fn execute_uninit<'a, T, I>(
1492 &self,
1493 dest: &'a mut RawStridedMut<'a, MaybeUninit<T>>,
1494 operand: &RawStridedRef<'_, T>,
1495 update: &RawStridedRef<'_, T>,
1496 starts: &RawStridedRef<'_, I>,
1497 exec: Exec<'_>,
1498 ) -> Result<()>
1499 where
1500 T: Copy + Send + Sync,
1501 I: GatherIndex,
1502 {
1503 self.check_call(dest, operand, update, starts)?;
1504 let window = self.preflight_update_window(dest, update, starts)?;
1505 self.copy_plan
1506 .execute_uninit_then(dest, operand, exec, |mut receipt, exec| {
1507 self.execute_update_with_writer(&mut receipt, update, &window, exec)
1508 })?
1509 }
1510
1511 fn preflight_update_window<'a, T, I, W>(
1513 &self,
1514 dest: &W,
1515 update: &'a RawStridedRef<'_, T>,
1516 starts: &RawStridedRef<'_, I>,
1517 ) -> Result<UpdateWindow<'a, T>>
1518 where
1519 T: Copy,
1520 I: GatherIndex,
1521 W: OverwriteWriter<T>,
1522 {
1523 if self.total == 0 {
1524 return Ok(UpdateWindow::Empty);
1525 }
1526 let mut starts_storage = CoordScratch::new(self.operand_dims.len());
1527 let clamped_starts = starts_storage.as_mut_slice();
1528 read_clamped_starts(
1529 starts,
1530 &self.operand_dims,
1531 &self.update_dims,
1532 clamped_starts,
1533 )?;
1534 let dest_base = checked_strided_offset(dest.offset(), &self.dest_strides, clamped_starts)?;
1535 self.replay.source_span.covers(update.offset())?;
1538 self.replay.dest_span.covers(dest_base)?;
1539 if self.uses_rank_one_contiguous_path() {
1540 let update_start =
1541 usize::try_from(update.offset()).map_err(|_| StridedError::OffsetOverflow)?;
1542 let dest_start =
1543 usize::try_from(dest_base).map_err(|_| StridedError::OffsetOverflow)?;
1544 let update_end = update_start
1545 .checked_add(self.total)
1546 .ok_or(StridedError::OffsetOverflow)?;
1547 let run = update
1548 .data()
1549 .get(update_start..update_end)
1550 .ok_or(StridedError::OffsetOverflow)?;
1551 return Ok(UpdateWindow::RankOne {
1552 update: run,
1553 dest_start,
1554 });
1555 }
1556 Ok(UpdateWindow::Replay { dest_base })
1557 }
1558
1559 fn execute_update_with_writer<T, W>(
1560 &self,
1561 dest: &mut W,
1562 update: &RawStridedRef<'_, T>,
1563 window: &UpdateWindow<'_, T>,
1564 exec: Exec<'_>,
1565 ) -> Result<()>
1566 where
1567 T: Copy + Send + Sync,
1568 W: OverwriteWriter<T>,
1569 {
1570 let dest_base = match *window {
1571 UpdateWindow::Empty => return Ok(()),
1572 UpdateWindow::RankOne { update, dest_start } => {
1573 return self.execute_rank_one_contiguous(dest, update, dest_start, exec)
1574 }
1575 UpdateWindow::Replay { dest_base } => dest_base,
1576 };
1577 if let Some(fused) = &self.window {
1578 return self.execute_fused_window(dest, update, dest_base, fused, exec);
1579 }
1580 let replay = &self.replay;
1581 let exec = crate::cost::for_len_tree(exec, KernelClass::Copy, self.total);
1582 if !exec.is_serial() {
1583 return self.execute_update_parallel(dest, update, dest_base, exec);
1584 }
1585
1586 let mut state = replay.start(update.offset(), dest_base);
1587 let update_data = update.data();
1588
1589 for _ in 0..self.total {
1593 let value = unsafe { *update_data.as_ptr().offset(state.source_offset) };
1595 unsafe { dest.write_at(state.dest_offset, value) };
1598 replay.advance(&mut state);
1599 }
1600 Ok(())
1601 }
1602
1603 fn execute_fused_window<T, W>(
1606 &self,
1607 dest: &mut W,
1608 update: &RawStridedRef<'_, T>,
1609 dest_base: isize,
1610 window: &FusedPairLayout,
1611 exec: Exec<'_>,
1612 ) -> Result<()>
1613 where
1614 T: Copy + Send + Sync,
1615 W: OverwriteWriter<T>,
1616 {
1617 let dest_ptr = unsafe { dest.data_ptr() }.cast::<MaybeUninit<T>>();
1619 let tiles = pair_tiles::<MaybeUninit<T>, T>(window);
1620 unsafe {
1629 replay_fused_raw(
1630 dest_ptr,
1631 dest_base,
1632 update.data().as_ptr(),
1633 update.offset(),
1634 window,
1635 tiles.as_ref(),
1636 |slot: &mut MaybeUninit<T>, value: T| *slot = MaybeUninit::new(value),
1637 KernelClass::Copy.ns_per_element(),
1638 exec,
1639 );
1640 }
1641 Ok(())
1642 }
1643
1644 #[inline]
1645 fn uses_rank_one_contiguous_path(&self) -> bool {
1646 self.operand_dims.len() == 1
1647 && self.operand_strides[0] == 1
1648 && self.update_strides[0] == 1
1649 && self.dest_strides[0] == 1
1650 }
1651
1652 fn execute_rank_one_contiguous<T, W>(
1653 &self,
1654 dest: &mut W,
1655 update: &[T],
1656 dest_start: usize,
1657 exec: Exec<'_>,
1658 ) -> Result<()>
1659 where
1660 T: Copy + Send + Sync,
1661 W: OverwriteWriter<T>,
1662 {
1663 let dest_ptr = unsafe { dest.data_ptr() };
1665 unsafe {
1680 crate::threading::copy_contiguous(
1683 update.as_ptr(),
1684 dest_ptr.add(dest_start),
1685 self.total,
1686 exec,
1687 );
1688 }
1689 Ok(())
1690 }
1691
1692 fn execute_update_parallel<T, W>(
1693 &self,
1694 dest: &mut W,
1695 update: &RawStridedRef<'_, T>,
1696 dest_base: isize,
1697 exec: Exec<'_>,
1698 ) -> Result<()>
1699 where
1700 T: Copy + Send + Sync,
1701 W: OverwriteWriter<T>,
1702 {
1703 let replay = &self.replay;
1704 let source_base = update.offset();
1705 let update_ptr = crate::threading::SendPtr(update.data().as_ptr() as *mut T);
1706 let dest_ptr = crate::threading::SendPtr(unsafe { dest.data_ptr() });
1708
1709 crate::threading::parallel_map_reduce(
1710 0..self.total,
1711 exec,
1712 &|range| {
1713 let mut state = replay.decode(range.start, source_base, dest_base)?;
1714 let update_ptr = update_ptr.as_const();
1715 let dest_ptr = dest_ptr.as_ptr();
1716
1717 for _ in range {
1722 unsafe {
1725 dest_ptr
1726 .offset(state.dest_offset)
1727 .write(update_ptr.offset(state.source_offset).read());
1728 }
1729 replay.advance(&mut state);
1730 }
1731 Ok(())
1732 },
1733 &|left, right| left.and(right),
1734 )
1735 }
1736
1737 fn check_call<T, I, W>(
1738 &self,
1739 dest: &W,
1740 operand: &RawStridedRef<'_, T>,
1741 update: &RawStridedRef<'_, T>,
1742 starts: &RawStridedRef<'_, I>,
1743 ) -> Result<()>
1744 where
1745 W: OverwriteWriter<T>,
1746 {
1747 if dest.dims() != &self.dest_dims[..]
1748 || dest.strides() != &self.dest_strides[..]
1749 || operand.dims() != &self.operand_dims[..]
1750 || operand.strides() != &self.operand_strides[..]
1751 || update.dims() != &self.update_dims[..]
1752 || update.strides() != &self.update_strides[..]
1753 || starts.dims() != &self.start_dims[..]
1754 || starts.strides() != &self.start_strides[..]
1755 {
1756 return Err(StridedError::PlanLayoutMismatch);
1757 }
1758 Ok(())
1759 }
1760}
1761
1762impl ScatterPlan {
1763 #[allow(clippy::too_many_arguments)]
1786 pub fn compile(
1787 operand_dims: &[usize],
1788 operand_strides: &[isize],
1789 index_dims: &[usize],
1790 index_strides: &[isize],
1791 update_dims: &[usize],
1792 update_strides: &[isize],
1793 dest_dims: &[usize],
1794 dest_strides: &[isize],
1795 spec: ScatterSpec,
1796 ) -> Result<Self> {
1797 if operand_dims.len() != operand_strides.len()
1798 || index_dims.len() != index_strides.len()
1799 || update_dims.len() != update_strides.len()
1800 || dest_dims.len() != dest_strides.len()
1801 {
1802 return Err(StridedError::StrideLengthMismatch);
1803 }
1804 checked_total_len(operand_dims)?;
1805 checked_total_len(index_dims)?;
1806 checked_total_len(update_dims)?;
1807 if dest_dims != operand_dims {
1808 return Err(StridedError::ShapeMismatch(
1809 dest_dims.to_vec(),
1810 operand_dims.to_vec(),
1811 ));
1812 }
1813 if !crate::layout_check::is_injective_layout(dest_dims, dest_strides) {
1814 return Err(StridedError::NonInjectiveOutputLayout);
1815 }
1816
1817 let operand_rank = operand_dims.len();
1818 validate_unique_axes(&spec.inserted_window_dims, operand_rank)?;
1819 validate_unique_axes(&spec.scatter_dims_to_operand_dims, operand_rank)?;
1820 if spec.index_vector_dim > index_dims.len() {
1821 return Err(StridedError::InvalidAxis {
1822 axis: spec.index_vector_dim,
1823 rank: index_dims.len() + 1,
1824 });
1825 }
1826 let index_vector_size = if spec.index_vector_dim == index_dims.len() {
1827 1
1828 } else {
1829 index_dims[spec.index_vector_dim]
1830 };
1831 if index_vector_size != spec.scatter_dims_to_operand_dims.len() {
1832 return Err(StridedError::RankMismatch(
1833 index_vector_size,
1834 spec.scatter_dims_to_operand_dims.len(),
1835 ));
1836 }
1837
1838 let batch_shape = index_batch_shape(index_dims, spec.index_vector_dim);
1839 let window_dims = operand_window_dims(operand_rank, &spec.inserted_window_dims);
1840 if spec.update_window_dims.len() != window_dims.len() {
1841 return Err(StridedError::RankMismatch(
1842 spec.update_window_dims.len(),
1843 window_dims.len(),
1844 ));
1845 }
1846
1847 let update_rank = update_dims.len();
1848 let expected_batch_rank = update_rank
1849 .checked_sub(spec.update_window_dims.len())
1850 .ok_or(StridedError::RankMismatch(
1851 spec.update_window_dims.len(),
1852 update_rank,
1853 ))?;
1854 if expected_batch_rank != batch_shape.len() {
1855 return Err(StridedError::RankMismatch(
1856 expected_batch_rank,
1857 batch_shape.len(),
1858 ));
1859 }
1860 validate_unique_axes(&spec.update_window_dims, update_rank)?;
1861
1862 let mut is_update_window_dim: AxisVec<bool> = (0..update_rank).map(|_| false).collect();
1863 for &axis in &spec.update_window_dims {
1864 is_update_window_dim[axis] = true;
1865 }
1866
1867 let mut batch_axis = 0usize;
1868 for axis in 0..update_rank {
1869 if !is_update_window_dim[axis] {
1870 if update_dims[axis] != batch_shape[batch_axis] {
1871 return Err(StridedError::ShapeMismatch(
1872 update_dims.to_vec(),
1873 expected_scatter_update_shape(&batch_shape, &spec, update_dims).to_vec(),
1874 ));
1875 }
1876 batch_axis += 1;
1877 }
1878 }
1879
1880 let mut window_shape: AxisVec<usize> = (0..operand_rank).map(|_| 1).collect();
1881 let mut window_shape_updates: AxisVec<usize> =
1882 AxisVec::with_capacity(spec.update_window_dims.len());
1883 for (pos, &update_axis) in spec.update_window_dims.iter().enumerate() {
1884 let dim = update_dims[update_axis];
1885 window_shape_updates.push(dim);
1886 window_shape[window_dims[pos]] = dim;
1887 }
1888 validate_window_sizes(operand_dims, &window_shape)?;
1889
1890 let batch_elems = checked_total_len(&batch_shape)?;
1891 let window_elems = checked_total_len(&window_shape_updates)?;
1892 let copy_plan = CopyPlan::compile(operand_dims, dest_strides, operand_strides)?;
1893 let replay = ScatterReplay::compile(
1894 &batch_shape,
1895 index_dims,
1896 index_strides,
1897 spec.index_vector_dim,
1898 spec.scatter_dims_to_operand_dims.len(),
1899 update_dims,
1900 update_strides,
1901 &spec.update_window_dims,
1902 &is_update_window_dim,
1903 &window_shape_updates,
1904 &window_dims,
1905 dest_strides,
1906 )?;
1907
1908 Ok(Self {
1909 operand_dims: operand_dims.into(),
1910 operand_strides: operand_strides.into(),
1911 index_dims: index_dims.into(),
1912 index_strides: index_strides.into(),
1913 update_dims: update_dims.into(),
1914 update_strides: update_strides.into(),
1915 dest_dims: dest_dims.into(),
1916 dest_strides: dest_strides.into(),
1917 spec,
1918 window_shape,
1919 batch_elems,
1920 window_elems,
1921 copy_plan,
1922 replay,
1923 })
1924 }
1925
1926 #[inline(always)]
1935 pub fn execute<T, I>(
1936 &self,
1937 dest: &mut RawStridedMut<'_, T>,
1938 operand: &RawStridedRef<'_, T>,
1939 scatter_indices: &RawStridedRef<'_, I>,
1940 updates: &RawStridedRef<'_, T>,
1941 exec: Exec<'_>,
1942 ) -> Result<()>
1943 where
1944 T: Copy + Add<Output = T> + Send + Sync,
1945 I: GatherIndex,
1946 {
1947 self.check_call(dest, operand, scatter_indices, updates)?;
1948 self.copy_plan.execute(dest, operand, exec)?;
1949 self.execute_updates(dest, scatter_indices, updates, |a, b| a + b)
1950 }
1951
1952 pub(crate) fn execute_uninit<'a, T, I>(
1955 &self,
1956 dest: &'a mut RawStridedMut<'a, MaybeUninit<T>>,
1957 operand: &RawStridedRef<'_, T>,
1958 scatter_indices: &RawStridedRef<'_, I>,
1959 updates: &RawStridedRef<'_, T>,
1960 combine: fn(T, T) -> T,
1961 exec: Exec<'_>,
1962 ) -> Result<()>
1963 where
1964 T: Copy + Add<Output = T> + Send + Sync,
1965 I: GatherIndex,
1966 {
1967 self.check_call(dest, operand, scatter_indices, updates)?;
1968 self.copy_plan
1969 .execute_uninit_then(dest, operand, exec, |mut receipt, _| {
1970 self.execute_updates(&mut receipt, scatter_indices, updates, combine)
1971 })?
1972 }
1973
1974 #[inline(always)]
1975 fn execute_updates<T, I, W, F>(
1976 &self,
1977 dest: &mut W,
1978 scatter_indices: &RawStridedRef<'_, I>,
1979 updates: &RawStridedRef<'_, T>,
1980 combine: F,
1981 ) -> Result<()>
1982 where
1983 T: Copy + Send + Sync,
1984 I: GatherIndex,
1985 W: ReadModifyWrite<T>,
1986 F: Fn(T, T) -> T + Copy,
1987 {
1988 if self.batch_elems == 0 || self.window_elems == 0 {
1989 return Ok(());
1990 }
1991 if self.uses_rank_one_scalar_update_path() {
1992 return self.execute_rank_one_scalar_updates(dest, scatter_indices, updates, combine);
1993 }
1994 self.execute_generic_updates(dest, scatter_indices, updates, combine)
1995 }
1996
1997 #[inline(never)]
1998 fn execute_generic_updates<T, I, W, F>(
1999 &self,
2000 dest: &mut W,
2001 scatter_indices: &RawStridedRef<'_, I>,
2002 updates: &RawStridedRef<'_, T>,
2003 combine: F,
2004 ) -> Result<()>
2005 where
2006 T: Copy + Send + Sync,
2007 I: GatherIndex,
2008 W: ReadModifyWrite<T>,
2009 F: Fn(T, T) -> T + Copy,
2010 {
2011 let replay = &self.replay;
2014
2015 let mut operand_base_storage = CoordScratch::new(self.operand_dims.len());
2016 let operand_base = operand_base_storage.as_mut_slice();
2017 let mut batch_state = replay
2018 .batch
2019 .decode(0, scatter_indices.offset(), updates.offset())?;
2020 let index_data = scatter_indices.data();
2021 let update_data = updates.data();
2022
2023 for _ in 0..self.batch_elems {
2026 operand_base.fill(0);
2027 for (&component_offset, &operand_axis) in replay
2028 .index_component_offsets
2029 .iter()
2030 .zip(self.spec.scatter_dims_to_operand_dims.iter())
2031 {
2032 let index_offset = batch_state
2033 .source_offset
2034 .checked_add(component_offset)
2035 .ok_or(StridedError::OffsetOverflow)?;
2036 let start = unsafe { *index_data.as_ptr().offset(index_offset) }.to_i64();
2039 operand_base[operand_axis] = clamp_window_start(
2040 start,
2041 self.operand_dims[operand_axis],
2042 self.window_shape[operand_axis],
2043 );
2044 }
2045
2046 let dest_base = checked_strided_offset(dest.offset(), dest.strides(), operand_base)?;
2047 let mut window_state = replay
2048 .window
2049 .decode(0, batch_state.dest_offset, dest_base)?;
2050 for _ in 0..self.window_elems {
2051 let value = unsafe { *update_data.as_ptr().offset(window_state.source_offset) };
2054 unsafe { dest.add_at(window_state.dest_offset, value, combine) };
2055 replay.window.advance(&mut window_state);
2056 }
2057 replay.batch.advance(&mut batch_state);
2058 }
2059 Ok(())
2060 }
2061
2062 fn uses_rank_one_scalar_update_path(&self) -> bool {
2063 self.operand_dims.len() == 1
2064 && self.index_dims.len() == 2
2065 && self.update_dims.len() == 1
2066 && self.dest_dims.len() == 1
2067 && self.operand_strides[0] == 1
2068 && self.index_strides[0] == 1
2069 && self.update_strides[0] == 1
2070 && self.dest_strides[0] == 1
2071 && self.index_dims[1] == 1
2072 && self.spec.update_window_dims.is_empty()
2073 && self.spec.inserted_window_dims.as_slice() == [0]
2074 && self.spec.scatter_dims_to_operand_dims.as_slice() == [0]
2075 && self.spec.index_vector_dim == 1
2076 && self.window_elems == 1
2077 }
2078
2079 #[inline(always)]
2080 fn execute_rank_one_scalar_updates<T, I, W, F>(
2081 &self,
2082 dest: &mut W,
2083 scatter_indices: &RawStridedRef<'_, I>,
2084 updates: &RawStridedRef<'_, T>,
2085 combine: F,
2086 ) -> Result<()>
2087 where
2088 T: Copy,
2089 I: GatherIndex,
2090 W: ReadModifyWrite<T>,
2091 F: Fn(T, T) -> T + Copy,
2092 {
2093 let mut index_offset = scatter_indices.offset();
2094 let mut update_offset = updates.offset();
2095 let dest_offset = dest.offset();
2096 let index_data = scatter_indices.data();
2097 let update_data = updates.data();
2098 let dest_ptr = unsafe { dest.data_ptr() };
2100
2101 #[allow(clippy::explicit_counter_loop)]
2105 for _ in 0..self.batch_elems {
2106 unsafe {
2109 let start = (*index_data.as_ptr().offset(index_offset)).to_i64();
2110 let output_offset =
2111 dest_offset + clamp_window_start(start, self.operand_dims[0], 1) as isize;
2112 let output = dest_ptr.offset(output_offset);
2113 output.write(combine(
2114 output.read(),
2115 *update_data.as_ptr().offset(update_offset),
2116 ));
2117 }
2118 index_offset += 1;
2119 update_offset += 1;
2120 }
2121 Ok(())
2122 }
2123
2124 fn check_call<T, I, W>(
2125 &self,
2126 dest: &W,
2127 operand: &RawStridedRef<'_, T>,
2128 scatter_indices: &RawStridedRef<'_, I>,
2129 updates: &RawStridedRef<'_, T>,
2130 ) -> Result<()>
2131 where
2132 W: OverwriteWriter<T>,
2133 {
2134 if dest.dims() != &self.dest_dims[..]
2135 || dest.strides() != &self.dest_strides[..]
2136 || operand.dims() != &self.operand_dims[..]
2137 || operand.strides() != &self.operand_strides[..]
2138 || scatter_indices.dims() != &self.index_dims[..]
2139 || scatter_indices.strides() != &self.index_strides[..]
2140 || updates.dims() != &self.update_dims[..]
2141 || updates.strides() != &self.update_strides[..]
2142 {
2143 return Err(StridedError::PlanLayoutMismatch);
2144 }
2145 Ok(())
2146 }
2147}
2148
2149fn validate_unique_axes(axes: &[usize], rank: usize) -> Result<()> {
2150 let mut seen: InlineVec<bool> = InlineVec::new();
2153 seen.resize(rank, false);
2154 for &axis in axes {
2155 if axis >= rank {
2156 return Err(StridedError::InvalidAxis { axis, rank });
2157 }
2158 if seen[axis] {
2159 return Err(StridedError::InvalidAxis { axis, rank });
2160 }
2161 seen[axis] = true;
2162 }
2163 Ok(())
2164}
2165
2166fn validate_start_vector(start_dims: &[usize], operand_rank: usize) -> Result<()> {
2167 if start_dims.len() != 1 {
2168 return Err(StridedError::RankMismatch(start_dims.len(), 1));
2169 }
2170 if start_dims[0] != operand_rank {
2171 return Err(StridedError::RankMismatch(start_dims[0], operand_rank));
2172 }
2173 Ok(())
2174}
2175
2176fn validate_window_sizes(operand_dims: &[usize], window_sizes: &[usize]) -> Result<()> {
2177 if operand_dims.len() != window_sizes.len() {
2178 return Err(StridedError::RankMismatch(
2179 window_sizes.len(),
2180 operand_dims.len(),
2181 ));
2182 }
2183 for (axis, (&window, &dim)) in window_sizes.iter().zip(operand_dims.iter()).enumerate() {
2184 if window > dim {
2185 return Err(StridedError::InvalidAxis {
2186 axis,
2187 rank: operand_dims.len(),
2188 });
2189 }
2190 }
2191 Ok(())
2192}
2193
2194fn read_clamped_starts<I>(
2195 starts: &RawStridedRef<'_, I>,
2196 operand_dims: &[usize],
2197 window_sizes: &[usize],
2198 out: &mut [usize],
2199) -> Result<()>
2200where
2201 I: GatherIndex,
2202{
2203 debug_assert_eq!(operand_dims.len(), window_sizes.len());
2204 debug_assert_eq!(operand_dims.len(), out.len());
2205 for axis in 0..operand_dims.len() {
2206 let offset = checked_offset_add(starts.offset(), starts.strides()[0], axis)?;
2207 let start = unsafe { *starts.data().as_ptr().offset(offset) }.to_i64();
2208 out[axis] = clamp_window_start(start, operand_dims[axis], window_sizes[axis]);
2209 }
2210 Ok(())
2211}
2212
2213#[inline]
2214fn clamp_window_start(start: i64, dim_size: usize, window_size: usize) -> usize {
2215 let max_start = dim_size.saturating_sub(window_size) as i64;
2216 start.clamp(0, max_start) as usize
2217}
2218
2219fn expected_scatter_update_shape(
2220 batch_shape: &[usize],
2221 spec: &ScatterSpec,
2222 update_dims: &[usize],
2223) -> AxisVec<usize> {
2224 let mut expected: AxisVec<usize> = AxisVec::with_capacity(update_dims.len());
2225 let mut batch_axis = 0usize;
2226 for (axis, &dim) in update_dims.iter().enumerate() {
2227 if spec.update_window_dims.contains(&axis) {
2228 expected.push(dim);
2229 } else {
2230 expected.push(batch_shape[batch_axis]);
2231 batch_axis += 1;
2232 }
2233 }
2234 expected
2235}
2236
2237fn operand_window_dims(rank: usize, collapsed_slice_dims: &[usize]) -> AxisVec<usize> {
2238 (0..rank)
2239 .filter(|axis| !collapsed_slice_dims.contains(axis))
2240 .collect()
2241}
2242
2243fn index_batch_shape(index_dims: &[usize], index_vector_dim: usize) -> AxisVec<usize> {
2244 if index_vector_dim == index_dims.len() {
2245 return index_dims.into();
2246 }
2247 index_dims
2248 .iter()
2249 .enumerate()
2250 .filter_map(|(axis, &dim)| (axis != index_vector_dim).then_some(dim))
2251 .collect()
2252}
2253
2254fn validate_layout_span(dims: &[usize], strides: &[isize]) -> Result<OffsetSpan> {
2256 if dims.len() != strides.len() {
2257 return Err(StridedError::StrideLengthMismatch);
2258 }
2259 let mut span = OffsetSpan::default();
2260 for (&dim, &stride) in dims.iter().zip(strides.iter()) {
2261 let last =
2262 isize::try_from(dim.saturating_sub(1)).map_err(|_| StridedError::OffsetOverflow)?;
2263 let extent = stride
2264 .checked_mul(last)
2265 .ok_or(StridedError::OffsetOverflow)?;
2266 if extent < 0 {
2267 span.min = span
2268 .min
2269 .checked_add(extent)
2270 .ok_or(StridedError::OffsetOverflow)?;
2271 } else {
2272 span.max = span
2273 .max
2274 .checked_add(extent)
2275 .ok_or(StridedError::OffsetOverflow)?;
2276 }
2277 }
2278 Ok(span)
2279}
2280
2281fn checked_replay_reset(dim: usize, step: isize) -> Result<isize> {
2282 if dim == 0 {
2283 return Ok(0);
2284 }
2285 let last = isize::try_from(dim - 1).map_err(|_| StridedError::OffsetOverflow)?;
2286 step.checked_mul(last)
2287 .and_then(isize::checked_neg)
2288 .ok_or(StridedError::OffsetOverflow)
2289}
2290
2291fn checked_total_len(dims: &[usize]) -> Result<usize> {
2292 if dims.is_empty() {
2293 return Ok(1);
2294 }
2295 dims.iter()
2296 .try_fold(1usize, |acc, &dim| acc.checked_mul(dim))
2297 .ok_or(StridedError::OffsetOverflow)
2298}
2299
2300fn checked_strided_offset(base: isize, strides: &[isize], index: &[usize]) -> Result<isize> {
2301 let mut offset = base;
2302 for (&stride, &coord) in strides.iter().zip(index.iter()) {
2303 offset = checked_offset_add(offset, stride, coord)?;
2304 }
2305 Ok(offset)
2306}
2307
2308fn checked_offset_add(base: isize, stride: isize, coord: usize) -> Result<isize> {
2309 let coord = isize::try_from(coord).map_err(|_| StridedError::OffsetOverflow)?;
2310 let scaled = stride
2311 .checked_mul(coord)
2312 .ok_or(StridedError::OffsetOverflow)?;
2313 base.checked_add(scaled).ok_or(StridedError::OffsetOverflow)
2314}
2315
2316struct CoordScratch {
2317 inline: [usize; RAW_FUSED_RANK_LIMIT],
2318 heap: Option<Vec<usize>>,
2319 len: usize,
2320}
2321
2322impl CoordScratch {
2323 fn new(len: usize) -> Self {
2324 if len <= RAW_FUSED_RANK_LIMIT {
2325 Self {
2326 inline: [0; RAW_FUSED_RANK_LIMIT],
2327 heap: None,
2328 len,
2329 }
2330 } else {
2331 Self {
2332 inline: [0; RAW_FUSED_RANK_LIMIT],
2333 heap: Some(vec![0; len]),
2334 len,
2335 }
2336 }
2337 }
2338
2339 fn as_mut_slice(&mut self) -> &mut [usize] {
2340 match &mut self.heap {
2341 Some(heap) => heap,
2342 None => &mut self.inline[..self.len],
2343 }
2344 }
2345}
2346
2347#[cfg(test)]
2348#[path = "gather_plan/tests/tests.rs"]
2349mod tests;
2350
2351#[cfg(test)]
2352#[path = "gather_plan/tests/parallel_tests.rs"]
2353mod parallel_tests;