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