Skip to main content

strided_basic/
reduce_view.rs

1//! Reduce operations on dynamic-rank strided views.
2
3use 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
21/// Number of independent accumulators of [`fold_contiguous`].
22const FOLD_LANES: usize = 16;
23
24/// Minimum outputs along a unit-stride kept axis for the column sweep of
25/// [`reduce_axis`].
26const AXIS_SWEEP_MIN_LEN: usize = 16;
27
28/// Byte budget of one output block of the column sweep of [`reduce_axis`].
29const AXIS_SWEEP_BLOCK_BYTES: usize = 64 * 1024;
30
31/// Combines the lanes of [`fold_contiguous`] left to right, after `init`.
32///
33/// Not inlined on purpose: the lane array crosses the call by memory, which
34/// keeps the lanes of the surrounding loop in vector registers. Inlined, the
35/// final fold makes the loop half-extract and re-insert every lane (on x86-64
36/// AVX2 `f64` max: 18 shuffles per 16 elements) although it runs once.
37#[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/// Folds a contiguous run with [`FOLD_LANES`] independent accumulators.
46///
47/// Lane `i` starts from element `i` and folds elements `i + FOLD_LANES`,
48/// `i + 2 * FOLD_LANES`, ... in order; the remainder is folded into the first
49/// lanes. `init` is combined exactly once, before lane 0, and the lanes are
50/// then combined left to right by [`fold_lanes`]. Independent lanes let the
51/// compiler keep several vector accumulators in flight instead of one serial
52/// dependency chain, which is what makes a closure-based sum or max approach
53/// the speed of a hand written lane loop.
54#[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/// Folds `len` elements starting at `ptr` with step `stride`.
85///
86/// # Safety
87/// `ptr.offset(i * stride)` must be a readable element for every `i < len`.
88#[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        // SAFETY: the caller proves `len` readable unit-stride elements.
106        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        // SAFETY: the caller proves every element of the run is readable.
113        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
121/// Full reduction with map function: `reduce(init, op, map.(src))`.
122///
123/// # Evaluation order
124///
125/// The result is independent of the pool when the call runs with a serial
126/// token ([`Exec::serial`]) or a budget of one: only serial branches run, and
127/// their fold order is fixed by the source layout. With a larger budget the
128/// fold is split over the budget, so the result is repeatable for a fixed
129/// shape, layout and budget but can differ between budgets.
130///
131/// In neither case is this a strict left to right fold: a contiguous source is
132/// folded with sixteen independent lanes (see the crate source for the exact
133/// lane assignment), non-contiguous sources are traversed in a cache-friendly
134/// loop order, and parallel execution folds per-task chunks independently
135/// and combines them in a tree. Floating point results can therefore differ
136/// from a sequential left to right sum in the last bits, and no bitwise
137/// equality across machines or target features is guaranteed.
138///
139/// Because of that, `reduce_fn` must be associative and commutative, and
140/// `init` must be an identity of `reduce_fn` whenever the reduction can run on
141/// several threads.
142///
143/// # Allocation
144///
145/// At rank ≤ [`INLINE_RANK`](strided_view::INLINE_RANK) the view metadata and
146/// the traversal plan are stored inline, so a call performs no heap
147/// allocation. Above that bound the planner may spill to the heap.
148///
149/// Because `map_fn` and `reduce_fn` are opaque closures this entry cannot
150/// select the dtype-specific SIMD kernels of [`crate::ErasedReducePlan`];
151/// callers that reduce with a known operation (sum, product, max, min) on a
152/// supported dtype can use that plan for the fastest path.
153///
154/// # Errors
155///
156/// Returns [`StridedError::OffsetOverflow`] when the element count of `src`
157/// does not fit `usize`.
158pub 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    // A zero-element reduction is exactly `init`. Return before planning: an
190    // empty view is allowed to carry an arbitrarily large stride, which the
191    // block-size arithmetic of the planner cannot represent.
192    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    // Parallel contiguous fast path: split into scheduler chunks with slice-based iteration.
207    // This enables LLVM auto-vectorization on each chunk, unlike the general threaded path
208    // which uses scalar pointer-offset loops.
209    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        // The reduction tree combines each split's partial result, so no
247        // worker-count-sized output-slot vector is needed (#306 scope).
248        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/// Folds a contiguous run of two operands with [`FOLD_LANES`] independent
311/// accumulators.
312///
313/// Same lane scheme as [`fold_contiguous`]: lane `i` starts from the pair at
314/// index `i` and folds the pairs at `i + FOLD_LANES`, `i + 2 * FOLD_LANES`,
315/// ... in order, the remainder goes to the first lanes, and `init` is combined
316/// once before the lanes are combined left to right.
317///
318/// The scheduling below deliberately mirrors [`fold_contiguous`] instead of
319/// sharing a generic "map index to value" lane helper: routing the existing
320/// single-operand fold through such an accessor was measured at 0.34 ns/element
321/// against 0.11 ns/element on a contiguous `f64` `reduce` (1 MiB, release,
322/// `--release -j 4`), because the `as_chunks` + `zip` form is what lets the
323/// compiler drop the bound checks and vectorize the 16 lanes. Keep the two
324/// bodies in step by hand; both must use the lane assignment documented here.
325#[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/// Folds `len` operand pairs starting at `a_ptr`/`b_ptr` with the given
374/// strides.
375///
376/// # Safety
377/// `a_ptr.offset(i * a_stride)` and `b_ptr.offset(i * b_stride)` must be
378/// readable elements for every `i < len`.
379#[inline(always)]
380// Run leaf over two strided inputs: both pointers, their strides, the length, the
381// initial value and the two folds.
382#[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        // SAFETY: the caller proves `len` readable unit-stride elements of
404        // both operands.
405        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        // SAFETY: the caller proves every pair of the run is readable.
414        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
427/// Two-input mapped reduction: `reduce(init, op, map.(a[i], b[i]))`.
428///
429/// This is the two-operand sibling of [`reduce`]. It exists so that the
430/// accumulator type `U` is chosen by the caller instead of being tied to the
431/// operand types by `Mul`, which is what makes a widening accumulation
432/// possible — for example an `f32` dot accumulated in `f64`:
433///
434/// ```
435/// use strided_basic::{zip_reduce, Exec, StridedArray};
436///
437/// let a = StridedArray::<f32>::from_fn_col_major(&[2, 3], |i| (1 + i[0] + 2 * i[1]) as f32);
438/// let b = StridedArray::<f32>::from_fn_col_major(&[2, 3], |i| (1 + i[0]) as f32 * 0.5);
439/// let dot: f64 = zip_reduce(
440///     &a.view(),
441///     &b.view(),
442///     |x: f32, y: f32| x as f64 * y as f64,
443///     |x, y| x + y,
444///     0.0,
445///     Exec::serial(),
446/// )
447/// .unwrap();
448/// assert_eq!(dot, 16.5);
449/// ```
450///
451/// Both operands must have the same shape. Each operand's [`ElementOp`] is
452/// applied before `map_fn`, so conjugation and transposition flags are honoured
453/// without materializing a conjugated copy. Permuted, gapped, negative and
454/// stride-0 (broadcast) operands are supported: the traversal is the fused
455/// plan of [`reduce`], extended to two stride lists.
456///
457/// # Evaluation order
458///
459/// The result is independent of the pool when the call runs with a serial
460/// token ([`Exec::serial`]) or a budget of one: only serial branches run, and
461/// their fold order is fixed by the operand layouts. With a larger budget the
462/// fold is split over the budget, so the result is repeatable for a fixed
463/// shape, layout and budget but can differ between budgets.
464///
465/// In neither case is this a strict left to right fold: a contiguous operand
466/// pair is folded with the same sixteen independent lanes as [`reduce`], the
467/// general plan is traversed in a cache-friendly loop order, and parallel
468/// execution folds per-worker chunks independently and combines them in a
469/// tree. Floating point results can therefore differ from a sequential left to
470/// right sum in the last bits, and no bitwise equality across machines or
471/// target features is guaranteed.
472///
473/// Because of that, `reduce_fn` must be associative and commutative, and
474/// `init` must be an identity of `reduce_fn` whenever the reduction can run on
475/// several threads.
476///
477/// # Allocation
478///
479/// At rank ≤ [`INLINE_RANK`](strided_view::INLINE_RANK) the view metadata and
480/// the two-operand traversal plan are stored inline, so a call performs no heap
481/// allocation. Above that bound the planner may spill to the heap.
482///
483/// # Errors
484///
485/// Returns [`StridedError::RankMismatch`] / [`StridedError::ShapeMismatch`] when
486/// the operand shapes differ, and [`StridedError::OffsetOverflow`] for
487/// unrepresentable element counts.
488pub 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    // A zero-element reduction is exactly `init`. Return before planning: an
514    // empty view is allowed to carry an arbitrarily large stride, which the
515    // block-size arithmetic of the planner cannot represent.
516    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            // SAFETY: both operands prove `total` readable elements.
526            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    // Parallel contiguous fast path: split into scheduler chunks so each chunk
533    // folds two contiguous slices, matching the serial contiguous kernel.
534    if is_parallel(KernelClass::Reduce, total, &exec)
535        && same_contiguous_layout(dims, &[a_strides, b_strides]).is_some()
536    {
537        // SAFETY: both operands prove `total` readable elements.
538        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 (fused_dims, ordered_strides, plan) = build_plan_fused(
562        dims,
563        &strides_list,
564        None,
565        &[std::mem::size_of::<A>(), std::mem::size_of::<B>()],
566    );
567
568    let total = total_len(&fused_dims)?;
569    if is_parallel(KernelClass::Reduce, total, &exec) {
570        let a_send = SendPtr(a_ptr as *mut A);
571        let b_send = SendPtr(b_ptr as *mut B);
572        let costs = compute_costs(&ordered_strides);
573        let initial_offsets: crate::inline::OperandVec<isize> =
574            ordered_strides.iter().map(|_| 0isize).collect();
575        let map_fn_ref = &map_fn;
576        let reduce_fn_ref = &reduce_fn;
577        let init_ref = &init;
578        // The reduction tree combines each split's partial result, so no
579        // worker-count-sized output-slot vector is needed (#306 scope).
580        let result = mapreduce_threaded_fold(
581            &fused_dims,
582            &plan.block,
583            &ordered_strides,
584            &initial_offsets,
585            &costs,
586            KernelClass::Reduce,
587            exec,
588            &|dims, blocks, strides_list, offsets| {
589                let mut acc = init_ref.clone();
590                for_each_inner_block_with_offsets(
591                    dims,
592                    blocks,
593                    strides_list,
594                    offsets,
595                    |offsets, len, strides| {
596                        // SAFETY: the plan proves every pair of this block
597                        // is a readable element of both operands.
598                        acc = unsafe {
599                            fold_run2::<A, B, OpA, OpB, M, R, U>(
600                                a_send.as_const().offset(offsets[0]),
601                                strides[0],
602                                b_send.as_const().offset(offsets[1]),
603                                strides[1],
604                                len,
605                                &acc,
606                                map_fn_ref,
607                                reduce_fn_ref,
608                            )
609                        };
610                        Ok(())
611                    },
612                )?;
613                Ok(acc)
614            },
615            &|left, right| reduce_fn_ref(left, right),
616        )?;
617        return Ok(result);
618    }
619
620    let mut acc = init;
621    let initial_offsets: crate::inline::OperandVec<isize> =
622        ordered_strides.iter().map(|_| 0isize).collect();
623    for_each_inner_block_preordered(
624        &fused_dims,
625        &plan.block,
626        &ordered_strides,
627        &initial_offsets,
628        |offsets, len, strides| {
629            // SAFETY: the plan proves every pair of this block is a readable
630            // element of both operands.
631            acc = unsafe {
632                fold_run2::<A, B, OpA, OpB, M, R, U>(
633                    a_ptr.offset(offsets[0]),
634                    strides[0],
635                    b_ptr.offset(offsets[1]),
636                    strides[1],
637                    len,
638                    &acc,
639                    &map_fn,
640                    &reduce_fn,
641                )
642            };
643            Ok(())
644        },
645    )?;
646
647    Ok(acc)
648}
649
650/// Reduce along a single axis, returning a new `StridedArray`.
651///
652/// This allocates a column-major output and delegates to
653/// [`reduce_axis_into`].
654///
655/// Every output folds `init` once and then its reduced elements. When the
656/// reduced axis has unit stride those elements are folded with the lane
657/// scheme of [`reduce`], so `reduce_fn` must be associative and commutative.
658/// When the leading kept axis has unit stride, a block of adjacent outputs
659/// is accumulated one contiguous source column at a time, which keeps the
660/// left to right order per output. Outputs are split across the budget of
661/// `exec` once the number of source elements read exceeds the threading
662/// threshold; each output is computed by one task, so the result does not
663/// depend on the budget.
664///
665/// # Errors
666///
667/// Returns [`StridedError::InvalidAxis`] when `axis >= src.ndim()`, and
668/// [`StridedError::OffsetOverflow`] when the source element count cannot be
669/// represented in `usize`. The destination layout is built here, so the
670/// destination-shape errors of [`reduce_axis_into`] cannot occur.
671///
672/// # Panics
673///
674/// Panics when the kept source extents cannot be described in `isize`, which
675/// an empty source extent hides from the element-count check: reducing axis 0
676/// of a `[0, usize::MAX]` source builds the output strides with
677/// [`col_major_strides`], which panics instead of reporting an error.
678pub fn reduce_axis<T: Copy + Send + Sync, Op: ElementOp<T>, M, R, U>(
679    src: &StridedView<T, Op>,
680    axis: usize,
681    map_fn: M,
682    reduce_fn: R,
683    init: U,
684    exec: Exec<'_>,
685) -> Result<StridedArray<U>>
686where
687    M: Fn(T) -> U + Sync,
688    R: Fn(U, U) -> U + Sync,
689    U: Clone + Send + Sync,
690{
691    let rank = src.ndim();
692    if axis >= rank {
693        return Err(StridedError::InvalidAxis { axis, rank });
694    }
695    // Reject an element count beyond `usize` before allocating the output.
696    total_len(src.dims())?;
697    let out_dims: InlineVec<usize> = src
698        .dims()
699        .iter()
700        .enumerate()
701        .filter(|(i, _)| *i != axis)
702        .map(|(_, &d)| d)
703        .collect();
704    // A full reduction keeps the historical rank-1 shape-[1] output; the
705    // `_into` form accepts any single-element destination for that case.
706    let (out_dims, out_strides) = if out_dims.is_empty() {
707        let mut dims = InlineVec::new();
708        dims.push(1usize);
709        let strides = col_major_strides(&dims);
710        (dims, strides)
711    } else {
712        let strides = col_major_strides(&out_dims);
713        (out_dims, strides)
714    };
715    let total_out = total_len(&out_dims)?;
716    let mut out =
717        StridedArray::<U>::from_parts(vec![init.clone(); total_out], &out_dims, &out_strides, 0)?;
718    {
719        let mut dest = out.view_mut();
720        // The fresh column-major destination needs no validation.
721        reduce_axis_into_impl(&mut dest, src, axis, map_fn, reduce_fn, init, exec)?;
722    }
723    Ok(out)
724}
725
726/// Reduce along a single axis into caller-owned storage.
727///
728/// `dest` must have the source's shape with `axis` removed, or any
729/// single-element destination for a full reduction, and an injective layout.
730/// Every destination element is written: an empty reduced axis fills each
731/// output with `init`.
732///
733/// # Errors
734///
735/// Returns [`StridedError::InvalidAxis`] for `axis >= src.ndim()`,
736/// [`StridedError::RankMismatch`] / [`StridedError::ShapeMismatch`] for a
737/// destination shape that is not the reduced source shape,
738/// [`StridedError::NonInjectiveOutputLayout`] for an overlapping destination,
739/// and [`StridedError::OffsetOverflow`] for unrepresentable sizes.
740///
741/// # Examples
742///
743/// ```
744/// use strided_basic::{reduce_axis_into, Exec, StridedArray};
745/// # let src = StridedArray::<f64>::from_fn_col_major(&[2, 3], |i| (i[0] + 2 * i[1]) as f64);
746/// let mut out = StridedArray::<f64>::col_major(&[3]);
747/// reduce_axis_into(&mut out.view_mut(), &src.view(), 0, |x| x, |a, b| a + b, 0.0, Exec::serial()).unwrap();
748/// assert_eq!(out.get(&[0]), 1.0);
749/// ```
750///
751/// Validation runs here; `reduce_axis_into_impl` is the shared kernel. The
752/// array-returning wrapper owns a fresh column-major destination and calls the
753/// kernel directly, so the common path does not re-validate.
754pub fn reduce_axis_into<T: Copy + Send + Sync, Op: ElementOp<T>, M, R, U>(
755    dest: &mut StridedViewMut<U>,
756    src: &StridedView<T, Op>,
757    axis: usize,
758    map_fn: M,
759    reduce_fn: R,
760    init: U,
761    exec: Exec<'_>,
762) -> Result<()>
763where
764    M: Fn(T) -> U + Sync,
765    R: Fn(U, U) -> U + Sync,
766    U: Clone + Send + Sync,
767{
768    let rank = src.ndim();
769    if axis >= rank {
770        return Err(StridedError::InvalidAxis { axis, rank });
771    }
772    let src_dims = src.dims();
773    // Reject an element count beyond usize (a huge stride-0 broadcast) up
774    // front instead of looping over it.
775    total_len(src_dims)?;
776    let kept_len = rank - 1;
777    let dest_len = total_len(dest.dims())?;
778    if kept_len == 0 {
779        if dest_len != 1 {
780            return Err(StridedError::ShapeMismatch(vec![dest_len], vec![1]));
781        }
782    } else {
783        if dest.ndim() != kept_len {
784            return Err(StridedError::RankMismatch(dest.ndim(), kept_len));
785        }
786        let dest_dims = dest.dims();
787        let mut d = 0usize;
788        for (i, &src_dim) in src_dims.iter().enumerate() {
789            if i == axis {
790                continue;
791            }
792            if src_dim != dest_dims[d] {
793                let expected: Vec<usize> = src_dims
794                    .iter()
795                    .enumerate()
796                    .filter(|(i, _)| *i != axis)
797                    .map(|(_, &d)| d)
798                    .collect();
799                return Err(StridedError::ShapeMismatch(dest_dims.to_vec(), expected));
800            }
801            d += 1;
802        }
803        if !crate::layout_check::is_injective_layout(dest.dims(), dest.strides()) {
804            return Err(StridedError::NonInjectiveOutputLayout);
805        }
806    }
807    reduce_axis_into_impl(dest, src, axis, map_fn, reduce_fn, init, exec)
808}
809
810/// Shared kernel of [`reduce_axis_into`] and [`reduce_axis`].
811///
812/// Assumes the destination has the reduced source shape (or one element for a
813/// full reduction) and an injective layout; the public entry validates that,
814/// while the array-returning wrapper owns a freshly allocated column-major
815/// destination and can skip the re-validation.
816fn reduce_axis_into_impl<T: Copy + Send + Sync, Op: ElementOp<T>, M, R, U>(
817    dest: &mut StridedViewMut<U>,
818    src: &StridedView<T, Op>,
819    axis: usize,
820    map_fn: M,
821    reduce_fn: R,
822    init: U,
823    exec: Exec<'_>,
824) -> Result<()>
825where
826    M: Fn(T) -> U + Sync,
827    R: Fn(U, U) -> U + Sync,
828    U: Clone + Send + Sync,
829{
830    let rank = src.ndim();
831    let src_dims = src.dims();
832    let src_strides = src.strides();
833    let src_ptr = src.ptr();
834    let dest_len = total_len(dest.dims())?;
835    let axis_len = src_dims[axis];
836    let axis_stride = src_strides[axis];
837
838    if axis_len == 0 {
839        // No source elements to fold: every output is `init`. Fill the
840        // destination directly rather than traversing the source, because an
841        // empty source view carries a dangling base pointer and `offset` on it
842        // is UB even when the fold reads zero elements.
843        fill_outputs_with(dest, &init);
844        return Ok(());
845    }
846
847    if rank == 1 {
848        // Full reduction into a single destination element.
849        // SAFETY: the view proves `axis_len` readable elements along `axis`.
850        let acc = unsafe {
851            fold_run::<T, Op, M, R, U>(src_ptr, axis_stride, axis_len, init, &map_fn, &reduce_fn)
852        };
853        unsafe { *dest.as_mut_ptr() = acc };
854        return Ok(());
855    }
856    if dest_len == 0 {
857        return Ok(());
858    }
859
860    // Build the kept-axis metadata in one pass. A column-major destination is
861    // the common case (the array-returning wrapper always allocates one); its
862    // offset equals the linear output index, so its stride list is only
863    // materialized for a strided destination.
864    let dest_stride_view = dest.strides();
865    let mut kept: InlineVec<(usize, isize)> = InlineVec::new();
866    let mut dest_linear = true;
867    let mut prefix = 1usize;
868    for (i, (&dim, &src_stride)) in src_dims.iter().zip(src_strides).enumerate() {
869        if i == axis {
870            continue;
871        }
872        let d = kept.len();
873        kept.push((dim, src_stride));
874        if dest_linear && dest_stride_view[d] != prefix as isize {
875            dest_linear = false;
876        }
877        prefix = prefix.saturating_mul(dim);
878    }
879    let dest_strides: InlineVec<isize> = if dest_linear {
880        InlineVec::new()
881    } else {
882        dest_stride_view.iter().copied().collect()
883    };
884    let out_ptr = dest.as_mut_ptr();
885    let parts = AxisParts {
886        kept: &kept,
887        dest_strides: &dest_strides,
888        axis_len,
889        axis_stride,
890        map_fn: &map_fn,
891        reduce_fn: &reduce_fn,
892        init: &init,
893    };
894
895    let work = dest_len.saturating_mul(axis_len);
896    let exec = crate::cost::for_len(exec, KernelClass::Reduce, work)
897        .limit(NonZeroUsize::new(dest_len).unwrap_or(NonZeroUsize::MIN));
898    if !exec.is_serial() {
899        let src_send = SendPtr(src_ptr as *mut T);
900        let out_send = SendPtr(out_ptr);
901        let parts = &parts;
902        if dest_linear {
903            crate::threading::parallel_for_each(0..dest_len, exec, &|range| {
904                // SAFETY: worker ranges are disjoint, the destination is
905                // injective, and the view proves every source offset
906                // reachable from its kept coordinates.
907                unsafe {
908                    reduce_axis_range_linear::<T, Op, M, R, U>(
909                        src_send.as_const(),
910                        out_send.as_ptr(),
911                        range,
912                        parts,
913                    )
914                }
915            });
916        } else {
917            crate::threading::parallel_for_each(0..dest_len, exec, &|range| {
918                // SAFETY: as for the linear path.
919                unsafe {
920                    reduce_axis_range_strided::<T, Op, M, R, U>(
921                        src_send.as_const(),
922                        out_send.as_ptr(),
923                        range,
924                        parts,
925                    )
926                }
927            });
928        }
929        return Ok(());
930    }
931
932    // SAFETY: as for the parallel ranges, with one range covering all outputs.
933    if dest_linear {
934        unsafe {
935            reduce_axis_range_linear::<T, Op, M, R, U>(src_ptr, out_ptr, 0..dest_len, &parts)
936        };
937    } else {
938        unsafe {
939            reduce_axis_range_strided::<T, Op, M, R, U>(src_ptr, out_ptr, 0..dest_len, &parts)
940        };
941    }
942    Ok(())
943}
944
945/// Writes `value` into every logical destination element.
946///
947/// Used when the reduced axis is empty: the fold would read zero source
948/// elements, so the destination is exactly `init` everywhere and no source
949/// pointer may be formed. The odometer keeps the fill allocation-free within
950/// [`strided_view::INLINE_RANK`] and spills above it.
951fn fill_outputs_with<U: Clone>(dest: &mut StridedViewMut<U>, value: &U) {
952    let dims = dest.dims();
953    if dims.contains(&0) {
954        return;
955    }
956    let strides = dest.strides();
957    let rank = dims.len();
958    let total: usize = dims.iter().product();
959    let base = dest.as_mut_ptr();
960    if rank == 0 {
961        // SAFETY: a rank-0 destination is one writable element.
962        unsafe { *base = value.clone() };
963        return;
964    }
965    let mut coords_inline = [0usize; strided_view::INLINE_RANK];
966    let mut coords_heap: Vec<usize> = Vec::new();
967    let coords: &mut [usize] = if rank <= strided_view::INLINE_RANK {
968        &mut coords_inline[..rank]
969    } else {
970        coords_heap.resize(rank, 0);
971        &mut coords_heap[..]
972    };
973    let mut offset = 0isize;
974    for _ in 0..total {
975        // SAFETY: the destination is an injective view validated by the
976        // caller, and the cursor visits each logical element exactly once, so
977        // every written offset is in bounds.
978        unsafe { *base.offset(offset) = value.clone() };
979        for axis in 0..rank {
980            coords[axis] += 1;
981            offset += strides[axis];
982            if coords[axis] < dims[axis] {
983                break;
984            }
985            coords[axis] = 0;
986            offset -= dims[axis] as isize * strides[axis];
987        }
988    }
989}
990
991/// Shared inputs of [`reduce_axis_range_linear`] and
992/// [`reduce_axis_range_strided`].
993struct AxisParts<'a, M, R, U> {
994    /// `(extent, source stride)` of every kept axis, in output order.
995    kept: &'a [(usize, isize)],
996    /// Destination stride of every kept axis, in the same order.
997    dest_strides: &'a [isize],
998    axis_len: usize,
999    axis_stride: isize,
1000    map_fn: &'a M,
1001    reduce_fn: &'a R,
1002    init: &'a U,
1003}
1004
1005/// Column-major destination cursor: the destination offset is the linear output
1006/// index, so no destination stride bookkeeping is needed.
1007///
1008/// Kept out of line so the common path stays the same single-cursor loop as the
1009/// pre-split kernel.
1010///
1011/// # Safety
1012/// `out` must be a column-major destination of `parts.kept` extents, `range` a
1013/// subrange of its logical output indices that no other thread writes, and
1014/// every source offset reachable from a kept coordinate plus
1015/// `k * parts.axis_stride` for `k < parts.axis_len` must be a readable element
1016/// of `src`.
1017#[inline(never)]
1018unsafe fn reduce_axis_range_linear<T, Op, M, R, U>(
1019    src: *const T,
1020    out: *mut U,
1021    range: Range<usize>,
1022    parts: &AxisParts<'_, M, R, U>,
1023) where
1024    T: Copy,
1025    Op: ElementOp<T>,
1026    M: Fn(T) -> U,
1027    R: Fn(U, U) -> U,
1028    U: Clone,
1029{
1030    let kept = parts.kept;
1031    let (lead_extent, lead_stride) = kept[0];
1032    let sweep = lead_stride == 1 && lead_extent >= AXIS_SWEEP_MIN_LEN && parts.axis_len > 1;
1033    let block = (AXIS_SWEEP_BLOCK_BYTES / std::mem::size_of::<U>().max(1)).max(AXIS_SWEEP_MIN_LEN);
1034
1035    // Decode the first output once, then advance incrementally. A fixed stack
1036    // array with a spill covers every inline rank without the per-access enum
1037    // match a `TinyVec` cursor would add to the hot loop, and allocates only
1038    // above `INLINE_RANK` (#306 P1).
1039    let coords_len = kept.len();
1040    let mut coords_inline = [0usize; strided_view::INLINE_RANK];
1041    let mut coords_heap: Vec<usize> = Vec::new();
1042    let coords: &mut [usize] = if coords_len <= strided_view::INLINE_RANK {
1043        &mut coords_inline[..coords_len]
1044    } else {
1045        coords_heap.resize(coords_len, 0);
1046        &mut coords_heap[..]
1047    };
1048    let mut rest = range.start;
1049    let mut src_off = 0isize;
1050    for (coord, &(extent, stride)) in coords.iter_mut().zip(kept) {
1051        *coord = rest % extent;
1052        rest /= extent;
1053        src_off += *coord as isize * stride;
1054    }
1055
1056    let mut output = range.start;
1057    while output < range.end {
1058        let len = if sweep {
1059            (lead_extent - coords[0]).min(range.end - output).min(block)
1060        } else {
1061            1
1062        };
1063        if sweep {
1064            // SAFETY: the `len` outputs are inside the caller's range, their
1065            // unit-stride destination elements are contiguous, and their
1066            // unit-stride source columns are readable.
1067            unsafe { sweep_block::<T, Op, M, R, U>(src, src_off, out.add(output), len, parts) };
1068        } else {
1069            // SAFETY: one reachable output and its reduced run.
1070            unsafe {
1071                let acc = fold_run::<T, Op, M, R, U>(
1072                    src.offset(src_off),
1073                    parts.axis_stride,
1074                    parts.axis_len,
1075                    parts.init.clone(),
1076                    parts.map_fn,
1077                    parts.reduce_fn,
1078                );
1079                *out.add(output) = acc;
1080            }
1081        }
1082        output += len;
1083        if output >= range.end {
1084            break;
1085        }
1086        // Advance the kept coordinates by `len` along the leading axis; a
1087        // block never crosses the end of the leading axis.
1088        coords[0] += len;
1089        src_off += len as isize * lead_stride;
1090        let mut axis = 0;
1091        while coords[axis] == kept[axis].0 {
1092            src_off -= kept[axis].0 as isize * kept[axis].1;
1093            coords[axis] = 0;
1094            axis += 1;
1095            coords[axis] += 1;
1096            src_off += kept[axis].1;
1097        }
1098    }
1099}
1100
1101/// General strided destination cursor, tracking a destination offset next to
1102/// the source offset.
1103///
1104/// # Safety
1105/// `out` must be a destination of `parts.kept` extents with injective layout,
1106/// `range` a subrange of its logical output indices that no other thread
1107/// writes, and every source offset reachable from a kept coordinate plus
1108/// `k * parts.axis_stride` for `k < parts.axis_len` must be a readable element
1109/// of `src`.
1110#[inline(never)]
1111unsafe fn reduce_axis_range_strided<T, Op, M, R, U>(
1112    src: *const T,
1113    out: *mut U,
1114    range: Range<usize>,
1115    parts: &AxisParts<'_, M, R, U>,
1116) where
1117    T: Copy,
1118    Op: ElementOp<T>,
1119    M: Fn(T) -> U,
1120    R: Fn(U, U) -> U,
1121    U: Clone,
1122{
1123    let kept = parts.kept;
1124    let dest_strides = parts.dest_strides;
1125    let (lead_extent, lead_stride) = kept[0];
1126    let lead_dest_stride = dest_strides[0];
1127    let sweep = lead_stride == 1
1128        && lead_dest_stride == 1
1129        && lead_extent >= AXIS_SWEEP_MIN_LEN
1130        && parts.axis_len > 1;
1131    let block = (AXIS_SWEEP_BLOCK_BYTES / std::mem::size_of::<U>().max(1)).max(AXIS_SWEEP_MIN_LEN);
1132
1133    // Same fixed-array-plus-spill cursor as `reduce_axis_range_linear`: the
1134    // `TinyVec` enum match is not paid per output access in the hot loop and
1135    // only ranks above `INLINE_RANK` allocate (#306 P1).
1136    let coords_len = kept.len();
1137    let mut coords_inline = [0usize; strided_view::INLINE_RANK];
1138    let mut coords_heap: Vec<usize> = Vec::new();
1139    let coords: &mut [usize] = if coords_len <= strided_view::INLINE_RANK {
1140        &mut coords_inline[..coords_len]
1141    } else {
1142        coords_heap.resize(coords_len, 0);
1143        &mut coords_heap[..]
1144    };
1145    let mut rest = range.start;
1146    let mut src_off = 0isize;
1147    let mut dest_off = 0isize;
1148    for (coord, (&(extent, stride), &dest_stride)) in
1149        coords.iter_mut().zip(kept.iter().zip(dest_strides))
1150    {
1151        *coord = rest % extent;
1152        rest /= extent;
1153        src_off += *coord as isize * stride;
1154        dest_off += *coord as isize * dest_stride;
1155    }
1156
1157    let mut output = range.start;
1158    while output < range.end {
1159        let len = if sweep {
1160            (lead_extent - coords[0]).min(range.end - output).min(block)
1161        } else {
1162            1
1163        };
1164        if sweep {
1165            // SAFETY: as for the linear cursor; `lead_dest_stride == 1` makes
1166            // the `len` destinations contiguous.
1167            unsafe {
1168                sweep_block::<T, Op, M, R, U>(src, src_off, out.offset(dest_off), len, parts)
1169            };
1170        } else {
1171            // SAFETY: one reachable output and its reduced run.
1172            unsafe {
1173                let acc = fold_run::<T, Op, M, R, U>(
1174                    src.offset(src_off),
1175                    parts.axis_stride,
1176                    parts.axis_len,
1177                    parts.init.clone(),
1178                    parts.map_fn,
1179                    parts.reduce_fn,
1180                );
1181                *out.offset(dest_off) = acc;
1182            }
1183        }
1184        output += len;
1185        if output >= range.end {
1186            break;
1187        }
1188        coords[0] += len;
1189        src_off += len as isize * lead_stride;
1190        dest_off += len as isize * lead_dest_stride;
1191        let mut axis = 0;
1192        while coords[axis] == kept[axis].0 {
1193            src_off -= kept[axis].0 as isize * kept[axis].1;
1194            dest_off -= kept[axis].0 as isize * dest_strides[axis];
1195            coords[axis] = 0;
1196            axis += 1;
1197            coords[axis] += 1;
1198            src_off += kept[axis].1;
1199            dest_off += dest_strides[axis];
1200        }
1201    }
1202}
1203
1204/// Accumulates `len` adjacent outputs, one contiguous source column per
1205/// reduced index, keeping the left to right order per output.
1206///
1207/// # Safety
1208/// `out` must be `len` writable initialized outputs and `src + src_off +
1209/// k * parts.axis_stride` must start `len` readable elements for every
1210/// `k < parts.axis_len`.
1211#[inline(always)]
1212unsafe fn sweep_block<T, Op, M, R, U>(
1213    src: *const T,
1214    src_off: isize,
1215    out: *mut U,
1216    len: usize,
1217    parts: &AxisParts<'_, M, R, U>,
1218) where
1219    T: Copy,
1220    Op: ElementOp<T>,
1221    M: Fn(T) -> U,
1222    R: Fn(U, U) -> U,
1223    U: Clone,
1224{
1225    let map_fn = parts.map_fn;
1226    let reduce_fn = parts.reduce_fn;
1227    // SAFETY: forwarded caller contract.
1228    let out = unsafe { std::slice::from_raw_parts_mut(out, len) };
1229    let column = |k: usize| {
1230        // SAFETY: forwarded caller contract for reduced index `k`.
1231        unsafe {
1232            std::slice::from_raw_parts(src.offset(src_off + k as isize * parts.axis_stride), len)
1233        }
1234    };
1235    let first = column(0);
1236    for (slot, &value) in out.iter_mut().zip(first) {
1237        *slot = reduce_fn(parts.init.clone(), map_fn(Op::apply(value)));
1238    }
1239    let mut k = 1;
1240    while k + 4 <= parts.axis_len {
1241        let (c0, c1, c2, c3) = (column(k), column(k + 1), column(k + 2), column(k + 3));
1242        for (index, slot) in out.iter_mut().enumerate() {
1243            let mut acc = reduce_fn(slot.clone(), map_fn(Op::apply(c0[index])));
1244            acc = reduce_fn(acc, map_fn(Op::apply(c1[index])));
1245            acc = reduce_fn(acc, map_fn(Op::apply(c2[index])));
1246            acc = reduce_fn(acc, map_fn(Op::apply(c3[index])));
1247            *slot = acc;
1248        }
1249        k += 4;
1250    }
1251    while k < parts.axis_len {
1252        let values = column(k);
1253        for (slot, &value) in out.iter_mut().zip(values) {
1254            *slot = reduce_fn(slot.clone(), map_fn(Op::apply(value)));
1255        }
1256        k += 1;
1257    }
1258}