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 (chunks, remainder) = rest.as_chunks::<FOLD_LANES>();
73 for chunk in chunks {
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(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 (chunks_a, remainder_a) = rest_a.as_chunks::<FOLD_LANES>();
355 let (chunks_b, remainder_b) = rest_b.as_chunks::<FOLD_LANES>();
356 for (chunk_a, chunk_b) in chunks_a.iter().zip(chunks_b) {
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.iter_mut().zip(remainder_a).zip(remainder_b) {
365 *lane = reduce_fn(
366 lane.clone(),
367 map_fn(OpA::apply(value_a), OpB::apply(value_b)),
368 );
369 }
370 lanes.into_iter().fold(init, reduce_fn)
371}
372
373#[inline(always)]
380#[allow(clippy::too_many_arguments)]
383unsafe fn fold_run2<A, B, OpA, OpB, M, R, U>(
384 a_ptr: *const A,
385 a_stride: isize,
386 b_ptr: *const B,
387 b_stride: isize,
388 len: usize,
389 init: &U,
390 map_fn: &M,
391 reduce_fn: &R,
392) -> U
393where
394 A: Copy,
395 B: Copy,
396 OpA: ElementOp<A>,
397 OpB: ElementOp<B>,
398 M: Fn(A, B) -> U,
399 R: Fn(U, U) -> U,
400 U: Clone,
401{
402 if a_stride == 1 && b_stride == 1 {
403 let a = unsafe { std::slice::from_raw_parts(a_ptr, len) };
406 let b = unsafe { std::slice::from_raw_parts(b_ptr, len) };
407 return fold_contiguous2::<A, B, OpA, OpB, M, R, U>(a, b, init.clone(), map_fn, reduce_fn);
408 }
409 let mut acc = init.clone();
410 let mut cursor_a = a_ptr;
411 let mut cursor_b = b_ptr;
412 for index in 0..len {
413 let mapped = map_fn(
415 OpA::apply(unsafe { *cursor_a }),
416 OpB::apply(unsafe { *cursor_b }),
417 );
418 acc = reduce_fn(acc, mapped);
419 if index + 1 < len {
420 cursor_a = cursor_a.wrapping_offset(a_stride);
421 cursor_b = cursor_b.wrapping_offset(b_stride);
422 }
423 }
424 acc
425}
426
427pub fn zip_reduce<A, B, OpA, OpB, M, R, U>(
489 a: &StridedView<A, OpA>,
490 b: &StridedView<B, OpB>,
491 map_fn: M,
492 reduce_fn: R,
493 init: U,
494 exec: Exec<'_>,
495) -> Result<U>
496where
497 A: Copy + Send + Sync,
498 B: Copy + Send + Sync,
499 OpA: ElementOp<A>,
500 OpB: ElementOp<B>,
501 M: Fn(A, B) -> U + Sync,
502 R: Fn(U, U) -> U + Sync,
503 U: Clone + Send + Sync,
504{
505 ensure_same_shape(a.dims(), b.dims())?;
506
507 let a_ptr = a.ptr();
508 let b_ptr = b.ptr();
509 let dims = a.dims();
510 let a_strides = a.strides();
511 let b_strides = b.strides();
512
513 let total = total_len(dims)?;
517 if total == 0 {
518 return Ok(init);
519 }
520
521 if sequential_contiguous_layout(KernelClass::Reduce, dims, &[a_strides, b_strides], &exec)?
522 .is_some()
523 {
524 return Ok(simd::dispatch_if_large(total, || {
525 let sa = unsafe { std::slice::from_raw_parts(a_ptr, total) };
527 let sb = unsafe { std::slice::from_raw_parts(b_ptr, total) };
528 fold_contiguous2::<A, B, OpA, OpB, M, R, U>(sa, sb, init, &map_fn, &reduce_fn)
529 }));
530 }
531
532 if is_parallel(KernelClass::Reduce, total, &exec)
535 && same_contiguous_layout(dims, &[a_strides, b_strides]).is_some()
536 {
537 let sa = unsafe { std::slice::from_raw_parts(a_ptr, total) };
539 let sb = unsafe { std::slice::from_raw_parts(b_ptr, total) };
540 let result = crate::threading::parallel_map_reduce(
541 0..total,
542 crate::cost::for_len_tree(exec, KernelClass::Reduce, total),
543 &|range| {
544 let len = range.len();
545 simd::dispatch_if_large(len, || {
546 fold_contiguous2::<A, B, OpA, OpB, M, R, U>(
547 &sa[range.clone()],
548 &sb[range],
549 init.clone(),
550 &map_fn,
551 &reduce_fn,
552 )
553 })
554 },
555 &|left, right| reduce_fn(left, right),
556 );
557 return Ok(result);
558 }
559
560 let strides_list: [&[isize]; 2] = [a_strides, b_strides];
561 let elem_size = std::mem::size_of::<A>().max(std::mem::size_of::<B>());
562 let (fused_dims, ordered_strides, plan) =
563 build_plan_fused(dims, &strides_list, None, elem_size);
564
565 let total = total_len(&fused_dims)?;
566 if is_parallel(KernelClass::Reduce, total, &exec) {
567 let a_send = SendPtr(a_ptr as *mut A);
568 let b_send = SendPtr(b_ptr as *mut B);
569 let costs = compute_costs(&ordered_strides);
570 let initial_offsets: crate::inline::OperandVec<isize> =
571 ordered_strides.iter().map(|_| 0isize).collect();
572 let map_fn_ref = &map_fn;
573 let reduce_fn_ref = &reduce_fn;
574 let init_ref = &init;
575 let result = mapreduce_threaded_fold(
578 &fused_dims,
579 &plan.block,
580 &ordered_strides,
581 &initial_offsets,
582 &costs,
583 KernelClass::Reduce,
584 exec,
585 &|dims, blocks, strides_list, offsets| {
586 let mut acc = init_ref.clone();
587 for_each_inner_block_with_offsets(
588 dims,
589 blocks,
590 strides_list,
591 offsets,
592 |offsets, len, strides| {
593 acc = unsafe {
596 fold_run2::<A, B, OpA, OpB, M, R, U>(
597 a_send.as_const().offset(offsets[0]),
598 strides[0],
599 b_send.as_const().offset(offsets[1]),
600 strides[1],
601 len,
602 &acc,
603 map_fn_ref,
604 reduce_fn_ref,
605 )
606 };
607 Ok(())
608 },
609 )?;
610 Ok(acc)
611 },
612 &|left, right| reduce_fn_ref(left, right),
613 )?;
614 return Ok(result);
615 }
616
617 let mut acc = init;
618 let initial_offsets: crate::inline::OperandVec<isize> =
619 ordered_strides.iter().map(|_| 0isize).collect();
620 for_each_inner_block_preordered(
621 &fused_dims,
622 &plan.block,
623 &ordered_strides,
624 &initial_offsets,
625 |offsets, len, strides| {
626 acc = unsafe {
629 fold_run2::<A, B, OpA, OpB, M, R, U>(
630 a_ptr.offset(offsets[0]),
631 strides[0],
632 b_ptr.offset(offsets[1]),
633 strides[1],
634 len,
635 &acc,
636 &map_fn,
637 &reduce_fn,
638 )
639 };
640 Ok(())
641 },
642 )?;
643
644 Ok(acc)
645}
646
647pub fn reduce_axis<T: Copy + Send + Sync, Op: ElementOp<T>, M, R, U>(
676 src: &StridedView<T, Op>,
677 axis: usize,
678 map_fn: M,
679 reduce_fn: R,
680 init: U,
681 exec: Exec<'_>,
682) -> Result<StridedArray<U>>
683where
684 M: Fn(T) -> U + Sync,
685 R: Fn(U, U) -> U + Sync,
686 U: Clone + Send + Sync,
687{
688 let rank = src.ndim();
689 if axis >= rank {
690 return Err(StridedError::InvalidAxis { axis, rank });
691 }
692 total_len(src.dims())?;
694 let out_dims: InlineVec<usize> = src
695 .dims()
696 .iter()
697 .enumerate()
698 .filter(|(i, _)| *i != axis)
699 .map(|(_, &d)| d)
700 .collect();
701 let (out_dims, out_strides) = if out_dims.is_empty() {
704 let mut dims = InlineVec::new();
705 dims.push(1usize);
706 let strides = col_major_strides(&dims);
707 (dims, strides)
708 } else {
709 let strides = col_major_strides(&out_dims);
710 (out_dims, strides)
711 };
712 let total_out = total_len(&out_dims)?;
713 let mut out =
714 StridedArray::<U>::from_parts(vec![init.clone(); total_out], &out_dims, &out_strides, 0)?;
715 {
716 let mut dest = out.view_mut();
717 reduce_axis_into_impl(&mut dest, src, axis, map_fn, reduce_fn, init, exec)?;
719 }
720 Ok(out)
721}
722
723pub fn reduce_axis_into<T: Copy + Send + Sync, Op: ElementOp<T>, M, R, U>(
752 dest: &mut StridedViewMut<U>,
753 src: &StridedView<T, Op>,
754 axis: usize,
755 map_fn: M,
756 reduce_fn: R,
757 init: U,
758 exec: Exec<'_>,
759) -> Result<()>
760where
761 M: Fn(T) -> U + Sync,
762 R: Fn(U, U) -> U + Sync,
763 U: Clone + Send + Sync,
764{
765 let rank = src.ndim();
766 if axis >= rank {
767 return Err(StridedError::InvalidAxis { axis, rank });
768 }
769 let src_dims = src.dims();
770 total_len(src_dims)?;
773 let kept_len = rank - 1;
774 let dest_len = total_len(dest.dims())?;
775 if kept_len == 0 {
776 if dest_len != 1 {
777 return Err(StridedError::ShapeMismatch(vec![dest_len], vec![1]));
778 }
779 } else {
780 if dest.ndim() != kept_len {
781 return Err(StridedError::RankMismatch(dest.ndim(), kept_len));
782 }
783 let dest_dims = dest.dims();
784 let mut d = 0usize;
785 for (i, &src_dim) in src_dims.iter().enumerate() {
786 if i == axis {
787 continue;
788 }
789 if src_dim != dest_dims[d] {
790 let expected: Vec<usize> = src_dims
791 .iter()
792 .enumerate()
793 .filter(|(i, _)| *i != axis)
794 .map(|(_, &d)| d)
795 .collect();
796 return Err(StridedError::ShapeMismatch(dest_dims.to_vec(), expected));
797 }
798 d += 1;
799 }
800 if !crate::layout_check::is_injective_layout(dest.dims(), dest.strides()) {
801 return Err(StridedError::NonInjectiveOutputLayout);
802 }
803 }
804 reduce_axis_into_impl(dest, src, axis, map_fn, reduce_fn, init, exec)
805}
806
807fn reduce_axis_into_impl<T: Copy + Send + Sync, Op: ElementOp<T>, M, R, U>(
814 dest: &mut StridedViewMut<U>,
815 src: &StridedView<T, Op>,
816 axis: usize,
817 map_fn: M,
818 reduce_fn: R,
819 init: U,
820 exec: Exec<'_>,
821) -> Result<()>
822where
823 M: Fn(T) -> U + Sync,
824 R: Fn(U, U) -> U + Sync,
825 U: Clone + Send + Sync,
826{
827 let rank = src.ndim();
828 let src_dims = src.dims();
829 let src_strides = src.strides();
830 let src_ptr = src.ptr();
831 let dest_len = total_len(dest.dims())?;
832 let axis_len = src_dims[axis];
833 let axis_stride = src_strides[axis];
834
835 if axis_len == 0 {
836 fill_outputs_with(dest, &init);
841 return Ok(());
842 }
843
844 if rank == 1 {
845 let acc = unsafe {
848 fold_run::<T, Op, M, R, U>(src_ptr, axis_stride, axis_len, init, &map_fn, &reduce_fn)
849 };
850 unsafe { *dest.as_mut_ptr() = acc };
851 return Ok(());
852 }
853 if dest_len == 0 {
854 return Ok(());
855 }
856
857 let dest_stride_view = dest.strides();
862 let mut kept: InlineVec<(usize, isize)> = InlineVec::new();
863 let mut dest_linear = true;
864 let mut prefix = 1usize;
865 for (i, (&dim, &src_stride)) in src_dims.iter().zip(src_strides).enumerate() {
866 if i == axis {
867 continue;
868 }
869 let d = kept.len();
870 kept.push((dim, src_stride));
871 if dest_linear && dest_stride_view[d] != prefix as isize {
872 dest_linear = false;
873 }
874 prefix = prefix.saturating_mul(dim);
875 }
876 let dest_strides: InlineVec<isize> = if dest_linear {
877 InlineVec::new()
878 } else {
879 dest_stride_view.iter().copied().collect()
880 };
881 let out_ptr = dest.as_mut_ptr();
882 let parts = AxisParts {
883 kept: &kept,
884 dest_strides: &dest_strides,
885 axis_len,
886 axis_stride,
887 map_fn: &map_fn,
888 reduce_fn: &reduce_fn,
889 init: &init,
890 };
891
892 let work = dest_len.saturating_mul(axis_len);
893 let exec = crate::cost::for_len(exec, KernelClass::Reduce, work)
894 .limit(NonZeroUsize::new(dest_len).unwrap_or(NonZeroUsize::MIN));
895 if !exec.is_serial() {
896 let src_send = SendPtr(src_ptr as *mut T);
897 let out_send = SendPtr(out_ptr);
898 let parts = &parts;
899 if dest_linear {
900 crate::threading::parallel_for_each(0..dest_len, exec, &|range| {
901 unsafe {
905 reduce_axis_range_linear::<T, Op, M, R, U>(
906 src_send.as_const(),
907 out_send.as_ptr(),
908 range,
909 parts,
910 )
911 }
912 });
913 } else {
914 crate::threading::parallel_for_each(0..dest_len, exec, &|range| {
915 unsafe {
917 reduce_axis_range_strided::<T, Op, M, R, U>(
918 src_send.as_const(),
919 out_send.as_ptr(),
920 range,
921 parts,
922 )
923 }
924 });
925 }
926 return Ok(());
927 }
928
929 if dest_linear {
931 unsafe {
932 reduce_axis_range_linear::<T, Op, M, R, U>(src_ptr, out_ptr, 0..dest_len, &parts)
933 };
934 } else {
935 unsafe {
936 reduce_axis_range_strided::<T, Op, M, R, U>(src_ptr, out_ptr, 0..dest_len, &parts)
937 };
938 }
939 Ok(())
940}
941
942fn fill_outputs_with<U: Clone>(dest: &mut StridedViewMut<U>, value: &U) {
949 let dims = dest.dims();
950 if dims.contains(&0) {
951 return;
952 }
953 let strides = dest.strides();
954 let rank = dims.len();
955 let total: usize = dims.iter().product();
956 let base = dest.as_mut_ptr();
957 if rank == 0 {
958 unsafe { *base = value.clone() };
960 return;
961 }
962 let mut coords_inline = [0usize; strided_view::INLINE_RANK];
963 let mut coords_heap: Vec<usize> = Vec::new();
964 let coords: &mut [usize] = if rank <= strided_view::INLINE_RANK {
965 &mut coords_inline[..rank]
966 } else {
967 coords_heap.resize(rank, 0);
968 &mut coords_heap[..]
969 };
970 let mut offset = 0isize;
971 for _ in 0..total {
972 unsafe { *base.offset(offset) = value.clone() };
976 for axis in 0..rank {
977 coords[axis] += 1;
978 offset += strides[axis];
979 if coords[axis] < dims[axis] {
980 break;
981 }
982 coords[axis] = 0;
983 offset -= dims[axis] as isize * strides[axis];
984 }
985 }
986}
987
988struct AxisParts<'a, M, R, U> {
991 kept: &'a [(usize, isize)],
993 dest_strides: &'a [isize],
995 axis_len: usize,
996 axis_stride: isize,
997 map_fn: &'a M,
998 reduce_fn: &'a R,
999 init: &'a U,
1000}
1001
1002#[inline(never)]
1015unsafe fn reduce_axis_range_linear<T, Op, M, R, U>(
1016 src: *const T,
1017 out: *mut U,
1018 range: Range<usize>,
1019 parts: &AxisParts<'_, M, R, U>,
1020) where
1021 T: Copy,
1022 Op: ElementOp<T>,
1023 M: Fn(T) -> U,
1024 R: Fn(U, U) -> U,
1025 U: Clone,
1026{
1027 let kept = parts.kept;
1028 let (lead_extent, lead_stride) = kept[0];
1029 let sweep = lead_stride == 1 && lead_extent >= AXIS_SWEEP_MIN_LEN && parts.axis_len > 1;
1030 let block = (AXIS_SWEEP_BLOCK_BYTES / std::mem::size_of::<U>().max(1)).max(AXIS_SWEEP_MIN_LEN);
1031
1032 let coords_len = kept.len();
1037 let mut coords_inline = [0usize; strided_view::INLINE_RANK];
1038 let mut coords_heap: Vec<usize> = Vec::new();
1039 let coords: &mut [usize] = if coords_len <= strided_view::INLINE_RANK {
1040 &mut coords_inline[..coords_len]
1041 } else {
1042 coords_heap.resize(coords_len, 0);
1043 &mut coords_heap[..]
1044 };
1045 let mut rest = range.start;
1046 let mut src_off = 0isize;
1047 for (coord, &(extent, stride)) in coords.iter_mut().zip(kept) {
1048 *coord = rest % extent;
1049 rest /= extent;
1050 src_off += *coord as isize * stride;
1051 }
1052
1053 let mut output = range.start;
1054 while output < range.end {
1055 let len = if sweep {
1056 (lead_extent - coords[0]).min(range.end - output).min(block)
1057 } else {
1058 1
1059 };
1060 if sweep {
1061 unsafe { sweep_block::<T, Op, M, R, U>(src, src_off, out.add(output), len, parts) };
1065 } else {
1066 unsafe {
1068 let acc = fold_run::<T, Op, M, R, U>(
1069 src.offset(src_off),
1070 parts.axis_stride,
1071 parts.axis_len,
1072 parts.init.clone(),
1073 parts.map_fn,
1074 parts.reduce_fn,
1075 );
1076 *out.add(output) = acc;
1077 }
1078 }
1079 output += len;
1080 if output >= range.end {
1081 break;
1082 }
1083 coords[0] += len;
1086 src_off += len as isize * lead_stride;
1087 let mut axis = 0;
1088 while coords[axis] == kept[axis].0 {
1089 src_off -= kept[axis].0 as isize * kept[axis].1;
1090 coords[axis] = 0;
1091 axis += 1;
1092 coords[axis] += 1;
1093 src_off += kept[axis].1;
1094 }
1095 }
1096}
1097
1098#[inline(never)]
1108unsafe fn reduce_axis_range_strided<T, Op, M, R, U>(
1109 src: *const T,
1110 out: *mut U,
1111 range: Range<usize>,
1112 parts: &AxisParts<'_, M, R, U>,
1113) where
1114 T: Copy,
1115 Op: ElementOp<T>,
1116 M: Fn(T) -> U,
1117 R: Fn(U, U) -> U,
1118 U: Clone,
1119{
1120 let kept = parts.kept;
1121 let dest_strides = parts.dest_strides;
1122 let (lead_extent, lead_stride) = kept[0];
1123 let lead_dest_stride = dest_strides[0];
1124 let sweep = lead_stride == 1
1125 && lead_dest_stride == 1
1126 && lead_extent >= AXIS_SWEEP_MIN_LEN
1127 && parts.axis_len > 1;
1128 let block = (AXIS_SWEEP_BLOCK_BYTES / std::mem::size_of::<U>().max(1)).max(AXIS_SWEEP_MIN_LEN);
1129
1130 let coords_len = kept.len();
1134 let mut coords_inline = [0usize; strided_view::INLINE_RANK];
1135 let mut coords_heap: Vec<usize> = Vec::new();
1136 let coords: &mut [usize] = if coords_len <= strided_view::INLINE_RANK {
1137 &mut coords_inline[..coords_len]
1138 } else {
1139 coords_heap.resize(coords_len, 0);
1140 &mut coords_heap[..]
1141 };
1142 let mut rest = range.start;
1143 let mut src_off = 0isize;
1144 let mut dest_off = 0isize;
1145 for (coord, (&(extent, stride), &dest_stride)) in
1146 coords.iter_mut().zip(kept.iter().zip(dest_strides))
1147 {
1148 *coord = rest % extent;
1149 rest /= extent;
1150 src_off += *coord as isize * stride;
1151 dest_off += *coord as isize * dest_stride;
1152 }
1153
1154 let mut output = range.start;
1155 while output < range.end {
1156 let len = if sweep {
1157 (lead_extent - coords[0]).min(range.end - output).min(block)
1158 } else {
1159 1
1160 };
1161 if sweep {
1162 unsafe {
1165 sweep_block::<T, Op, M, R, U>(src, src_off, out.offset(dest_off), len, parts)
1166 };
1167 } else {
1168 unsafe {
1170 let acc = fold_run::<T, Op, M, R, U>(
1171 src.offset(src_off),
1172 parts.axis_stride,
1173 parts.axis_len,
1174 parts.init.clone(),
1175 parts.map_fn,
1176 parts.reduce_fn,
1177 );
1178 *out.offset(dest_off) = acc;
1179 }
1180 }
1181 output += len;
1182 if output >= range.end {
1183 break;
1184 }
1185 coords[0] += len;
1186 src_off += len as isize * lead_stride;
1187 dest_off += len as isize * lead_dest_stride;
1188 let mut axis = 0;
1189 while coords[axis] == kept[axis].0 {
1190 src_off -= kept[axis].0 as isize * kept[axis].1;
1191 dest_off -= kept[axis].0 as isize * dest_strides[axis];
1192 coords[axis] = 0;
1193 axis += 1;
1194 coords[axis] += 1;
1195 src_off += kept[axis].1;
1196 dest_off += dest_strides[axis];
1197 }
1198 }
1199}
1200
1201#[inline(always)]
1209unsafe fn sweep_block<T, Op, M, R, U>(
1210 src: *const T,
1211 src_off: isize,
1212 out: *mut U,
1213 len: usize,
1214 parts: &AxisParts<'_, M, R, U>,
1215) where
1216 T: Copy,
1217 Op: ElementOp<T>,
1218 M: Fn(T) -> U,
1219 R: Fn(U, U) -> U,
1220 U: Clone,
1221{
1222 let map_fn = parts.map_fn;
1223 let reduce_fn = parts.reduce_fn;
1224 let out = unsafe { std::slice::from_raw_parts_mut(out, len) };
1226 let column = |k: usize| {
1227 unsafe {
1229 std::slice::from_raw_parts(src.offset(src_off + k as isize * parts.axis_stride), len)
1230 }
1231 };
1232 let first = column(0);
1233 for (slot, &value) in out.iter_mut().zip(first) {
1234 *slot = reduce_fn(parts.init.clone(), map_fn(Op::apply(value)));
1235 }
1236 let mut k = 1;
1237 while k + 4 <= parts.axis_len {
1238 let (c0, c1, c2, c3) = (column(k), column(k + 1), column(k + 2), column(k + 3));
1239 for (index, slot) in out.iter_mut().enumerate() {
1240 let mut acc = reduce_fn(slot.clone(), map_fn(Op::apply(c0[index])));
1241 acc = reduce_fn(acc, map_fn(Op::apply(c1[index])));
1242 acc = reduce_fn(acc, map_fn(Op::apply(c2[index])));
1243 acc = reduce_fn(acc, map_fn(Op::apply(c3[index])));
1244 *slot = acc;
1245 }
1246 k += 4;
1247 }
1248 while k < parts.axis_len {
1249 let values = column(k);
1250 for (slot, &value) in out.iter_mut().zip(values) {
1251 *slot = reduce_fn(slot.clone(), map_fn(Op::apply(value)));
1252 }
1253 k += 1;
1254 }
1255}