1use crate::kernel::{
4 build_plan_fused, ensure_same_shape, for_each_inner_block_preordered, same_contiguous_layout,
5 sequential_contiguous_layout, total_len,
6};
7use crate::simd;
8use crate::view::{col_major_strides, StridedArray, StridedView, StridedViewMut};
9use crate::{Exec, Result, StridedError};
10use core::num::NonZeroUsize;
11use std::ops::Range;
12use strided_view::ElementOp;
13
14use crate::cost::KernelClass;
15use crate::fuse::compute_costs;
16use crate::inline::InlineVec;
17use crate::threading::{
18 for_each_inner_block_with_offsets, is_parallel, mapreduce_threaded_fold, SendPtr,
19};
20
21const FOLD_LANES: usize = 16;
23
24const AXIS_SWEEP_MIN_LEN: usize = 16;
27
28const AXIS_SWEEP_BLOCK_BYTES: usize = 64 * 1024;
30
31#[inline(never)]
38fn fold_lanes<U, R>(lanes: [U; FOLD_LANES], init: U, reduce_fn: &R) -> U
39where
40 R: Fn(U, U) -> U,
41{
42 lanes.into_iter().fold(init, reduce_fn)
43}
44
45#[inline(always)]
55fn fold_contiguous<T, Op, M, R, U>(src: &[T], init: U, map_fn: &M, reduce_fn: &R) -> U
56where
57 T: Copy,
58 Op: ElementOp<T>,
59 M: Fn(T) -> U,
60 R: Fn(U, U) -> U,
61 U: Clone,
62{
63 if src.len() < 2 * FOLD_LANES {
64 let mut acc = init;
65 for &value in src {
66 acc = reduce_fn(acc, map_fn(Op::apply(value)));
67 }
68 return acc;
69 }
70 let (head, rest) = src.split_at(FOLD_LANES);
71 let mut lanes: [U; FOLD_LANES] = core::array::from_fn(|lane| map_fn(Op::apply(head[lane])));
72 let mut chunks = rest.chunks_exact(FOLD_LANES);
73 for chunk in chunks.by_ref() {
74 for (lane, &value) in lanes.iter_mut().zip(chunk) {
75 *lane = reduce_fn(lane.clone(), map_fn(Op::apply(value)));
76 }
77 }
78 for (lane, &value) in lanes.iter_mut().zip(chunks.remainder()) {
79 *lane = reduce_fn(lane.clone(), map_fn(Op::apply(value)));
80 }
81 fold_lanes(lanes, init, reduce_fn)
82}
83
84#[inline(always)]
89unsafe fn fold_run<T, Op, M, R, U>(
90 ptr: *const T,
91 stride: isize,
92 len: usize,
93 init: U,
94 map_fn: &M,
95 reduce_fn: &R,
96) -> U
97where
98 T: Copy,
99 Op: ElementOp<T>,
100 M: Fn(T) -> U,
101 R: Fn(U, U) -> U,
102 U: Clone,
103{
104 if stride == 1 {
105 let run = unsafe { std::slice::from_raw_parts(ptr, len) };
107 return fold_contiguous::<T, Op, M, R, U>(run, init, map_fn, reduce_fn);
108 }
109 let mut acc = init;
110 let mut cursor = ptr;
111 for index in 0..len {
112 acc = reduce_fn(acc, map_fn(Op::apply(unsafe { *cursor })));
114 if index + 1 < len {
115 cursor = cursor.wrapping_offset(stride);
116 }
117 }
118 acc
119}
120
121pub fn reduce<T: Copy + Send + Sync, Op: ElementOp<T>, M, R, U>(
159 src: &StridedView<T, Op>,
160 map_fn: M,
161 reduce_fn: R,
162 init: U,
163 exec: Exec<'_>,
164) -> Result<U>
165where
166 M: Fn(T) -> U + Sync,
167 R: Fn(U, U) -> U + Sync,
168 U: Clone + Send + Sync,
169{
170 reduce_impl(src, map_fn, reduce_fn, init, exec)
171}
172
173fn reduce_impl<T: Copy + Send + Sync, Op: ElementOp<T>, M, R, U>(
174 src: &StridedView<T, Op>,
175 map_fn: M,
176 reduce_fn: R,
177 init: U,
178 exec: Exec<'_>,
179) -> Result<U>
180where
181 M: Fn(T) -> U + Sync,
182 R: Fn(U, U) -> U + Sync,
183 U: Clone + Send + Sync,
184{
185 let src_ptr = src.ptr();
186 let src_dims = src.dims();
187 let src_strides = src.strides();
188
189 if total_len(src_dims)? == 0 {
193 return Ok(init);
194 }
195
196 let contiguous =
197 sequential_contiguous_layout(KernelClass::Reduce, src_dims, &[src_strides], &exec)?;
198 if contiguous.is_some() {
199 let len = total_len(src_dims)?;
200 let src = unsafe { std::slice::from_raw_parts(src_ptr, len) };
201 return Ok(simd::dispatch_if_large(len, || {
202 fold_contiguous::<T, Op, M, R, U>(src, init, &map_fn, &reduce_fn)
203 }));
204 }
205
206 let total = total_len(src_dims)?;
210 if is_parallel(KernelClass::Reduce, total, &exec)
211 && same_contiguous_layout(src_dims, &[src_strides]).is_some()
212 {
213 let src_slice = unsafe { std::slice::from_raw_parts(src_ptr, total) };
214 let result = crate::threading::parallel_map_reduce(
215 0..total,
216 crate::cost::for_len_tree(exec, KernelClass::Reduce, total),
217 &|range| {
218 simd::dispatch_if_large(range.len(), || {
219 fold_contiguous::<T, Op, M, R, U>(
220 &src_slice[range],
221 init.clone(),
222 &map_fn,
223 &reduce_fn,
224 )
225 })
226 },
227 &|a, b| reduce_fn(a, b),
228 );
229 return Ok(result);
230 }
231
232 let strides_list: [&[isize]; 1] = [src_strides];
233
234 let (fused_dims, ordered_strides, plan) =
235 build_plan_fused(src_dims, &strides_list, None, std::mem::size_of::<T>());
236
237 let total = total_len(&fused_dims)?;
238 if is_parallel(KernelClass::Reduce, total, &exec) {
239 let src_send = SendPtr(src_ptr as *mut T);
240 let costs = compute_costs(&ordered_strides);
241 let initial_offsets: crate::inline::OperandVec<isize> =
242 ordered_strides.iter().map(|_| 0isize).collect();
243 let map_fn_ref = &map_fn;
244 let reduce_fn_ref = &reduce_fn;
245 let init_ref = &init;
246 let result = mapreduce_threaded_fold(
249 &fused_dims,
250 &plan.block,
251 &ordered_strides,
252 &initial_offsets,
253 &costs,
254 KernelClass::Reduce,
255 exec,
256 &|dims, blocks, strides_list, offsets| {
257 let mut acc = init_ref.clone();
258 for_each_inner_block_with_offsets(
259 dims,
260 blocks,
261 strides_list,
262 offsets,
263 |offsets, len, strides| {
264 let mut ptr = unsafe { src_send.as_const().offset(offsets[0]) };
265 let stride = strides[0];
266 for _ in 0..len {
267 let val = Op::apply(unsafe { *ptr });
268 let mapped = map_fn_ref(val);
269 acc = reduce_fn_ref(acc.clone(), mapped);
270 unsafe {
271 ptr = ptr.offset(stride);
272 }
273 }
274 Ok(())
275 },
276 )?;
277 Ok(acc)
278 },
279 &|a, b| reduce_fn_ref(a, b),
280 )?;
281 return Ok(result);
282 }
283
284 let mut acc = init;
285 let initial_offsets: crate::inline::OperandVec<isize> =
286 ordered_strides.iter().map(|_| 0isize).collect();
287 for_each_inner_block_preordered(
288 &fused_dims,
289 &plan.block,
290 &ordered_strides,
291 &initial_offsets,
292 |offsets, len, strides| {
293 let mut ptr = unsafe { src_ptr.offset(offsets[0]) };
294 let stride = strides[0];
295 for _ in 0..len {
296 let val = Op::apply(unsafe { *ptr });
297 let mapped = map_fn(val);
298 acc = reduce_fn(acc.clone(), mapped);
299 unsafe {
300 ptr = ptr.offset(stride);
301 }
302 }
303 Ok(())
304 },
305 )?;
306
307 Ok(acc)
308}
309
310#[inline(always)]
326fn fold_contiguous2<A, B, OpA, OpB, M, R, U>(
327 a: &[A],
328 b: &[B],
329 init: U,
330 map_fn: &M,
331 reduce_fn: &R,
332) -> U
333where
334 A: Copy,
335 B: Copy,
336 OpA: ElementOp<A>,
337 OpB: ElementOp<B>,
338 M: Fn(A, B) -> U,
339 R: Fn(U, U) -> U,
340 U: Clone,
341{
342 debug_assert_eq!(a.len(), b.len());
343 if a.len() < 2 * FOLD_LANES {
344 let mut acc = init;
345 for (&value_a, &value_b) in a.iter().zip(b) {
346 acc = reduce_fn(acc, map_fn(OpA::apply(value_a), OpB::apply(value_b)));
347 }
348 return acc;
349 }
350 let (head_a, rest_a) = a.split_at(FOLD_LANES);
351 let (head_b, rest_b) = b.split_at(FOLD_LANES);
352 let mut lanes: [U; FOLD_LANES] =
353 core::array::from_fn(|lane| map_fn(OpA::apply(head_a[lane]), OpB::apply(head_b[lane])));
354 let mut chunks_a = rest_a.chunks_exact(FOLD_LANES);
355 let mut chunks_b = rest_b.chunks_exact(FOLD_LANES);
356 for (chunk_a, chunk_b) in chunks_a.by_ref().zip(chunks_b.by_ref()) {
357 for ((lane, &value_a), &value_b) in lanes.iter_mut().zip(chunk_a).zip(chunk_b) {
358 *lane = reduce_fn(
359 lane.clone(),
360 map_fn(OpA::apply(value_a), OpB::apply(value_b)),
361 );
362 }
363 }
364 for ((lane, &value_a), &value_b) in lanes
365 .iter_mut()
366 .zip(chunks_a.remainder())
367 .zip(chunks_b.remainder())
368 {
369 *lane = reduce_fn(
370 lane.clone(),
371 map_fn(OpA::apply(value_a), OpB::apply(value_b)),
372 );
373 }
374 lanes.into_iter().fold(init, reduce_fn)
375}
376
377#[inline(always)]
384#[allow(clippy::too_many_arguments)]
385unsafe fn fold_run2<A, B, OpA, OpB, M, R, U>(
386 a_ptr: *const A,
387 a_stride: isize,
388 b_ptr: *const B,
389 b_stride: isize,
390 len: usize,
391 init: &U,
392 map_fn: &M,
393 reduce_fn: &R,
394) -> U
395where
396 A: Copy,
397 B: Copy,
398 OpA: ElementOp<A>,
399 OpB: ElementOp<B>,
400 M: Fn(A, B) -> U,
401 R: Fn(U, U) -> U,
402 U: Clone,
403{
404 if a_stride == 1 && b_stride == 1 {
405 let a = unsafe { std::slice::from_raw_parts(a_ptr, len) };
408 let b = unsafe { std::slice::from_raw_parts(b_ptr, len) };
409 return fold_contiguous2::<A, B, OpA, OpB, M, R, U>(a, b, init.clone(), map_fn, reduce_fn);
410 }
411 let mut acc = init.clone();
412 let mut cursor_a = a_ptr;
413 let mut cursor_b = b_ptr;
414 for index in 0..len {
415 let mapped = map_fn(
417 OpA::apply(unsafe { *cursor_a }),
418 OpB::apply(unsafe { *cursor_b }),
419 );
420 acc = reduce_fn(acc, mapped);
421 if index + 1 < len {
422 cursor_a = cursor_a.wrapping_offset(a_stride);
423 cursor_b = cursor_b.wrapping_offset(b_stride);
424 }
425 }
426 acc
427}
428
429pub fn zip_reduce<A, B, OpA, OpB, M, R, U>(
491 a: &StridedView<A, OpA>,
492 b: &StridedView<B, OpB>,
493 map_fn: M,
494 reduce_fn: R,
495 init: U,
496 exec: Exec<'_>,
497) -> Result<U>
498where
499 A: Copy + Send + Sync,
500 B: Copy + Send + Sync,
501 OpA: ElementOp<A>,
502 OpB: ElementOp<B>,
503 M: Fn(A, B) -> U + Sync,
504 R: Fn(U, U) -> U + Sync,
505 U: Clone + Send + Sync,
506{
507 ensure_same_shape(a.dims(), b.dims())?;
508
509 let a_ptr = a.ptr();
510 let b_ptr = b.ptr();
511 let dims = a.dims();
512 let a_strides = a.strides();
513 let b_strides = b.strides();
514
515 let total = total_len(dims)?;
519 if total == 0 {
520 return Ok(init);
521 }
522
523 if sequential_contiguous_layout(KernelClass::Reduce, dims, &[a_strides, b_strides], &exec)?
524 .is_some()
525 {
526 return Ok(simd::dispatch_if_large(total, || {
527 let sa = unsafe { std::slice::from_raw_parts(a_ptr, total) };
529 let sb = unsafe { std::slice::from_raw_parts(b_ptr, total) };
530 fold_contiguous2::<A, B, OpA, OpB, M, R, U>(sa, sb, init, &map_fn, &reduce_fn)
531 }));
532 }
533
534 if is_parallel(KernelClass::Reduce, total, &exec)
537 && same_contiguous_layout(dims, &[a_strides, b_strides]).is_some()
538 {
539 let sa = unsafe { std::slice::from_raw_parts(a_ptr, total) };
541 let sb = unsafe { std::slice::from_raw_parts(b_ptr, total) };
542 let result = crate::threading::parallel_map_reduce(
543 0..total,
544 crate::cost::for_len_tree(exec, KernelClass::Reduce, total),
545 &|range| {
546 let len = range.len();
547 simd::dispatch_if_large(len, || {
548 fold_contiguous2::<A, B, OpA, OpB, M, R, U>(
549 &sa[range.clone()],
550 &sb[range],
551 init.clone(),
552 &map_fn,
553 &reduce_fn,
554 )
555 })
556 },
557 &|left, right| reduce_fn(left, right),
558 );
559 return Ok(result);
560 }
561
562 let strides_list: [&[isize]; 2] = [a_strides, b_strides];
563 let elem_size = std::mem::size_of::<A>().max(std::mem::size_of::<B>());
564 let (fused_dims, ordered_strides, plan) =
565 build_plan_fused(dims, &strides_list, None, elem_size);
566
567 let total = total_len(&fused_dims)?;
568 if is_parallel(KernelClass::Reduce, total, &exec) {
569 let a_send = SendPtr(a_ptr as *mut A);
570 let b_send = SendPtr(b_ptr as *mut B);
571 let costs = compute_costs(&ordered_strides);
572 let initial_offsets: crate::inline::OperandVec<isize> =
573 ordered_strides.iter().map(|_| 0isize).collect();
574 let map_fn_ref = &map_fn;
575 let reduce_fn_ref = &reduce_fn;
576 let init_ref = &init;
577 let result = mapreduce_threaded_fold(
580 &fused_dims,
581 &plan.block,
582 &ordered_strides,
583 &initial_offsets,
584 &costs,
585 KernelClass::Reduce,
586 exec,
587 &|dims, blocks, strides_list, offsets| {
588 let mut acc = init_ref.clone();
589 for_each_inner_block_with_offsets(
590 dims,
591 blocks,
592 strides_list,
593 offsets,
594 |offsets, len, strides| {
595 acc = unsafe {
598 fold_run2::<A, B, OpA, OpB, M, R, U>(
599 a_send.as_const().offset(offsets[0]),
600 strides[0],
601 b_send.as_const().offset(offsets[1]),
602 strides[1],
603 len,
604 &acc,
605 map_fn_ref,
606 reduce_fn_ref,
607 )
608 };
609 Ok(())
610 },
611 )?;
612 Ok(acc)
613 },
614 &|left, right| reduce_fn_ref(left, right),
615 )?;
616 return Ok(result);
617 }
618
619 let mut acc = init;
620 let initial_offsets: crate::inline::OperandVec<isize> =
621 ordered_strides.iter().map(|_| 0isize).collect();
622 for_each_inner_block_preordered(
623 &fused_dims,
624 &plan.block,
625 &ordered_strides,
626 &initial_offsets,
627 |offsets, len, strides| {
628 acc = unsafe {
631 fold_run2::<A, B, OpA, OpB, M, R, U>(
632 a_ptr.offset(offsets[0]),
633 strides[0],
634 b_ptr.offset(offsets[1]),
635 strides[1],
636 len,
637 &acc,
638 &map_fn,
639 &reduce_fn,
640 )
641 };
642 Ok(())
643 },
644 )?;
645
646 Ok(acc)
647}
648
649pub fn reduce_axis<T: Copy + Send + Sync, Op: ElementOp<T>, M, R, U>(
678 src: &StridedView<T, Op>,
679 axis: usize,
680 map_fn: M,
681 reduce_fn: R,
682 init: U,
683 exec: Exec<'_>,
684) -> Result<StridedArray<U>>
685where
686 M: Fn(T) -> U + Sync,
687 R: Fn(U, U) -> U + Sync,
688 U: Clone + Send + Sync,
689{
690 let rank = src.ndim();
691 if axis >= rank {
692 return Err(StridedError::InvalidAxis { axis, rank });
693 }
694 total_len(src.dims())?;
696 let out_dims: InlineVec<usize> = src
697 .dims()
698 .iter()
699 .enumerate()
700 .filter(|(i, _)| *i != axis)
701 .map(|(_, &d)| d)
702 .collect();
703 let (out_dims, out_strides) = if out_dims.is_empty() {
706 let mut dims = InlineVec::new();
707 dims.push(1usize);
708 let strides = col_major_strides(&dims);
709 (dims, strides)
710 } else {
711 let strides = col_major_strides(&out_dims);
712 (out_dims, strides)
713 };
714 let total_out = total_len(&out_dims)?;
715 let mut out =
716 StridedArray::<U>::from_parts(vec![init.clone(); total_out], &out_dims, &out_strides, 0)?;
717 {
718 let mut dest = out.view_mut();
719 reduce_axis_into_impl(&mut dest, src, axis, map_fn, reduce_fn, init, exec)?;
721 }
722 Ok(out)
723}
724
725pub fn reduce_axis_into<T: Copy + Send + Sync, Op: ElementOp<T>, M, R, U>(
754 dest: &mut StridedViewMut<U>,
755 src: &StridedView<T, Op>,
756 axis: usize,
757 map_fn: M,
758 reduce_fn: R,
759 init: U,
760 exec: Exec<'_>,
761) -> Result<()>
762where
763 M: Fn(T) -> U + Sync,
764 R: Fn(U, U) -> U + Sync,
765 U: Clone + Send + Sync,
766{
767 let rank = src.ndim();
768 if axis >= rank {
769 return Err(StridedError::InvalidAxis { axis, rank });
770 }
771 let src_dims = src.dims();
772 total_len(src_dims)?;
775 let kept_len = rank - 1;
776 let dest_len = total_len(dest.dims())?;
777 if kept_len == 0 {
778 if dest_len != 1 {
779 return Err(StridedError::ShapeMismatch(vec![dest_len], vec![1]));
780 }
781 } else {
782 if dest.ndim() != kept_len {
783 return Err(StridedError::RankMismatch(dest.ndim(), kept_len));
784 }
785 let dest_dims = dest.dims();
786 let mut d = 0usize;
787 for (i, &src_dim) in src_dims.iter().enumerate() {
788 if i == axis {
789 continue;
790 }
791 if src_dim != dest_dims[d] {
792 let expected: Vec<usize> = src_dims
793 .iter()
794 .enumerate()
795 .filter(|(i, _)| *i != axis)
796 .map(|(_, &d)| d)
797 .collect();
798 return Err(StridedError::ShapeMismatch(dest_dims.to_vec(), expected));
799 }
800 d += 1;
801 }
802 if !crate::layout_check::is_injective_layout(dest.dims(), dest.strides()) {
803 return Err(StridedError::NonInjectiveOutputLayout);
804 }
805 }
806 reduce_axis_into_impl(dest, src, axis, map_fn, reduce_fn, init, exec)
807}
808
809fn reduce_axis_into_impl<T: Copy + Send + Sync, Op: ElementOp<T>, M, R, U>(
816 dest: &mut StridedViewMut<U>,
817 src: &StridedView<T, Op>,
818 axis: usize,
819 map_fn: M,
820 reduce_fn: R,
821 init: U,
822 exec: Exec<'_>,
823) -> Result<()>
824where
825 M: Fn(T) -> U + Sync,
826 R: Fn(U, U) -> U + Sync,
827 U: Clone + Send + Sync,
828{
829 let rank = src.ndim();
830 let src_dims = src.dims();
831 let src_strides = src.strides();
832 let src_ptr = src.ptr();
833 let dest_len = total_len(dest.dims())?;
834 let axis_len = src_dims[axis];
835 let axis_stride = src_strides[axis];
836
837 if axis_len == 0 {
838 fill_outputs_with(dest, &init);
843 return Ok(());
844 }
845
846 if rank == 1 {
847 let acc = unsafe {
850 fold_run::<T, Op, M, R, U>(src_ptr, axis_stride, axis_len, init, &map_fn, &reduce_fn)
851 };
852 unsafe { *dest.as_mut_ptr() = acc };
853 return Ok(());
854 }
855 if dest_len == 0 {
856 return Ok(());
857 }
858
859 let dest_stride_view = dest.strides();
864 let mut kept: InlineVec<(usize, isize)> = InlineVec::new();
865 let mut dest_linear = true;
866 let mut prefix = 1usize;
867 for (i, (&dim, &src_stride)) in src_dims.iter().zip(src_strides).enumerate() {
868 if i == axis {
869 continue;
870 }
871 let d = kept.len();
872 kept.push((dim, src_stride));
873 if dest_linear && dest_stride_view[d] != prefix as isize {
874 dest_linear = false;
875 }
876 prefix = prefix.saturating_mul(dim);
877 }
878 let dest_strides: InlineVec<isize> = if dest_linear {
879 InlineVec::new()
880 } else {
881 dest_stride_view.iter().copied().collect()
882 };
883 let out_ptr = dest.as_mut_ptr();
884 let parts = AxisParts {
885 kept: &kept,
886 dest_strides: &dest_strides,
887 axis_len,
888 axis_stride,
889 map_fn: &map_fn,
890 reduce_fn: &reduce_fn,
891 init: &init,
892 };
893
894 let work = dest_len.saturating_mul(axis_len);
895 let exec = crate::cost::for_len(exec, KernelClass::Reduce, work)
896 .limit(NonZeroUsize::new(dest_len).unwrap_or(NonZeroUsize::MIN));
897 if !exec.is_serial() {
898 let src_send = SendPtr(src_ptr as *mut T);
899 let out_send = SendPtr(out_ptr);
900 let parts = &parts;
901 if dest_linear {
902 crate::threading::parallel_for_each(0..dest_len, exec, &|range| {
903 unsafe {
907 reduce_axis_range_linear::<T, Op, M, R, U>(
908 src_send.as_const(),
909 out_send.as_ptr(),
910 range,
911 parts,
912 )
913 }
914 });
915 } else {
916 crate::threading::parallel_for_each(0..dest_len, exec, &|range| {
917 unsafe {
919 reduce_axis_range_strided::<T, Op, M, R, U>(
920 src_send.as_const(),
921 out_send.as_ptr(),
922 range,
923 parts,
924 )
925 }
926 });
927 }
928 return Ok(());
929 }
930
931 if dest_linear {
933 unsafe {
934 reduce_axis_range_linear::<T, Op, M, R, U>(src_ptr, out_ptr, 0..dest_len, &parts)
935 };
936 } else {
937 unsafe {
938 reduce_axis_range_strided::<T, Op, M, R, U>(src_ptr, out_ptr, 0..dest_len, &parts)
939 };
940 }
941 Ok(())
942}
943
944fn fill_outputs_with<U: Clone>(dest: &mut StridedViewMut<U>, value: &U) {
951 let dims = dest.dims();
952 if dims.iter().any(|&dim| dim == 0) {
953 return;
954 }
955 let strides = dest.strides();
956 let rank = dims.len();
957 let total: usize = dims.iter().product();
958 let base = dest.as_mut_ptr();
959 if rank == 0 {
960 unsafe { *base = value.clone() };
962 return;
963 }
964 let mut coords_inline = [0usize; strided_view::INLINE_RANK];
965 let mut coords_heap: Vec<usize> = Vec::new();
966 let coords: &mut [usize] = if rank <= strided_view::INLINE_RANK {
967 &mut coords_inline[..rank]
968 } else {
969 coords_heap.resize(rank, 0);
970 &mut coords_heap[..]
971 };
972 let mut offset = 0isize;
973 for _ in 0..total {
974 unsafe { *base.offset(offset) = value.clone() };
978 for axis in 0..rank {
979 coords[axis] += 1;
980 offset += strides[axis];
981 if coords[axis] < dims[axis] {
982 break;
983 }
984 coords[axis] = 0;
985 offset -= dims[axis] as isize * strides[axis];
986 }
987 }
988}
989
990struct AxisParts<'a, M, R, U> {
993 kept: &'a [(usize, isize)],
995 dest_strides: &'a [isize],
997 axis_len: usize,
998 axis_stride: isize,
999 map_fn: &'a M,
1000 reduce_fn: &'a R,
1001 init: &'a U,
1002}
1003
1004#[inline(never)]
1017unsafe fn reduce_axis_range_linear<T, Op, M, R, U>(
1018 src: *const T,
1019 out: *mut U,
1020 range: Range<usize>,
1021 parts: &AxisParts<'_, M, R, U>,
1022) where
1023 T: Copy,
1024 Op: ElementOp<T>,
1025 M: Fn(T) -> U,
1026 R: Fn(U, U) -> U,
1027 U: Clone,
1028{
1029 let kept = parts.kept;
1030 let (lead_extent, lead_stride) = kept[0];
1031 let sweep = lead_stride == 1 && lead_extent >= AXIS_SWEEP_MIN_LEN && parts.axis_len > 1;
1032 let block = (AXIS_SWEEP_BLOCK_BYTES / std::mem::size_of::<U>().max(1)).max(AXIS_SWEEP_MIN_LEN);
1033
1034 let coords_len = kept.len();
1039 let mut coords_inline = [0usize; strided_view::INLINE_RANK];
1040 let mut coords_heap: Vec<usize> = Vec::new();
1041 let coords: &mut [usize] = if coords_len <= strided_view::INLINE_RANK {
1042 &mut coords_inline[..coords_len]
1043 } else {
1044 coords_heap.resize(coords_len, 0);
1045 &mut coords_heap[..]
1046 };
1047 let mut rest = range.start;
1048 let mut src_off = 0isize;
1049 for (coord, &(extent, stride)) in coords.iter_mut().zip(kept) {
1050 *coord = rest % extent;
1051 rest /= extent;
1052 src_off += *coord as isize * stride;
1053 }
1054
1055 let mut output = range.start;
1056 while output < range.end {
1057 let len = if sweep {
1058 (lead_extent - coords[0]).min(range.end - output).min(block)
1059 } else {
1060 1
1061 };
1062 if sweep {
1063 unsafe { sweep_block::<T, Op, M, R, U>(src, src_off, out.add(output), len, parts) };
1067 } else {
1068 unsafe {
1070 let acc = fold_run::<T, Op, M, R, U>(
1071 src.offset(src_off),
1072 parts.axis_stride,
1073 parts.axis_len,
1074 parts.init.clone(),
1075 parts.map_fn,
1076 parts.reduce_fn,
1077 );
1078 *out.add(output) = acc;
1079 }
1080 }
1081 output += len;
1082 if output >= range.end {
1083 break;
1084 }
1085 coords[0] += len;
1088 src_off += len as isize * lead_stride;
1089 let mut axis = 0;
1090 while coords[axis] == kept[axis].0 {
1091 src_off -= kept[axis].0 as isize * kept[axis].1;
1092 coords[axis] = 0;
1093 axis += 1;
1094 coords[axis] += 1;
1095 src_off += kept[axis].1;
1096 }
1097 }
1098}
1099
1100#[inline(never)]
1110unsafe fn reduce_axis_range_strided<T, Op, M, R, U>(
1111 src: *const T,
1112 out: *mut U,
1113 range: Range<usize>,
1114 parts: &AxisParts<'_, M, R, U>,
1115) where
1116 T: Copy,
1117 Op: ElementOp<T>,
1118 M: Fn(T) -> U,
1119 R: Fn(U, U) -> U,
1120 U: Clone,
1121{
1122 let kept = parts.kept;
1123 let dest_strides = parts.dest_strides;
1124 let (lead_extent, lead_stride) = kept[0];
1125 let lead_dest_stride = dest_strides[0];
1126 let sweep = lead_stride == 1
1127 && lead_dest_stride == 1
1128 && lead_extent >= AXIS_SWEEP_MIN_LEN
1129 && parts.axis_len > 1;
1130 let block = (AXIS_SWEEP_BLOCK_BYTES / std::mem::size_of::<U>().max(1)).max(AXIS_SWEEP_MIN_LEN);
1131
1132 let coords_len = kept.len();
1136 let mut coords_inline = [0usize; strided_view::INLINE_RANK];
1137 let mut coords_heap: Vec<usize> = Vec::new();
1138 let coords: &mut [usize] = if coords_len <= strided_view::INLINE_RANK {
1139 &mut coords_inline[..coords_len]
1140 } else {
1141 coords_heap.resize(coords_len, 0);
1142 &mut coords_heap[..]
1143 };
1144 let mut rest = range.start;
1145 let mut src_off = 0isize;
1146 let mut dest_off = 0isize;
1147 for (coord, (&(extent, stride), &dest_stride)) in
1148 coords.iter_mut().zip(kept.iter().zip(dest_strides))
1149 {
1150 *coord = rest % extent;
1151 rest /= extent;
1152 src_off += *coord as isize * stride;
1153 dest_off += *coord as isize * dest_stride;
1154 }
1155
1156 let mut output = range.start;
1157 while output < range.end {
1158 let len = if sweep {
1159 (lead_extent - coords[0]).min(range.end - output).min(block)
1160 } else {
1161 1
1162 };
1163 if sweep {
1164 unsafe {
1167 sweep_block::<T, Op, M, R, U>(src, src_off, out.offset(dest_off), len, parts)
1168 };
1169 } else {
1170 unsafe {
1172 let acc = fold_run::<T, Op, M, R, U>(
1173 src.offset(src_off),
1174 parts.axis_stride,
1175 parts.axis_len,
1176 parts.init.clone(),
1177 parts.map_fn,
1178 parts.reduce_fn,
1179 );
1180 *out.offset(dest_off) = acc;
1181 }
1182 }
1183 output += len;
1184 if output >= range.end {
1185 break;
1186 }
1187 coords[0] += len;
1188 src_off += len as isize * lead_stride;
1189 dest_off += len as isize * lead_dest_stride;
1190 let mut axis = 0;
1191 while coords[axis] == kept[axis].0 {
1192 src_off -= kept[axis].0 as isize * kept[axis].1;
1193 dest_off -= kept[axis].0 as isize * dest_strides[axis];
1194 coords[axis] = 0;
1195 axis += 1;
1196 coords[axis] += 1;
1197 src_off += kept[axis].1;
1198 dest_off += dest_strides[axis];
1199 }
1200 }
1201}
1202
1203#[inline(always)]
1211unsafe fn sweep_block<T, Op, M, R, U>(
1212 src: *const T,
1213 src_off: isize,
1214 out: *mut U,
1215 len: usize,
1216 parts: &AxisParts<'_, M, R, U>,
1217) where
1218 T: Copy,
1219 Op: ElementOp<T>,
1220 M: Fn(T) -> U,
1221 R: Fn(U, U) -> U,
1222 U: Clone,
1223{
1224 let map_fn = parts.map_fn;
1225 let reduce_fn = parts.reduce_fn;
1226 let out = unsafe { std::slice::from_raw_parts_mut(out, len) };
1228 let column = |k: usize| {
1229 unsafe {
1231 std::slice::from_raw_parts(src.offset(src_off + k as isize * parts.axis_stride), len)
1232 }
1233 };
1234 let first = column(0);
1235 for (slot, &value) in out.iter_mut().zip(first) {
1236 *slot = reduce_fn(parts.init.clone(), map_fn(Op::apply(value)));
1237 }
1238 let mut k = 1;
1239 while k + 4 <= parts.axis_len {
1240 let (c0, c1, c2, c3) = (column(k), column(k + 1), column(k + 2), column(k + 3));
1241 for (index, slot) in out.iter_mut().enumerate() {
1242 let mut acc = reduce_fn(slot.clone(), map_fn(Op::apply(c0[index])));
1243 acc = reduce_fn(acc, map_fn(Op::apply(c1[index])));
1244 acc = reduce_fn(acc, map_fn(Op::apply(c2[index])));
1245 acc = reduce_fn(acc, map_fn(Op::apply(c3[index])));
1246 *slot = acc;
1247 }
1248 k += 4;
1249 }
1250 while k < parts.axis_len {
1251 let values = column(k);
1252 for (slot, &value) in out.iter_mut().zip(values) {
1253 *slot = reduce_fn(slot.clone(), map_fn(Op::apply(value)));
1254 }
1255 k += 1;
1256 }
1257}