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 fn compile(
147 batch_shape: &[usize],
148 index_dims: &[usize],
149 index_strides: &[isize],
150 index_vector_dim: usize,
151 index_component_count: usize,
152 update_dims: &[usize],
153 update_strides: &[isize],
154 update_window_dims: &[usize],
155 is_update_window_dim: &[bool],
156 window_shape_updates: &[usize],
157 window_dims: &[usize],
158 dest_strides: &[isize],
159 ) -> Result<Self> {
160 let (
161 batch_source_strides,
162 batch_dest_strides,
163 window_source_strides,
164 window_dest_strides,
165 vector_stride,
166 ) = scatter_replay_strides(
167 index_dims,
168 index_strides,
169 index_vector_dim,
170 update_dims,
171 update_strides,
172 update_window_dims,
173 is_update_window_dim,
174 window_dims,
175 dest_strides,
176 );
177 let batch = WindowReplay::compile(batch_shape, &batch_source_strides, &batch_dest_strides)?;
178 let window = WindowReplay::compile(
179 window_shape_updates,
180 &window_source_strides,
181 &window_dest_strides,
182 )?;
183 let mut index_component_offsets = AxisVec::with_capacity(index_component_count);
184 for component in 0..index_component_count {
185 index_component_offsets.push(checked_offset_add(0, vector_stride, component)?);
186 }
187 Ok(Self {
188 batch,
189 window,
190 index_component_offsets,
191 })
192 }
193}
194
195fn scatter_replay_strides(
196 index_dims: &[usize],
197 index_strides: &[isize],
198 index_vector_dim: usize,
199 update_dims: &[usize],
200 update_strides: &[isize],
201 update_window_dims: &[usize],
202 is_update_window_dim: &[bool],
203 window_dims: &[usize],
204 dest_strides: &[isize],
205) -> (
206 AxisVec<isize>,
207 AxisVec<isize>,
208 AxisVec<isize>,
209 AxisVec<isize>,
210 isize,
211) {
212 let batch_source_strides = index_dims
213 .iter()
214 .zip(index_strides.iter())
215 .enumerate()
216 .filter_map(|(axis, (_, &stride))| (axis != index_vector_dim).then_some(stride))
217 .collect();
218 let batch_dest_strides = update_dims
219 .iter()
220 .zip(update_strides.iter())
221 .enumerate()
222 .filter_map(|(axis, (_, &stride))| (!is_update_window_dim[axis]).then_some(stride))
223 .collect();
224 let window_source_strides = update_window_dims
225 .iter()
226 .map(|&axis| update_strides[axis])
227 .collect();
228 let window_dest_strides = window_dims.iter().map(|&axis| dest_strides[axis]).collect();
229 let vector_stride = if index_vector_dim < index_dims.len() {
230 index_strides[index_vector_dim]
231 } else {
232 0
233 };
234 (
235 batch_source_strides,
236 batch_dest_strides,
237 window_source_strides,
238 window_dest_strides,
239 vector_stride,
240 )
241}
242
243impl WindowReplay {
244 fn compile(shape: &[usize], source_strides: &[isize], dest_strides: &[isize]) -> Result<Self> {
245 let source_span = validate_layout_span(shape, source_strides)?;
246 let dest_span = validate_layout_span(shape, dest_strides)?;
247 let mut fused_shape: AxisVec<usize> = AxisVec::with_capacity(shape.len());
248 let mut axes: AxisVec<WindowReplayAxis> = AxisVec::with_capacity(shape.len());
249 for (axis, &dim) in shape.iter().enumerate() {
250 let source_step = source_strides[axis];
251 let dest_step = dest_strides[axis];
252 if let Some(previous_axis) = fused_shape.len().checked_sub(1) {
253 let previous_extent = fused_shape[previous_axis];
254 let previous_extent =
255 isize::try_from(previous_extent).map_err(|_| StridedError::OffsetOverflow)?;
256 let expected_source = axes[previous_axis]
257 .source_step
258 .checked_mul(previous_extent)
259 .ok_or(StridedError::OffsetOverflow)?;
260 let expected_dest = axes[previous_axis]
261 .dest_step
262 .checked_mul(previous_extent)
263 .ok_or(StridedError::OffsetOverflow)?;
264 if source_step == expected_source && dest_step == expected_dest {
265 let fused_extent = fused_shape[previous_axis]
266 .checked_mul(dim)
267 .ok_or(StridedError::OffsetOverflow)?;
268 fused_shape[previous_axis] = fused_extent;
269 axes[previous_axis].source_reset =
270 checked_replay_reset(fused_extent, axes[previous_axis].source_step)?;
271 axes[previous_axis].dest_reset =
272 checked_replay_reset(fused_extent, axes[previous_axis].dest_step)?;
273 continue;
274 }
275 }
276 fused_shape.push(dim);
277 axes.push(WindowReplayAxis {
278 source_step,
279 source_reset: checked_replay_reset(dim, source_step)?,
280 dest_step,
281 dest_reset: checked_replay_reset(dim, dest_step)?,
282 });
283 }
284 Ok(Self {
285 shape: fused_shape,
286 axes,
287 source_span,
288 dest_span,
289 })
290 }
291
292 fn start(&self, source_base: isize, dest_base: isize) -> WindowReplayState {
296 WindowReplayState {
297 coords: CoordScratch::new(self.shape.len()),
298 source_offset: source_base,
299 dest_offset: dest_base,
300 }
301 }
302
303 fn decode(
304 &self,
305 mut linear: usize,
306 source_base: isize,
307 dest_base: isize,
308 ) -> Result<WindowReplayState> {
309 let mut coords = CoordScratch::new(self.shape.len());
310 let mut source_offset = source_base;
311 let mut dest_offset = dest_base;
312 for (axis, (&dim, coord)) in self
313 .shape
314 .iter()
315 .zip(coords.as_mut_slice().iter_mut())
316 .enumerate()
317 {
318 *coord = linear % dim;
319 linear /= dim;
320 let replay_axis = self.axes[axis];
321 source_offset = checked_offset_add(source_offset, replay_axis.source_step, *coord)?;
322 dest_offset = checked_offset_add(dest_offset, replay_axis.dest_step, *coord)?;
323 }
324 Ok(WindowReplayState {
325 coords,
326 source_offset,
327 dest_offset,
328 })
329 }
330
331 #[inline]
332 fn advance(&self, state: &mut WindowReplayState) {
333 for ((coord, &dim), replay_axis) in state
334 .coords
335 .as_mut_slice()
336 .iter_mut()
337 .zip(self.shape.iter())
338 .zip(self.axes.iter())
339 {
340 let next = *coord + 1;
341 if next < dim {
342 *coord = next;
343 state.source_offset += replay_axis.source_step;
344 state.dest_offset += replay_axis.dest_step;
345 return;
346 }
347 *coord = 0;
348 state.source_offset += replay_axis.source_reset;
349 state.dest_offset += replay_axis.dest_reset;
350 }
351 }
352}
353
354#[derive(Clone, Debug, Eq, PartialEq)]
360pub struct ScatterSpec {
361 pub update_window_dims: Vec<usize>,
362 pub inserted_window_dims: Vec<usize>,
363 pub scatter_dims_to_operand_dims: Vec<usize>,
364 pub index_vector_dim: usize,
365}
366
367#[derive(Clone, Debug)]
369pub struct DynamicSlicePlan {
370 operand_dims: AxisVec<usize>,
371 operand_strides: AxisVec<isize>,
372 start_dims: AxisVec<usize>,
373 start_strides: AxisVec<isize>,
374 dest_dims: AxisVec<usize>,
375 dest_strides: AxisVec<isize>,
376 slice_sizes: AxisVec<usize>,
377 total: usize,
378 window: Option<FusedPairLayout>,
383 replay: WindowReplay,
384}
385
386#[derive(Clone, Debug)]
392pub struct DynamicUpdateSlicePlan {
393 operand_dims: AxisVec<usize>,
394 operand_strides: AxisVec<isize>,
395 start_dims: AxisVec<usize>,
396 start_strides: AxisVec<isize>,
397 update_dims: AxisVec<usize>,
398 update_strides: AxisVec<isize>,
399 dest_dims: AxisVec<usize>,
400 dest_strides: AxisVec<isize>,
401 total: usize,
402 copy_plan: CopyPlan,
403 window: Option<FusedPairLayout>,
408 replay: WindowReplay,
409}
410
411enum UpdateWindow<'a, T> {
419 Empty,
421 RankOne { update: &'a [T], dest_start: usize },
424 Replay { dest_base: isize },
427}
428
429#[derive(Clone, Debug)]
435pub struct ScatterPlan {
436 operand_dims: AxisVec<usize>,
437 operand_strides: AxisVec<isize>,
438 index_dims: AxisVec<usize>,
439 index_strides: AxisVec<isize>,
440 update_dims: AxisVec<usize>,
441 update_strides: AxisVec<isize>,
442 dest_dims: AxisVec<usize>,
443 dest_strides: AxisVec<isize>,
444 spec: ScatterSpec,
445 window_shape: AxisVec<usize>,
446 batch_elems: usize,
447 window_elems: usize,
448 copy_plan: CopyPlan,
449 replay: ScatterReplay,
450}
451
452impl GatherPlan {
453 pub fn compile(
472 operand_dims: &[usize],
473 operand_strides: &[isize],
474 index_dims: &[usize],
475 index_strides: &[isize],
476 dest_dims: &[usize],
477 dest_strides: &[isize],
478 spec: GatherSpec,
479 ) -> Result<Self> {
480 if operand_dims.len() != operand_strides.len()
481 || index_dims.len() != index_strides.len()
482 || dest_dims.len() != dest_strides.len()
483 {
484 return Err(StridedError::StrideLengthMismatch);
485 }
486 checked_total_len(operand_dims)?;
487 checked_total_len(index_dims)?;
488 let total = checked_total_len(dest_dims)?;
489 validate_layout_span(operand_dims, operand_strides)?;
490 validate_layout_span(index_dims, index_strides)?;
491 validate_layout_span(dest_dims, dest_strides)?;
492 if !crate::layout_check::is_injective_layout(dest_dims, dest_strides) {
493 return Err(StridedError::NonInjectiveOutputLayout);
494 }
495
496 let operand_rank = operand_dims.len();
497 if spec.slice_sizes.len() != operand_rank {
498 return Err(StridedError::RankMismatch(
499 spec.slice_sizes.len(),
500 operand_rank,
501 ));
502 }
503 validate_unique_axes(&spec.collapsed_slice_dims, operand_rank)?;
504 validate_unique_axes(&spec.start_index_map, operand_rank)?;
505 if spec.index_vector_dim > index_dims.len() {
506 return Err(StridedError::InvalidAxis {
507 axis: spec.index_vector_dim,
508 rank: index_dims.len() + 1,
509 });
510 }
511
512 for (axis, (&window, &dim)) in spec.slice_sizes.iter().zip(operand_dims.iter()).enumerate()
513 {
514 if window > dim {
515 return Err(StridedError::InvalidAxis {
516 axis,
517 rank: operand_rank,
518 });
519 }
520 }
521 for &axis in &spec.collapsed_slice_dims {
522 if spec.slice_sizes[axis] != 1 {
523 return Err(StridedError::InvalidAxis {
524 axis,
525 rank: operand_rank,
526 });
527 }
528 }
529
530 let index_vector_size = if spec.index_vector_dim == index_dims.len() {
531 1
532 } else {
533 index_dims[spec.index_vector_dim]
534 };
535 if index_vector_size != spec.start_index_map.len() {
536 return Err(StridedError::RankMismatch(
537 index_vector_size,
538 spec.start_index_map.len(),
539 ));
540 }
541
542 let window_dims = operand_window_dims(operand_rank, &spec.collapsed_slice_dims);
543 if spec.offset_dims.len() != window_dims.len() {
544 return Err(StridedError::RankMismatch(
545 spec.offset_dims.len(),
546 window_dims.len(),
547 ));
548 }
549
550 let batch_shape = index_batch_shape(index_dims, spec.index_vector_dim);
551 let out_rank = batch_shape.len() + spec.offset_dims.len();
552 validate_unique_axes(&spec.offset_dims, out_rank)?;
553
554 let mut out_axis_to_operand_dim: AxisVec<Option<usize>> =
555 (0..out_rank).map(|_| None).collect();
556 for (offset_axis, &out_axis) in spec.offset_dims.iter().enumerate() {
557 out_axis_to_operand_dim[out_axis] = Some(window_dims[offset_axis]);
558 }
559
560 let mut expected_dest_dims: AxisVec<usize> = AxisVec::with_capacity(out_rank);
561 let mut batch_axis = 0usize;
562 for &operand_dim in &out_axis_to_operand_dim {
563 match operand_dim {
564 Some(axis) => expected_dest_dims.push(spec.slice_sizes[axis]),
565 None => {
566 expected_dest_dims.push(batch_shape[batch_axis]);
567 batch_axis += 1;
568 }
569 }
570 }
571 if dest_dims != &expected_dest_dims[..] {
572 return Err(StridedError::ShapeMismatch(
573 dest_dims.to_vec(),
574 expected_dest_dims.to_vec(),
575 ));
576 }
577
578 let batch_index_strides: AxisVec<isize> = index_dims
579 .iter()
580 .zip(index_strides.iter())
581 .enumerate()
582 .filter_map(|(axis, (_, &stride))| (axis != spec.index_vector_dim).then_some(stride))
583 .collect();
584 let mut batch_axis = 0usize;
585 let mut replay_axes = AxisVec::with_capacity(out_rank);
586 for (out_axis, &operand_dim) in out_axis_to_operand_dim.iter().enumerate() {
587 let (window_step, index_batch_step) = match operand_dim {
588 Some(axis) => (operand_strides[axis], 0),
589 None => {
590 let step = batch_index_strides[batch_axis];
591 batch_axis += 1;
592 (0, step)
593 }
594 };
595 replay_axes.push(GatherReplayAxis {
596 dest_step: dest_strides[out_axis],
597 dest_reset: checked_replay_reset(dest_dims[out_axis], dest_strides[out_axis])?,
598 window_step,
599 window_reset: checked_replay_reset(dest_dims[out_axis], window_step)?,
600 index_batch_step,
601 index_batch_reset: checked_replay_reset(dest_dims[out_axis], index_batch_step)?,
602 });
603 }
604
605 let vector_stride = if spec.index_vector_dim < index_dims.len() {
606 index_strides[spec.index_vector_dim]
607 } else {
608 0
609 };
610 let mut index_component_offsets = AxisVec::with_capacity(spec.start_index_map.len());
611 for component in 0..spec.start_index_map.len() {
612 index_component_offsets.push(checked_offset_add(0, vector_stride, component)?);
613 }
614
615 let index_operand_strides: AxisVec<isize> = spec
616 .start_index_map
617 .iter()
618 .map(|&axis| operand_strides[axis])
619 .collect();
620
621 Ok(Self {
622 operand_dims: operand_dims.into(),
623 operand_strides: operand_strides.into(),
624 index_dims: index_dims.into(),
625 index_strides: index_strides.into(),
626 dest_dims: dest_dims.into(),
627 dest_strides: dest_strides.into(),
628 spec,
629 replay: GatherReplay {
630 axes: replay_axes,
631 index_component_offsets,
632 index_operand_strides,
633 },
634 total,
635 })
636 }
637
638 #[inline]
639 pub fn spec(&self) -> &GatherSpec {
640 &self.spec
641 }
642
643 #[inline]
644 pub fn dest_dims(&self) -> &[usize] {
645 &self.dest_dims
646 }
647
648 pub fn execute<T, I>(
662 &self,
663 dest: &mut RawStridedMut<'_, T>,
664 operand: &RawStridedRef<'_, T>,
665 start_indices: &RawStridedRef<'_, I>,
666 exec: Exec<'_>,
667 ) -> Result<()>
668 where
669 T: Copy + Send + Sync,
670 I: GatherIndex,
671 {
672 self.execute_with_writer(dest, operand, start_indices, exec)
673 }
674
675 pub(crate) fn execute_uninit<T, I>(
678 &self,
679 dest: &mut RawStridedMut<'_, MaybeUninit<T>>,
680 operand: &RawStridedRef<'_, T>,
681 start_indices: &RawStridedRef<'_, I>,
682 exec: Exec<'_>,
683 ) -> Result<()>
684 where
685 T: Copy + Send + Sync,
686 I: GatherIndex,
687 {
688 self.execute_with_writer(dest, operand, start_indices, exec)
689 }
690
691 fn execute_with_writer<T, I, W>(
692 &self,
693 dest: &mut W,
694 operand: &RawStridedRef<'_, T>,
695 start_indices: &RawStridedRef<'_, I>,
696 exec: Exec<'_>,
697 ) -> Result<()>
698 where
699 T: Copy + Send + Sync,
700 I: GatherIndex,
701 W: OverwriteWriter<T>,
702 {
703 self.check_call(dest, operand, start_indices)?;
704 if self.total == 0 {
705 return Ok(());
706 }
707 if self.uses_rank_one_scalar_take_path() {
708 let exec = crate::cost::for_len_tree(exec, KernelClass::Copy, self.total);
709 if !exec.is_serial() {
710 return self.execute_rank_one_scalar_take_parallel(
711 dest,
712 operand,
713 start_indices,
714 exec,
715 );
716 }
717 return self.execute_rank_one_scalar_take(dest, operand, start_indices);
718 }
719 let exec = crate::cost::for_len_tree(exec, KernelClass::Copy, self.total);
720 if !exec.is_serial() {
721 return self.execute_parallel(dest, operand, start_indices, exec);
722 }
723
724 let mut state =
725 self.decode_replay_state(0, dest.offset(), operand.offset(), start_indices.offset())?;
726 let operand_data = operand.data();
727 let index_data = start_indices.data();
728
729 for _ in 0..self.total {
733 let mut source_offset = state.window_offset;
738 for ((&index_component_offset, &operand_stride), &operand_dim) in self
739 .replay
740 .index_component_offsets
741 .iter()
742 .zip(self.replay.index_operand_strides.iter())
743 .zip(self.spec.start_index_map.iter())
744 {
745 let index_offset = state.index_batch_offset + index_component_offset;
746 let start = unsafe { *index_data.as_ptr().offset(index_offset) }.to_i64();
749 let clamped = self.clamp_window_start(start, operand_dim);
750 source_offset += operand_stride * clamped as isize;
751 }
752
753 let value = unsafe { *operand_data.as_ptr().offset(source_offset) };
756 unsafe { dest.write_at(state.dest_offset, value) };
757 self.advance_replay_state(&mut state);
758 }
759 Ok(())
760 }
761
762 fn uses_rank_one_scalar_take_path(&self) -> bool {
763 self.operand_dims.len() == 1
764 && self.index_dims.len() == 1
765 && self.dest_dims.len() == 1
766 && self.operand_strides[0] == 1
767 && self.index_strides[0] == 1
768 && self.dest_strides[0] == 1
769 && self.spec.offset_dims.is_empty()
770 && self.spec.collapsed_slice_dims.as_slice() == [0]
771 && self.spec.start_index_map.as_slice() == [0]
772 && self.spec.index_vector_dim == 1
773 && self.spec.slice_sizes.as_slice() == [1]
774 }
775
776 fn execute_rank_one_scalar_take<T, I, W>(
777 &self,
778 dest: &mut W,
779 operand: &RawStridedRef<'_, T>,
780 start_indices: &RawStridedRef<'_, I>,
781 ) -> Result<()>
782 where
783 T: Copy,
784 I: GatherIndex,
785 W: OverwriteWriter<T>,
786 {
787 let mut dest_offset = dest.offset();
788 let mut index_offset = start_indices.offset();
789 let operand_offset = operand.offset();
790 let operand_data = operand.data();
791 let index_data = start_indices.data();
792
793 for _ in 0..self.total {
797 unsafe {
799 let start = (*index_data.as_ptr().offset(index_offset)).to_i64();
800 let source_offset = operand_offset + self.clamp_window_start(start, 0) as isize;
801 dest.write_at(dest_offset, *operand_data.as_ptr().offset(source_offset));
802 }
803 dest_offset += 1;
804 index_offset += 1;
805 }
806 Ok(())
807 }
808
809 fn execute_rank_one_scalar_take_parallel<T, I, W>(
810 &self,
811 dest: &mut W,
812 operand: &RawStridedRef<'_, T>,
813 start_indices: &RawStridedRef<'_, I>,
814 exec: Exec<'_>,
815 ) -> Result<()>
816 where
817 T: Copy + Send + Sync,
818 I: GatherIndex,
819 W: OverwriteWriter<T>,
820 {
821 let dest_offset = dest.offset();
822 let operand_offset = operand.offset();
823 let index_offset = start_indices.offset();
824 let dest_ptr = crate::threading::SendPtr(unsafe { dest.data_ptr() });
826 let operand_ptr = crate::threading::SendPtr(operand.data().as_ptr() as *mut T);
827 let index_ptr = crate::threading::SendPtr(start_indices.data().as_ptr() as *mut I);
828
829 crate::threading::parallel_map_reduce(
830 0..self.total,
831 exec,
832 &|range| {
833 let dest_ptr = dest_ptr.as_ptr();
834 let operand_ptr = operand_ptr.as_const();
835 let index_ptr = index_ptr.as_const();
836 for position in range {
839 let position = position as isize;
840 unsafe {
843 let start = (*index_ptr.offset(index_offset + position)).to_i64();
844 let source_offset =
845 operand_offset + self.clamp_window_start(start, 0) as isize;
846 dest_ptr
847 .offset(dest_offset + position)
848 .write(operand_ptr.offset(source_offset).read());
849 }
850 }
851 Ok(())
852 },
853 &|left, right| left.and(right),
854 )
855 }
856
857 fn execute_parallel<T, I, W>(
858 &self,
859 dest: &mut W,
860 operand: &RawStridedRef<'_, T>,
861 start_indices: &RawStridedRef<'_, I>,
862 exec: Exec<'_>,
863 ) -> Result<()>
864 where
865 T: Copy + Send + Sync,
866 I: GatherIndex,
867 W: OverwriteWriter<T>,
868 {
869 let dest_offset_base = dest.offset();
870 let operand_offset_base = operand.offset();
871 let index_offset_base = start_indices.offset();
872 let dest_ptr = crate::threading::SendPtr(unsafe { dest.data_ptr() });
874 let operand_ptr = crate::threading::SendPtr(operand.data().as_ptr() as *mut T);
875 let index_ptr = crate::threading::SendPtr(start_indices.data().as_ptr() as *mut I);
876
877 crate::threading::parallel_map_reduce(
878 0..self.total,
879 exec,
880 &|range| {
881 let mut state = self.decode_replay_state(
882 range.start,
883 dest_offset_base,
884 operand_offset_base,
885 index_offset_base,
886 )?;
887 let dest_ptr = dest_ptr.as_ptr();
888 let operand_ptr = operand_ptr.as_const();
889 let index_ptr = index_ptr.as_const();
890
891 for _ in range {
896 let mut source_offset = state.window_offset;
900 for ((&index_component_offset, &operand_stride), &operand_dim) in self
901 .replay
902 .index_component_offsets
903 .iter()
904 .zip(self.replay.index_operand_strides.iter())
905 .zip(self.spec.start_index_map.iter())
906 {
907 let index_offset = state.index_batch_offset + index_component_offset;
908 let start = unsafe { (*index_ptr.offset(index_offset)).to_i64() };
911 let clamped = self.clamp_window_start(start, operand_dim);
912 source_offset += operand_stride * clamped as isize;
913 }
914
915 unsafe {
918 dest_ptr
919 .offset(state.dest_offset)
920 .write(operand_ptr.offset(source_offset).read());
921 }
922 self.advance_replay_state(&mut state);
923 }
924 Ok(())
925 },
926 &|left, right| left.and(right),
927 )
928 }
929
930 fn check_call<T, I, W>(
931 &self,
932 dest: &W,
933 operand: &RawStridedRef<'_, T>,
934 start_indices: &RawStridedRef<'_, I>,
935 ) -> Result<()>
936 where
937 W: OverwriteWriter<T>,
938 {
939 if dest.dims() != &self.dest_dims[..]
940 || dest.strides() != &self.dest_strides[..]
941 || operand.dims() != &self.operand_dims[..]
942 || operand.strides() != &self.operand_strides[..]
943 || start_indices.dims() != &self.index_dims[..]
944 || start_indices.strides() != &self.index_strides[..]
945 {
946 return Err(StridedError::PlanLayoutMismatch);
947 }
948 Ok(())
949 }
950
951 fn decode_replay_state(
952 &self,
953 mut linear: usize,
954 dest_offset_base: isize,
955 operand_offset_base: isize,
956 index_offset_base: isize,
957 ) -> Result<GatherReplayState> {
958 let mut coords = AxisVec::with_capacity(self.dest_dims.len());
959 let mut dest_offset = dest_offset_base;
960 let mut window_offset = operand_offset_base;
961 let mut index_batch_offset = index_offset_base;
962 for (axis, &dim) in self.dest_dims.iter().enumerate() {
963 let coord = linear % dim;
964 linear /= dim;
965 let replay_axis = self.replay.axes[axis];
966 coords.push(coord);
967 dest_offset = checked_offset_add(dest_offset, replay_axis.dest_step, coord)?;
968 window_offset = checked_offset_add(window_offset, replay_axis.window_step, coord)?;
969 index_batch_offset =
970 checked_offset_add(index_batch_offset, replay_axis.index_batch_step, coord)?;
971 }
972 Ok(GatherReplayState {
973 coords,
974 dest_offset,
975 window_offset,
976 index_batch_offset,
977 })
978 }
979
980 #[inline]
981 fn advance_replay_state(&self, state: &mut GatherReplayState) {
982 for (axis, replay_axis) in self.replay.axes.iter().enumerate() {
983 let coord = state.coords[axis];
984 if coord + 1 < self.dest_dims[axis] {
985 state.coords[axis] = coord + 1;
986 state.dest_offset += replay_axis.dest_step;
987 state.window_offset += replay_axis.window_step;
988 state.index_batch_offset += replay_axis.index_batch_step;
989 return;
990 }
991 state.coords[axis] = 0;
992 state.dest_offset += replay_axis.dest_reset;
993 state.window_offset += replay_axis.window_reset;
994 state.index_batch_offset += replay_axis.index_batch_reset;
995 }
996 }
997
998 #[inline]
999 fn clamp_window_start(&self, start: i64, operand_dim: usize) -> usize {
1000 let dim_size = self.operand_dims[operand_dim];
1001 let window_size = self.spec.slice_sizes[operand_dim];
1002 let max_start = dim_size.saturating_sub(window_size) as i64;
1003 start.clamp(0, max_start) as usize
1004 }
1005}
1006
1007impl DynamicSlicePlan {
1008 pub fn compile(
1027 operand_dims: &[usize],
1028 operand_strides: &[isize],
1029 start_dims: &[usize],
1030 start_strides: &[isize],
1031 dest_dims: &[usize],
1032 dest_strides: &[isize],
1033 slice_sizes: &[usize],
1034 ) -> Result<Self> {
1035 if operand_dims.len() != operand_strides.len()
1036 || start_dims.len() != start_strides.len()
1037 || dest_dims.len() != dest_strides.len()
1038 {
1039 return Err(StridedError::StrideLengthMismatch);
1040 }
1041 if slice_sizes.len() != operand_dims.len() {
1042 return Err(StridedError::RankMismatch(
1043 slice_sizes.len(),
1044 operand_dims.len(),
1045 ));
1046 }
1047 validate_start_vector(start_dims, operand_dims.len())?;
1048 checked_total_len(operand_dims)?;
1049 checked_total_len(start_dims)?;
1050 let total = checked_total_len(dest_dims)?;
1051 validate_layout_span(operand_dims, operand_strides)?;
1052 validate_layout_span(start_dims, start_strides)?;
1053 validate_layout_span(dest_dims, dest_strides)?;
1054 if dest_dims != slice_sizes {
1055 return Err(StridedError::ShapeMismatch(
1056 dest_dims.to_vec(),
1057 slice_sizes.to_vec(),
1058 ));
1059 }
1060 if !crate::layout_check::is_injective_layout(dest_dims, dest_strides) {
1061 return Err(StridedError::NonInjectiveOutputLayout);
1062 }
1063 validate_window_sizes(operand_dims, slice_sizes)?;
1064 let replay = WindowReplay::compile(slice_sizes, operand_strides, dest_strides)?;
1065
1066 Ok(Self {
1067 operand_dims: operand_dims.into(),
1068 operand_strides: operand_strides.into(),
1069 start_dims: start_dims.into(),
1070 start_strides: start_strides.into(),
1071 dest_dims: dest_dims.into(),
1072 dest_strides: dest_strides.into(),
1073 slice_sizes: slice_sizes.into(),
1074 total,
1075 window: fuse_pair_layout(slice_sizes, dest_strides, operand_strides),
1076 replay,
1077 })
1078 }
1079
1080 pub fn execute<T, I>(
1090 &self,
1091 dest: &mut RawStridedMut<'_, T>,
1092 operand: &RawStridedRef<'_, T>,
1093 starts: &RawStridedRef<'_, I>,
1094 exec: Exec<'_>,
1095 ) -> Result<()>
1096 where
1097 T: Copy + Send + Sync,
1098 I: GatherIndex,
1099 {
1100 self.execute_with_writer(dest, operand, starts, exec)
1101 }
1102
1103 pub(crate) fn execute_uninit<T, I>(
1104 &self,
1105 dest: &mut RawStridedMut<'_, MaybeUninit<T>>,
1106 operand: &RawStridedRef<'_, T>,
1107 starts: &RawStridedRef<'_, I>,
1108 exec: Exec<'_>,
1109 ) -> Result<()>
1110 where
1111 T: Copy + Send + Sync,
1112 I: GatherIndex,
1113 {
1114 self.execute_with_writer(dest, operand, starts, exec)
1115 }
1116
1117 fn execute_with_writer<T, I, W>(
1118 &self,
1119 dest: &mut W,
1120 operand: &RawStridedRef<'_, T>,
1121 starts: &RawStridedRef<'_, I>,
1122 exec: Exec<'_>,
1123 ) -> Result<()>
1124 where
1125 T: Copy + Send + Sync,
1126 I: GatherIndex,
1127 W: OverwriteWriter<T>,
1128 {
1129 self.check_call(dest, operand, starts)?;
1130 if self.total == 0 {
1131 return Ok(());
1132 }
1133 if self.uses_rank_one_contiguous_path() {
1134 return self.execute_rank_one_contiguous(dest, operand, starts, exec);
1135 }
1136 if let Some(window) = &self.window {
1137 return self.execute_fused_window(dest, operand, starts, window, exec);
1138 }
1139 let replay = &self.replay;
1140 let exec = crate::cost::for_len_tree(exec, KernelClass::Copy, self.total);
1141 if !exec.is_serial() {
1142 return self.execute_parallel(dest, operand, starts, exec, replay);
1143 }
1144
1145 let mut starts_storage = CoordScratch::new(self.operand_dims.len());
1146 let clamped_starts = starts_storage.as_mut_slice();
1147 read_clamped_starts(
1148 starts,
1149 &self.operand_dims,
1150 &self.slice_sizes,
1151 clamped_starts,
1152 )?;
1153 let source_base =
1154 checked_strided_offset(operand.offset(), &self.operand_strides, clamped_starts)?;
1155 let mut state = replay.decode(0, source_base, dest.offset())?;
1156 let operand_data = operand.data();
1157
1158 for _ in 0..self.total {
1162 let value = unsafe { *operand_data.as_ptr().offset(state.source_offset) };
1164 unsafe { dest.write_at(state.dest_offset, value) };
1167 replay.advance(&mut state);
1168 }
1169 Ok(())
1170 }
1171
1172 fn execute_fused_window<T, I, W>(
1178 &self,
1179 dest: &mut W,
1180 operand: &RawStridedRef<'_, T>,
1181 starts: &RawStridedRef<'_, I>,
1182 window: &FusedPairLayout,
1183 exec: Exec<'_>,
1184 ) -> Result<()>
1185 where
1186 T: Copy + Send + Sync,
1187 I: GatherIndex,
1188 W: OverwriteWriter<T>,
1189 {
1190 let mut starts_storage = CoordScratch::new(self.operand_dims.len());
1191 let clamped_starts = starts_storage.as_mut_slice();
1192 read_clamped_starts(
1193 starts,
1194 &self.operand_dims,
1195 &self.slice_sizes,
1196 clamped_starts,
1197 )?;
1198 let source_base =
1199 checked_strided_offset(operand.offset(), &self.operand_strides, clamped_starts)?;
1200 let dest_base = dest.offset();
1201 let dest_ptr = unsafe { dest.data_ptr() }.cast::<MaybeUninit<T>>();
1203 unsafe {
1213 replay_fused_raw(
1214 dest_ptr,
1215 dest_base,
1216 operand.data().as_ptr(),
1217 source_base,
1218 window,
1219 |slot: &mut MaybeUninit<T>, value: T| *slot = MaybeUninit::new(value),
1220 exec,
1221 );
1222 }
1223 Ok(())
1224 }
1225
1226 #[inline]
1227 fn uses_rank_one_contiguous_path(&self) -> bool {
1228 self.operand_dims.len() == 1 && self.operand_strides[0] == 1 && self.dest_strides[0] == 1
1229 }
1230
1231 fn execute_rank_one_contiguous<T, I, W>(
1232 &self,
1233 dest: &mut W,
1234 operand: &RawStridedRef<'_, T>,
1235 starts: &RawStridedRef<'_, I>,
1236 exec: Exec<'_>,
1237 ) -> Result<()>
1238 where
1239 T: Copy + Send + Sync,
1240 I: GatherIndex,
1241 W: OverwriteWriter<T>,
1242 {
1243 let mut clamped_starts = [0usize; 1];
1244 read_clamped_starts(
1245 starts,
1246 &self.operand_dims,
1247 &self.slice_sizes,
1248 &mut clamped_starts,
1249 )?;
1250 let source_start = checked_offset_add(operand.offset(), 1, clamped_starts[0])?;
1251 let source_start =
1252 usize::try_from(source_start).map_err(|_| StridedError::OffsetOverflow)?;
1253 let dest_start =
1254 usize::try_from(dest.offset()).map_err(|_| StridedError::OffsetOverflow)?;
1255 let source_end = source_start
1256 .checked_add(self.total)
1257 .ok_or(StridedError::OffsetOverflow)?;
1258 let source = operand
1259 .data()
1260 .get(source_start..source_end)
1261 .ok_or(StridedError::OffsetOverflow)?;
1262 let dest_ptr = unsafe { dest.data_ptr() };
1264 unsafe {
1275 crate::threading::copy_contiguous(
1278 source.as_ptr(),
1279 dest_ptr.add(dest_start),
1280 self.total,
1281 exec,
1282 );
1283 }
1284 Ok(())
1285 }
1286
1287 fn execute_parallel<T, I, W>(
1288 &self,
1289 dest: &mut W,
1290 operand: &RawStridedRef<'_, T>,
1291 starts: &RawStridedRef<'_, I>,
1292 exec: Exec<'_>,
1293 replay: &WindowReplay,
1294 ) -> Result<()>
1295 where
1296 T: Copy + Send + Sync,
1297 I: GatherIndex,
1298 W: OverwriteWriter<T>,
1299 {
1300 let mut clamped_starts: AxisVec<usize> = (0..self.operand_dims.len()).map(|_| 0).collect();
1301 read_clamped_starts(
1302 starts,
1303 &self.operand_dims,
1304 &self.slice_sizes,
1305 &mut clamped_starts,
1306 )?;
1307 let source_base =
1308 checked_strided_offset(operand.offset(), &self.operand_strides, &clamped_starts)?;
1309 let dest_base = dest.offset();
1310 let operand_ptr = crate::threading::SendPtr(operand.data().as_ptr() as *mut T);
1311 let dest_ptr = crate::threading::SendPtr(unsafe { dest.data_ptr() });
1313
1314 crate::threading::parallel_map_reduce(
1315 0..self.total,
1316 exec,
1317 &|range| {
1318 let mut state = replay.decode(range.start, source_base, dest_base)?;
1319 let operand_ptr = operand_ptr.as_const();
1320 let dest_ptr = dest_ptr.as_ptr();
1321
1322 for _ in range {
1326 unsafe {
1329 dest_ptr
1330 .offset(state.dest_offset)
1331 .write(operand_ptr.offset(state.source_offset).read());
1332 }
1333 replay.advance(&mut state);
1334 }
1335 Ok(())
1336 },
1337 &|left, right| left.and(right),
1338 )
1339 }
1340
1341 fn check_call<T, I, W>(
1342 &self,
1343 dest: &W,
1344 operand: &RawStridedRef<'_, T>,
1345 starts: &RawStridedRef<'_, I>,
1346 ) -> Result<()>
1347 where
1348 W: OverwriteWriter<T>,
1349 {
1350 if dest.dims() != &self.dest_dims[..]
1351 || dest.strides() != &self.dest_strides[..]
1352 || operand.dims() != &self.operand_dims[..]
1353 || operand.strides() != &self.operand_strides[..]
1354 || starts.dims() != &self.start_dims[..]
1355 || starts.strides() != &self.start_strides[..]
1356 {
1357 return Err(StridedError::PlanLayoutMismatch);
1358 }
1359 Ok(())
1360 }
1361}
1362
1363impl DynamicUpdateSlicePlan {
1364 #[allow(clippy::too_many_arguments)]
1383 pub fn compile(
1384 operand_dims: &[usize],
1385 operand_strides: &[isize],
1386 start_dims: &[usize],
1387 start_strides: &[isize],
1388 update_dims: &[usize],
1389 update_strides: &[isize],
1390 dest_dims: &[usize],
1391 dest_strides: &[isize],
1392 ) -> Result<Self> {
1393 if operand_dims.len() != operand_strides.len()
1394 || start_dims.len() != start_strides.len()
1395 || update_dims.len() != update_strides.len()
1396 || dest_dims.len() != dest_strides.len()
1397 {
1398 return Err(StridedError::StrideLengthMismatch);
1399 }
1400 if update_dims.len() != operand_dims.len() {
1401 return Err(StridedError::RankMismatch(
1402 update_dims.len(),
1403 operand_dims.len(),
1404 ));
1405 }
1406 validate_start_vector(start_dims, operand_dims.len())?;
1407 checked_total_len(operand_dims)?;
1408 checked_total_len(start_dims)?;
1409 let total = checked_total_len(update_dims)?;
1410 validate_layout_span(operand_dims, operand_strides)?;
1411 validate_layout_span(start_dims, start_strides)?;
1412 validate_layout_span(update_dims, update_strides)?;
1413 validate_layout_span(dest_dims, dest_strides)?;
1414 if dest_dims != operand_dims {
1415 return Err(StridedError::ShapeMismatch(
1416 dest_dims.to_vec(),
1417 operand_dims.to_vec(),
1418 ));
1419 }
1420 if !crate::layout_check::is_injective_layout(dest_dims, dest_strides) {
1421 return Err(StridedError::NonInjectiveOutputLayout);
1422 }
1423 validate_window_sizes(operand_dims, update_dims)?;
1424 let copy_plan = CopyPlan::compile(operand_dims, dest_strides, operand_strides)?;
1425 let replay = WindowReplay::compile(update_dims, update_strides, dest_strides)?;
1426
1427 Ok(Self {
1428 operand_dims: operand_dims.into(),
1429 operand_strides: operand_strides.into(),
1430 start_dims: start_dims.into(),
1431 start_strides: start_strides.into(),
1432 update_dims: update_dims.into(),
1433 update_strides: update_strides.into(),
1434 dest_dims: dest_dims.into(),
1435 dest_strides: dest_strides.into(),
1436 total,
1437 copy_plan,
1438 window: fuse_pair_layout(update_dims, dest_strides, update_strides),
1439 replay,
1440 })
1441 }
1442
1443 pub fn execute<T, I>(
1455 &self,
1456 dest: &mut RawStridedMut<'_, T>,
1457 operand: &RawStridedRef<'_, T>,
1458 update: &RawStridedRef<'_, T>,
1459 starts: &RawStridedRef<'_, I>,
1460 exec: Exec<'_>,
1461 ) -> Result<()>
1462 where
1463 T: Copy + Send + Sync,
1464 I: GatherIndex,
1465 {
1466 let mut exec = exec;
1467 self.check_call(dest, operand, update, starts)?;
1468 let window = self.preflight_update_window(dest, update, starts)?;
1469 self.copy_plan.execute(dest, operand, exec.reborrow())?;
1470 self.execute_update_with_writer(dest, update, &window, exec)
1471 }
1472
1473 pub(crate) fn execute_uninit<'a, T, I>(
1477 &self,
1478 dest: &'a mut RawStridedMut<'a, MaybeUninit<T>>,
1479 operand: &RawStridedRef<'_, T>,
1480 update: &RawStridedRef<'_, T>,
1481 starts: &RawStridedRef<'_, I>,
1482 exec: Exec<'_>,
1483 ) -> Result<()>
1484 where
1485 T: Copy + Send + Sync,
1486 I: GatherIndex,
1487 {
1488 self.check_call(dest, operand, update, starts)?;
1489 let window = self.preflight_update_window(dest, update, starts)?;
1490 self.copy_plan
1491 .execute_uninit_then(dest, operand, exec, |mut receipt, exec| {
1492 self.execute_update_with_writer(&mut receipt, update, &window, exec)
1493 })?
1494 }
1495
1496 fn preflight_update_window<'a, T, I, W>(
1498 &self,
1499 dest: &W,
1500 update: &'a RawStridedRef<'_, T>,
1501 starts: &RawStridedRef<'_, I>,
1502 ) -> Result<UpdateWindow<'a, T>>
1503 where
1504 T: Copy,
1505 I: GatherIndex,
1506 W: OverwriteWriter<T>,
1507 {
1508 if self.total == 0 {
1509 return Ok(UpdateWindow::Empty);
1510 }
1511 let mut starts_storage = CoordScratch::new(self.operand_dims.len());
1512 let clamped_starts = starts_storage.as_mut_slice();
1513 read_clamped_starts(
1514 starts,
1515 &self.operand_dims,
1516 &self.update_dims,
1517 clamped_starts,
1518 )?;
1519 let dest_base = checked_strided_offset(dest.offset(), &self.dest_strides, clamped_starts)?;
1520 self.replay.source_span.covers(update.offset())?;
1523 self.replay.dest_span.covers(dest_base)?;
1524 if self.uses_rank_one_contiguous_path() {
1525 let update_start =
1526 usize::try_from(update.offset()).map_err(|_| StridedError::OffsetOverflow)?;
1527 let dest_start =
1528 usize::try_from(dest_base).map_err(|_| StridedError::OffsetOverflow)?;
1529 let update_end = update_start
1530 .checked_add(self.total)
1531 .ok_or(StridedError::OffsetOverflow)?;
1532 let run = update
1533 .data()
1534 .get(update_start..update_end)
1535 .ok_or(StridedError::OffsetOverflow)?;
1536 return Ok(UpdateWindow::RankOne {
1537 update: run,
1538 dest_start,
1539 });
1540 }
1541 Ok(UpdateWindow::Replay { dest_base })
1542 }
1543
1544 fn execute_update_with_writer<T, W>(
1545 &self,
1546 dest: &mut W,
1547 update: &RawStridedRef<'_, T>,
1548 window: &UpdateWindow<'_, T>,
1549 exec: Exec<'_>,
1550 ) -> Result<()>
1551 where
1552 T: Copy + Send + Sync,
1553 W: OverwriteWriter<T>,
1554 {
1555 let dest_base = match *window {
1556 UpdateWindow::Empty => return Ok(()),
1557 UpdateWindow::RankOne { update, dest_start } => {
1558 return self.execute_rank_one_contiguous(dest, update, dest_start, exec)
1559 }
1560 UpdateWindow::Replay { dest_base } => dest_base,
1561 };
1562 if let Some(fused) = &self.window {
1563 return self.execute_fused_window(dest, update, dest_base, fused, exec);
1564 }
1565 let replay = &self.replay;
1566 let exec = crate::cost::for_len_tree(exec, KernelClass::Copy, self.total);
1567 if !exec.is_serial() {
1568 return self.execute_update_parallel(dest, update, dest_base, exec);
1569 }
1570
1571 let mut state = replay.start(update.offset(), dest_base);
1572 let update_data = update.data();
1573
1574 for _ in 0..self.total {
1578 let value = unsafe { *update_data.as_ptr().offset(state.source_offset) };
1580 unsafe { dest.write_at(state.dest_offset, value) };
1583 replay.advance(&mut state);
1584 }
1585 Ok(())
1586 }
1587
1588 fn execute_fused_window<T, W>(
1591 &self,
1592 dest: &mut W,
1593 update: &RawStridedRef<'_, T>,
1594 dest_base: isize,
1595 window: &FusedPairLayout,
1596 exec: Exec<'_>,
1597 ) -> Result<()>
1598 where
1599 T: Copy + Send + Sync,
1600 W: OverwriteWriter<T>,
1601 {
1602 let dest_ptr = unsafe { dest.data_ptr() }.cast::<MaybeUninit<T>>();
1604 unsafe {
1612 replay_fused_raw(
1613 dest_ptr,
1614 dest_base,
1615 update.data().as_ptr(),
1616 update.offset(),
1617 window,
1618 |slot: &mut MaybeUninit<T>, value: T| *slot = MaybeUninit::new(value),
1619 exec,
1620 );
1621 }
1622 Ok(())
1623 }
1624
1625 #[inline]
1626 fn uses_rank_one_contiguous_path(&self) -> bool {
1627 self.operand_dims.len() == 1
1628 && self.operand_strides[0] == 1
1629 && self.update_strides[0] == 1
1630 && self.dest_strides[0] == 1
1631 }
1632
1633 fn execute_rank_one_contiguous<T, W>(
1634 &self,
1635 dest: &mut W,
1636 update: &[T],
1637 dest_start: usize,
1638 exec: Exec<'_>,
1639 ) -> Result<()>
1640 where
1641 T: Copy + Send + Sync,
1642 W: OverwriteWriter<T>,
1643 {
1644 let dest_ptr = unsafe { dest.data_ptr() };
1646 unsafe {
1661 crate::threading::copy_contiguous(
1664 update.as_ptr(),
1665 dest_ptr.add(dest_start),
1666 self.total,
1667 exec,
1668 );
1669 }
1670 Ok(())
1671 }
1672
1673 fn execute_update_parallel<T, W>(
1674 &self,
1675 dest: &mut W,
1676 update: &RawStridedRef<'_, T>,
1677 dest_base: isize,
1678 exec: Exec<'_>,
1679 ) -> Result<()>
1680 where
1681 T: Copy + Send + Sync,
1682 W: OverwriteWriter<T>,
1683 {
1684 let replay = &self.replay;
1685 let source_base = update.offset();
1686 let update_ptr = crate::threading::SendPtr(update.data().as_ptr() as *mut T);
1687 let dest_ptr = crate::threading::SendPtr(unsafe { dest.data_ptr() });
1689
1690 crate::threading::parallel_map_reduce(
1691 0..self.total,
1692 exec,
1693 &|range| {
1694 let mut state = replay.decode(range.start, source_base, dest_base)?;
1695 let update_ptr = update_ptr.as_const();
1696 let dest_ptr = dest_ptr.as_ptr();
1697
1698 for _ in range {
1703 unsafe {
1706 dest_ptr
1707 .offset(state.dest_offset)
1708 .write(update_ptr.offset(state.source_offset).read());
1709 }
1710 replay.advance(&mut state);
1711 }
1712 Ok(())
1713 },
1714 &|left, right| left.and(right),
1715 )
1716 }
1717
1718 fn check_call<T, I, W>(
1719 &self,
1720 dest: &W,
1721 operand: &RawStridedRef<'_, T>,
1722 update: &RawStridedRef<'_, T>,
1723 starts: &RawStridedRef<'_, I>,
1724 ) -> Result<()>
1725 where
1726 W: OverwriteWriter<T>,
1727 {
1728 if dest.dims() != &self.dest_dims[..]
1729 || dest.strides() != &self.dest_strides[..]
1730 || operand.dims() != &self.operand_dims[..]
1731 || operand.strides() != &self.operand_strides[..]
1732 || update.dims() != &self.update_dims[..]
1733 || update.strides() != &self.update_strides[..]
1734 || starts.dims() != &self.start_dims[..]
1735 || starts.strides() != &self.start_strides[..]
1736 {
1737 return Err(StridedError::PlanLayoutMismatch);
1738 }
1739 Ok(())
1740 }
1741}
1742
1743impl ScatterPlan {
1744 #[allow(clippy::too_many_arguments)]
1765 pub fn compile(
1766 operand_dims: &[usize],
1767 operand_strides: &[isize],
1768 index_dims: &[usize],
1769 index_strides: &[isize],
1770 update_dims: &[usize],
1771 update_strides: &[isize],
1772 dest_dims: &[usize],
1773 dest_strides: &[isize],
1774 spec: ScatterSpec,
1775 ) -> Result<Self> {
1776 if operand_dims.len() != operand_strides.len()
1777 || index_dims.len() != index_strides.len()
1778 || update_dims.len() != update_strides.len()
1779 || dest_dims.len() != dest_strides.len()
1780 {
1781 return Err(StridedError::StrideLengthMismatch);
1782 }
1783 checked_total_len(operand_dims)?;
1784 checked_total_len(index_dims)?;
1785 checked_total_len(update_dims)?;
1786 if dest_dims != operand_dims {
1787 return Err(StridedError::ShapeMismatch(
1788 dest_dims.to_vec(),
1789 operand_dims.to_vec(),
1790 ));
1791 }
1792 if !crate::layout_check::is_injective_layout(dest_dims, dest_strides) {
1793 return Err(StridedError::NonInjectiveOutputLayout);
1794 }
1795
1796 let operand_rank = operand_dims.len();
1797 validate_unique_axes(&spec.inserted_window_dims, operand_rank)?;
1798 validate_unique_axes(&spec.scatter_dims_to_operand_dims, operand_rank)?;
1799 if spec.index_vector_dim > index_dims.len() {
1800 return Err(StridedError::InvalidAxis {
1801 axis: spec.index_vector_dim,
1802 rank: index_dims.len() + 1,
1803 });
1804 }
1805 let index_vector_size = if spec.index_vector_dim == index_dims.len() {
1806 1
1807 } else {
1808 index_dims[spec.index_vector_dim]
1809 };
1810 if index_vector_size != spec.scatter_dims_to_operand_dims.len() {
1811 return Err(StridedError::RankMismatch(
1812 index_vector_size,
1813 spec.scatter_dims_to_operand_dims.len(),
1814 ));
1815 }
1816
1817 let batch_shape = index_batch_shape(index_dims, spec.index_vector_dim);
1818 let window_dims = operand_window_dims(operand_rank, &spec.inserted_window_dims);
1819 if spec.update_window_dims.len() != window_dims.len() {
1820 return Err(StridedError::RankMismatch(
1821 spec.update_window_dims.len(),
1822 window_dims.len(),
1823 ));
1824 }
1825
1826 let update_rank = update_dims.len();
1827 let expected_batch_rank = update_rank
1828 .checked_sub(spec.update_window_dims.len())
1829 .ok_or(StridedError::RankMismatch(
1830 spec.update_window_dims.len(),
1831 update_rank,
1832 ))?;
1833 if expected_batch_rank != batch_shape.len() {
1834 return Err(StridedError::RankMismatch(
1835 expected_batch_rank,
1836 batch_shape.len(),
1837 ));
1838 }
1839 validate_unique_axes(&spec.update_window_dims, update_rank)?;
1840
1841 let mut is_update_window_dim: AxisVec<bool> = (0..update_rank).map(|_| false).collect();
1842 for &axis in &spec.update_window_dims {
1843 is_update_window_dim[axis] = true;
1844 }
1845
1846 let mut batch_axis = 0usize;
1847 for axis in 0..update_rank {
1848 if !is_update_window_dim[axis] {
1849 if update_dims[axis] != batch_shape[batch_axis] {
1850 return Err(StridedError::ShapeMismatch(
1851 update_dims.to_vec(),
1852 expected_scatter_update_shape(&batch_shape, &spec, update_dims).to_vec(),
1853 ));
1854 }
1855 batch_axis += 1;
1856 }
1857 }
1858
1859 let mut window_shape: AxisVec<usize> = (0..operand_rank).map(|_| 1).collect();
1860 let mut window_shape_updates: AxisVec<usize> =
1861 AxisVec::with_capacity(spec.update_window_dims.len());
1862 for (pos, &update_axis) in spec.update_window_dims.iter().enumerate() {
1863 let dim = update_dims[update_axis];
1864 window_shape_updates.push(dim);
1865 window_shape[window_dims[pos]] = dim;
1866 }
1867 validate_window_sizes(operand_dims, &window_shape)?;
1868
1869 let batch_elems = checked_total_len(&batch_shape)?;
1870 let window_elems = checked_total_len(&window_shape_updates)?;
1871 let copy_plan = CopyPlan::compile(operand_dims, dest_strides, operand_strides)?;
1872 let replay = ScatterReplay::compile(
1873 &batch_shape,
1874 index_dims,
1875 index_strides,
1876 spec.index_vector_dim,
1877 spec.scatter_dims_to_operand_dims.len(),
1878 update_dims,
1879 update_strides,
1880 &spec.update_window_dims,
1881 &is_update_window_dim,
1882 &window_shape_updates,
1883 &window_dims,
1884 dest_strides,
1885 )?;
1886
1887 Ok(Self {
1888 operand_dims: operand_dims.into(),
1889 operand_strides: operand_strides.into(),
1890 index_dims: index_dims.into(),
1891 index_strides: index_strides.into(),
1892 update_dims: update_dims.into(),
1893 update_strides: update_strides.into(),
1894 dest_dims: dest_dims.into(),
1895 dest_strides: dest_strides.into(),
1896 spec,
1897 window_shape,
1898 batch_elems,
1899 window_elems,
1900 copy_plan,
1901 replay,
1902 })
1903 }
1904
1905 #[inline(always)]
1914 pub fn execute<T, I>(
1915 &self,
1916 dest: &mut RawStridedMut<'_, T>,
1917 operand: &RawStridedRef<'_, T>,
1918 scatter_indices: &RawStridedRef<'_, I>,
1919 updates: &RawStridedRef<'_, T>,
1920 exec: Exec<'_>,
1921 ) -> Result<()>
1922 where
1923 T: Copy + Add<Output = T> + Send + Sync,
1924 I: GatherIndex,
1925 {
1926 self.check_call(dest, operand, scatter_indices, updates)?;
1927 self.copy_plan.execute(dest, operand, exec)?;
1928 self.execute_updates(dest, scatter_indices, updates, |a, b| a + b)
1929 }
1930
1931 pub(crate) fn execute_uninit<'a, T, I>(
1934 &self,
1935 dest: &'a mut RawStridedMut<'a, MaybeUninit<T>>,
1936 operand: &RawStridedRef<'_, T>,
1937 scatter_indices: &RawStridedRef<'_, I>,
1938 updates: &RawStridedRef<'_, T>,
1939 combine: fn(T, T) -> T,
1940 exec: Exec<'_>,
1941 ) -> Result<()>
1942 where
1943 T: Copy + Add<Output = T> + Send + Sync,
1944 I: GatherIndex,
1945 {
1946 self.check_call(dest, operand, scatter_indices, updates)?;
1947 self.copy_plan
1948 .execute_uninit_then(dest, operand, exec, |mut receipt, _| {
1949 self.execute_updates(&mut receipt, scatter_indices, updates, combine)
1950 })?
1951 }
1952
1953 #[inline(always)]
1954 fn execute_updates<T, I, W, F>(
1955 &self,
1956 dest: &mut W,
1957 scatter_indices: &RawStridedRef<'_, I>,
1958 updates: &RawStridedRef<'_, T>,
1959 combine: F,
1960 ) -> Result<()>
1961 where
1962 T: Copy + Send + Sync,
1963 I: GatherIndex,
1964 W: ReadModifyWrite<T>,
1965 F: Fn(T, T) -> T + Copy,
1966 {
1967 if self.batch_elems == 0 || self.window_elems == 0 {
1968 return Ok(());
1969 }
1970 if self.uses_rank_one_scalar_update_path() {
1971 return self.execute_rank_one_scalar_updates(dest, scatter_indices, updates, combine);
1972 }
1973 self.execute_generic_updates(dest, scatter_indices, updates, combine)
1974 }
1975
1976 #[inline(never)]
1977 fn execute_generic_updates<T, I, W, F>(
1978 &self,
1979 dest: &mut W,
1980 scatter_indices: &RawStridedRef<'_, I>,
1981 updates: &RawStridedRef<'_, T>,
1982 combine: F,
1983 ) -> Result<()>
1984 where
1985 T: Copy + Send + Sync,
1986 I: GatherIndex,
1987 W: ReadModifyWrite<T>,
1988 F: Fn(T, T) -> T + Copy,
1989 {
1990 let replay = &self.replay;
1993
1994 let mut operand_base_storage = CoordScratch::new(self.operand_dims.len());
1995 let operand_base = operand_base_storage.as_mut_slice();
1996 let mut batch_state = replay
1997 .batch
1998 .decode(0, scatter_indices.offset(), updates.offset())?;
1999 let index_data = scatter_indices.data();
2000 let update_data = updates.data();
2001
2002 for _ in 0..self.batch_elems {
2005 operand_base.fill(0);
2006 for (&component_offset, &operand_axis) in replay
2007 .index_component_offsets
2008 .iter()
2009 .zip(self.spec.scatter_dims_to_operand_dims.iter())
2010 {
2011 let index_offset = batch_state
2012 .source_offset
2013 .checked_add(component_offset)
2014 .ok_or(StridedError::OffsetOverflow)?;
2015 let start = unsafe { *index_data.as_ptr().offset(index_offset) }.to_i64();
2018 operand_base[operand_axis] = clamp_window_start(
2019 start,
2020 self.operand_dims[operand_axis],
2021 self.window_shape[operand_axis],
2022 );
2023 }
2024
2025 let dest_base = checked_strided_offset(dest.offset(), dest.strides(), operand_base)?;
2026 let mut window_state = replay
2027 .window
2028 .decode(0, batch_state.dest_offset, dest_base)?;
2029 for _ in 0..self.window_elems {
2030 let value = unsafe { *update_data.as_ptr().offset(window_state.source_offset) };
2033 unsafe { dest.add_at(window_state.dest_offset, value, combine) };
2034 replay.window.advance(&mut window_state);
2035 }
2036 replay.batch.advance(&mut batch_state);
2037 }
2038 Ok(())
2039 }
2040
2041 fn uses_rank_one_scalar_update_path(&self) -> bool {
2042 self.operand_dims.len() == 1
2043 && self.index_dims.len() == 2
2044 && self.update_dims.len() == 1
2045 && self.dest_dims.len() == 1
2046 && self.operand_strides[0] == 1
2047 && self.index_strides[0] == 1
2048 && self.update_strides[0] == 1
2049 && self.dest_strides[0] == 1
2050 && self.index_dims[1] == 1
2051 && self.spec.update_window_dims.is_empty()
2052 && self.spec.inserted_window_dims.as_slice() == [0]
2053 && self.spec.scatter_dims_to_operand_dims.as_slice() == [0]
2054 && self.spec.index_vector_dim == 1
2055 && self.window_elems == 1
2056 }
2057
2058 #[inline(always)]
2059 fn execute_rank_one_scalar_updates<T, I, W, F>(
2060 &self,
2061 dest: &mut W,
2062 scatter_indices: &RawStridedRef<'_, I>,
2063 updates: &RawStridedRef<'_, T>,
2064 combine: F,
2065 ) -> Result<()>
2066 where
2067 T: Copy,
2068 I: GatherIndex,
2069 W: ReadModifyWrite<T>,
2070 F: Fn(T, T) -> T + Copy,
2071 {
2072 let mut index_offset = scatter_indices.offset();
2073 let mut update_offset = updates.offset();
2074 let dest_offset = dest.offset();
2075 let index_data = scatter_indices.data();
2076 let update_data = updates.data();
2077 let dest_ptr = unsafe { dest.data_ptr() };
2079
2080 for _ in 0..self.batch_elems {
2083 unsafe {
2086 let start = (*index_data.as_ptr().offset(index_offset)).to_i64();
2087 let output_offset =
2088 dest_offset + clamp_window_start(start, self.operand_dims[0], 1) as isize;
2089 let output = dest_ptr.offset(output_offset);
2090 output.write(combine(
2091 output.read(),
2092 *update_data.as_ptr().offset(update_offset),
2093 ));
2094 }
2095 index_offset += 1;
2096 update_offset += 1;
2097 }
2098 Ok(())
2099 }
2100
2101 fn check_call<T, I, W>(
2102 &self,
2103 dest: &W,
2104 operand: &RawStridedRef<'_, T>,
2105 scatter_indices: &RawStridedRef<'_, I>,
2106 updates: &RawStridedRef<'_, T>,
2107 ) -> Result<()>
2108 where
2109 W: OverwriteWriter<T>,
2110 {
2111 if dest.dims() != &self.dest_dims[..]
2112 || dest.strides() != &self.dest_strides[..]
2113 || operand.dims() != &self.operand_dims[..]
2114 || operand.strides() != &self.operand_strides[..]
2115 || scatter_indices.dims() != &self.index_dims[..]
2116 || scatter_indices.strides() != &self.index_strides[..]
2117 || updates.dims() != &self.update_dims[..]
2118 || updates.strides() != &self.update_strides[..]
2119 {
2120 return Err(StridedError::PlanLayoutMismatch);
2121 }
2122 Ok(())
2123 }
2124}
2125
2126fn validate_unique_axes(axes: &[usize], rank: usize) -> Result<()> {
2127 let mut seen: InlineVec<bool> = InlineVec::new();
2130 seen.resize(rank, false);
2131 for &axis in axes {
2132 if axis >= rank {
2133 return Err(StridedError::InvalidAxis { axis, rank });
2134 }
2135 if seen[axis] {
2136 return Err(StridedError::InvalidAxis { axis, rank });
2137 }
2138 seen[axis] = true;
2139 }
2140 Ok(())
2141}
2142
2143fn validate_start_vector(start_dims: &[usize], operand_rank: usize) -> Result<()> {
2144 if start_dims.len() != 1 {
2145 return Err(StridedError::RankMismatch(start_dims.len(), 1));
2146 }
2147 if start_dims[0] != operand_rank {
2148 return Err(StridedError::RankMismatch(start_dims[0], operand_rank));
2149 }
2150 Ok(())
2151}
2152
2153fn validate_window_sizes(operand_dims: &[usize], window_sizes: &[usize]) -> Result<()> {
2154 if operand_dims.len() != window_sizes.len() {
2155 return Err(StridedError::RankMismatch(
2156 window_sizes.len(),
2157 operand_dims.len(),
2158 ));
2159 }
2160 for (axis, (&window, &dim)) in window_sizes.iter().zip(operand_dims.iter()).enumerate() {
2161 if window > dim {
2162 return Err(StridedError::InvalidAxis {
2163 axis,
2164 rank: operand_dims.len(),
2165 });
2166 }
2167 }
2168 Ok(())
2169}
2170
2171fn read_clamped_starts<I>(
2172 starts: &RawStridedRef<'_, I>,
2173 operand_dims: &[usize],
2174 window_sizes: &[usize],
2175 out: &mut [usize],
2176) -> Result<()>
2177where
2178 I: GatherIndex,
2179{
2180 debug_assert_eq!(operand_dims.len(), window_sizes.len());
2181 debug_assert_eq!(operand_dims.len(), out.len());
2182 for axis in 0..operand_dims.len() {
2183 let offset = checked_offset_add(starts.offset(), starts.strides()[0], axis)?;
2184 let start = unsafe { *starts.data().as_ptr().offset(offset) }.to_i64();
2185 out[axis] = clamp_window_start(start, operand_dims[axis], window_sizes[axis]);
2186 }
2187 Ok(())
2188}
2189
2190#[inline]
2191fn clamp_window_start(start: i64, dim_size: usize, window_size: usize) -> usize {
2192 let max_start = dim_size.saturating_sub(window_size) as i64;
2193 start.clamp(0, max_start) as usize
2194}
2195
2196fn expected_scatter_update_shape(
2197 batch_shape: &[usize],
2198 spec: &ScatterSpec,
2199 update_dims: &[usize],
2200) -> AxisVec<usize> {
2201 let mut expected: AxisVec<usize> = AxisVec::with_capacity(update_dims.len());
2202 let mut batch_axis = 0usize;
2203 for axis in 0..update_dims.len() {
2204 if spec.update_window_dims.contains(&axis) {
2205 expected.push(update_dims[axis]);
2206 } else {
2207 expected.push(batch_shape[batch_axis]);
2208 batch_axis += 1;
2209 }
2210 }
2211 expected
2212}
2213
2214fn operand_window_dims(rank: usize, collapsed_slice_dims: &[usize]) -> AxisVec<usize> {
2215 (0..rank)
2216 .filter(|axis| !collapsed_slice_dims.contains(axis))
2217 .collect()
2218}
2219
2220fn index_batch_shape(index_dims: &[usize], index_vector_dim: usize) -> AxisVec<usize> {
2221 if index_vector_dim == index_dims.len() {
2222 return index_dims.into();
2223 }
2224 index_dims
2225 .iter()
2226 .enumerate()
2227 .filter_map(|(axis, &dim)| (axis != index_vector_dim).then_some(dim))
2228 .collect()
2229}
2230
2231fn validate_layout_span(dims: &[usize], strides: &[isize]) -> Result<OffsetSpan> {
2233 if dims.len() != strides.len() {
2234 return Err(StridedError::StrideLengthMismatch);
2235 }
2236 let mut span = OffsetSpan::default();
2237 for (&dim, &stride) in dims.iter().zip(strides.iter()) {
2238 let last =
2239 isize::try_from(dim.saturating_sub(1)).map_err(|_| StridedError::OffsetOverflow)?;
2240 let extent = stride
2241 .checked_mul(last)
2242 .ok_or(StridedError::OffsetOverflow)?;
2243 if extent < 0 {
2244 span.min = span
2245 .min
2246 .checked_add(extent)
2247 .ok_or(StridedError::OffsetOverflow)?;
2248 } else {
2249 span.max = span
2250 .max
2251 .checked_add(extent)
2252 .ok_or(StridedError::OffsetOverflow)?;
2253 }
2254 }
2255 Ok(span)
2256}
2257
2258fn checked_replay_reset(dim: usize, step: isize) -> Result<isize> {
2259 if dim == 0 {
2260 return Ok(0);
2261 }
2262 let last = isize::try_from(dim - 1).map_err(|_| StridedError::OffsetOverflow)?;
2263 step.checked_mul(last)
2264 .and_then(isize::checked_neg)
2265 .ok_or(StridedError::OffsetOverflow)
2266}
2267
2268fn checked_total_len(dims: &[usize]) -> Result<usize> {
2269 if dims.is_empty() {
2270 return Ok(1);
2271 }
2272 dims.iter()
2273 .try_fold(1usize, |acc, &dim| acc.checked_mul(dim))
2274 .ok_or(StridedError::OffsetOverflow)
2275}
2276
2277fn checked_strided_offset(base: isize, strides: &[isize], index: &[usize]) -> Result<isize> {
2278 let mut offset = base;
2279 for (&stride, &coord) in strides.iter().zip(index.iter()) {
2280 offset = checked_offset_add(offset, stride, coord)?;
2281 }
2282 Ok(offset)
2283}
2284
2285fn checked_offset_add(base: isize, stride: isize, coord: usize) -> Result<isize> {
2286 let coord = isize::try_from(coord).map_err(|_| StridedError::OffsetOverflow)?;
2287 let scaled = stride
2288 .checked_mul(coord)
2289 .ok_or(StridedError::OffsetOverflow)?;
2290 base.checked_add(scaled).ok_or(StridedError::OffsetOverflow)
2291}
2292
2293struct CoordScratch {
2294 inline: [usize; RAW_FUSED_RANK_LIMIT],
2295 heap: Option<Vec<usize>>,
2296 len: usize,
2297}
2298
2299impl CoordScratch {
2300 fn new(len: usize) -> Self {
2301 if len <= RAW_FUSED_RANK_LIMIT {
2302 Self {
2303 inline: [0; RAW_FUSED_RANK_LIMIT],
2304 heap: None,
2305 len,
2306 }
2307 } else {
2308 Self {
2309 inline: [0; RAW_FUSED_RANK_LIMIT],
2310 heap: Some(vec![0; len]),
2311 len,
2312 }
2313 }
2314 }
2315
2316 fn as_mut_slice(&mut self) -> &mut [usize] {
2317 match &mut self.heap {
2318 Some(heap) => heap,
2319 None => &mut self.inline[..self.len],
2320 }
2321 }
2322}
2323
2324#[cfg(test)]
2325#[path = "gather_plan/tests/tests.rs"]
2326mod tests;
2327
2328#[cfg(test)]
2329#[path = "gather_plan/tests/parallel_tests.rs"]
2330mod parallel_tests;