Skip to main content

strided_basic/
kernel.rs

1//! Kernel iteration engine ported from Julia's Strided.jl/src/mapreduce.jl
2//!
3//! This module implements the core iteration engine that follows Julia's
4//! `_mapreduce_kernel!` pattern for cache-optimized strided array operations.
5
6use crate::fuse::{compress_dims, fuse_dims};
7use crate::inline::{InlineVec, OperandVec};
8use crate::{block, order, Exec, Result, StridedError};
9
10/// Maximum total elements for the small tensor fast path.
11/// Tensors at or below this size skip `compute_order` and `compute_block_sizes`
12/// since they fit in L1 cache and blocking provides no benefit.
13pub const SMALL_TENSOR_THRESHOLD: usize = 1024;
14
15/// Blocking metadata produced by the execution planners; not a layout-validity proof.
16#[derive(Debug)]
17pub struct KernelPlan {
18    // `order` is only read by the `#[cfg(test)]` `for_each_inner_block` traversal.
19    #[cfg_attr(not(test), allow(dead_code))]
20    pub(crate) order: InlineVec<usize>, // inner -> outer
21    pub block: InlineVec<usize>,
22}
23
24/// Build an execution plan for strided iteration (used only in tests).
25///
26/// This follows Julia's `_mapreduce_order!` -> `_mapreduce_block!` pipeline
27/// without fusion:
28/// 1. Compute optimal iteration order
29/// 2. Reorder dims and strides into that order
30/// 3. Compute block sizes for cache efficiency
31#[cfg(test)]
32pub(crate) fn build_plan(
33    dims: &[usize],
34    strides_list: &[&[isize]],
35    dest_index: Option<usize>,
36    elem_sizes: &[usize],
37) -> KernelPlan {
38    let order = order::compute_order(dims, strides_list, dest_index);
39    let ordered_dims: InlineVec<usize> = order.iter().map(|&d| dims[d]).collect();
40    let ordered_strides: OperandVec<InlineVec<isize>> = strides_list
41        .iter()
42        .map(|strides| order.iter().map(|&d| strides[d]).collect())
43        .collect();
44    let ordered_strides_refs: OperandVec<&[isize]> =
45        ordered_strides.iter().map(|s| s.as_slice()).collect();
46    let block = block::compute_block_sizes(&ordered_dims, &ordered_strides_refs, elem_sizes);
47    KernelPlan { order, block }
48}
49
50/// The plan a typed pointwise operation runs: [`build_plan_fused_small`] for
51/// tensors at or below [`SMALL_TENSOR_THRESHOLD`], [`build_plan_fused`]
52/// otherwise, with `elem_sizes[k]` the element size of `strides_list[k]`.
53pub(crate) fn pointwise_plan(
54    dims: &[usize],
55    strides_list: &[&[isize]],
56    dest_index: Option<usize>,
57    elem_sizes: &[usize],
58    total: usize,
59) -> (InlineVec<usize>, OperandVec<InlineVec<isize>>, KernelPlan) {
60    debug_assert_eq!(strides_list.len(), elem_sizes.len());
61    if total <= SMALL_TENSOR_THRESHOLD {
62        build_plan_fused_small(dims, strides_list)
63    } else {
64        build_plan_fused(dims, strides_list, dest_index, elem_sizes)
65    }
66}
67
68/// Build an execution plan with dimension fusion.
69///
70/// Pipeline: order -> reorder -> fuse -> block.
71///
72/// Ordering first ensures that dimensions are sorted by stride importance
73/// (smallest stride innermost). Fusing *after* ordering catches contiguous
74/// dimensions regardless of the original memory layout (column-major,
75/// row-major, or any permutation).
76///
77/// Returns `(fused_dims, ordered_strides, KernelPlan)` where dimensions
78/// and strides are already in iteration order (plan.order is identity).
79///
80/// `elem_sizes[k]` is the element size in bytes of `strides_list[k]`; the
81/// block model forms `strides_list[k][i] * elem_sizes[k]` per operand.
82pub(crate) fn build_plan_fused(
83    dims: &[usize],
84    strides_list: &[&[isize]],
85    dest_index: Option<usize>,
86    elem_sizes: &[usize],
87) -> (InlineVec<usize>, OperandVec<InlineVec<isize>>, KernelPlan) {
88    plan_fused(dims, strides_list, dest_index, elem_sizes, dest_index)
89}
90
91/// [`pointwise_plan`] for a fold into one accumulator that orders its axes
92/// as if operand `order_by` were a destination (`dot`): the same order, fusion
93/// and model tiles, but never the L1 set fit, because a fold's tiles order its
94/// accumulation and must stay the model's (#287).
95pub(crate) fn fold_plan(
96    dims: &[usize],
97    strides_list: &[&[isize]],
98    order_by: usize,
99    elem_sizes: &[usize],
100    total: usize,
101) -> (InlineVec<usize>, OperandVec<InlineVec<isize>>, KernelPlan) {
102    debug_assert_eq!(strides_list.len(), elem_sizes.len());
103    if total <= SMALL_TENSOR_THRESHOLD {
104        build_plan_fused_small(dims, strides_list)
105    } else {
106        plan_fused(dims, strides_list, Some(order_by), elem_sizes, None)
107    }
108}
109
110/// [`build_plan_fused`] with the ordering operand and the destination the
111/// tiles are fitted for given apart; `fit_dest: None` keeps the model's tiles.
112fn plan_fused(
113    dims: &[usize],
114    strides_list: &[&[isize]],
115    dest_index: Option<usize>,
116    elem_sizes: &[usize],
117    fit_dest: Option<usize>,
118) -> (InlineVec<usize>, OperandVec<InlineVec<isize>>, KernelPlan) {
119    // 1. Compute optimal iteration order on original dims
120    let order = order::compute_order(dims, strides_list, dest_index);
121
122    // 2. Reorder dims and strides
123    let ordered_dims: InlineVec<usize> = order.iter().map(|&d| dims[d]).collect();
124    let ordered_strides: OperandVec<InlineVec<isize>> = strides_list
125        .iter()
126        .map(|strides| order.iter().map(|&d| strides[d]).collect())
127        .collect();
128    let ordered_strides_refs: OperandVec<&[isize]> =
129        ordered_strides.iter().map(|s| s.as_slice()).collect();
130
131    // 3. Fuse contiguous dimensions in ordered space
132    let fused_dims = fuse_dims(&ordered_dims, &ordered_strides_refs);
133
134    // 4. Compress: remove size-1 dimensions to reduce loop depth
135    let (compressed_dims, compressed_strides) = compress_dims(&fused_dims, &ordered_strides_refs);
136    let compressed_strides_refs: OperandVec<&[isize]> =
137        compressed_strides.iter().map(|s| s.as_slice()).collect();
138
139    // 5. Compute blocks on the already ordered axes. With a destination the
140    // tiles are also fitted to the L1 sets (#287); a fold keeps the model's
141    // tiles, which order its single accumulator.
142    let identity: InlineVec<usize> = (0..compressed_dims.len()).collect();
143    let block = match fit_dest {
144        Some(dest) => block::destination_block_sizes(
145            &compressed_dims,
146            &compressed_strides_refs,
147            elem_sizes,
148            dest,
149        ),
150        None => block::compute_block_sizes(&compressed_dims, &compressed_strides_refs, elem_sizes),
151    };
152    #[cfg(feature = "bench-hooks")]
153    let block = {
154        let forced = crate::bench_hooks::FORCED_TILES.lock().unwrap();
155        if fit_dest.is_some() && forced.len() == block.len() {
156            InlineVec::from(forced.as_slice())
157        } else {
158            block
159        }
160    };
161
162    (
163        compressed_dims,
164        compressed_strides,
165        KernelPlan {
166            order: identity,
167            block,
168        },
169    )
170}
171
172/// Simplified plan for small tensors that fit in L1 cache.
173///
174/// Skips `compute_order` and `compute_block_sizes` since blocking is
175/// unnecessary for small data. Only fuses and compresses dimensions
176/// to reduce loop depth.
177///
178/// Returns `(fused_dims, fused_strides, KernelPlan)` where the plan's
179/// order is identity and block sizes equal the full dimension sizes.
180pub(crate) fn build_plan_fused_small(
181    dims: &[usize],
182    strides_list: &[&[isize]],
183) -> (InlineVec<usize>, OperandVec<InlineVec<isize>>, KernelPlan) {
184    // Single fuse + compress pass (no ordering needed)
185    let fused = fuse_dims(dims, strides_list);
186    let (fused_dims, fused_strides) = compress_dims(&fused, strides_list);
187
188    // Block = full dimension (no tiling)
189    let block = fused_dims.clone();
190    let identity: InlineVec<usize> = (0..fused_dims.len()).collect();
191
192    (
193        fused_dims,
194        fused_strides,
195        KernelPlan {
196            order: identity,
197            block,
198        },
199    )
200}
201
202// ============================================================================
203// Block-based iteration with inner stride callback
204// ============================================================================
205
206/// Iterate over blocks, calling f with (offsets, block_len, inner_strides).
207///
208/// The callback receives the current byte offsets for each array, the number
209/// of elements in the innermost block, and the innermost strides for each array.
210/// This allows the caller to implement vectorized inner loops.
211#[cfg(test)]
212#[inline]
213pub(crate) fn for_each_inner_block<F>(
214    dims: &[usize],
215    plan: &KernelPlan,
216    strides_list: &[&[isize]],
217    mut f: F,
218) -> Result<()>
219where
220    F: FnMut(&[isize], usize, &[isize]) -> Result<()>,
221{
222    let rank = dims.len();
223    if rank == 0 {
224        let offsets: OperandVec<isize> = strides_list.iter().map(|_| 0isize).collect();
225        return f(&offsets, 1, &[]);
226    }
227
228    // Reorder dimensions and strides according to plan
229    let ordered_dims: InlineVec<usize> = plan.order.iter().map(|&d| dims[d]).collect();
230    let ordered_blocks: InlineVec<usize> = plan.block.clone();
231
232    // Build stride vectors for each array, ordered by plan
233    let mut ordered_strides: OperandVec<InlineVec<isize>> = OperandVec::new();
234    for strides in strides_list {
235        ordered_strides.push(plan.order.iter().map(|&d| strides[d]).collect());
236    }
237    let ordered_strides_refs: OperandVec<&[isize]> =
238        ordered_strides.iter().map(|s| s.as_slice()).collect();
239
240    // Initial offsets (all zero)
241    let mut offsets: OperandVec<isize> = strides_list.iter().map(|_| 0isize).collect();
242
243    // Call the specialized kernel based on rank
244    match rank {
245        1 => kernel_1d_inner(
246            &ordered_dims,
247            &ordered_blocks,
248            &ordered_strides_refs,
249            &mut offsets,
250            &mut f,
251        ),
252        2 => kernel_2d_inner(
253            &ordered_dims,
254            &ordered_blocks,
255            &ordered_strides_refs,
256            &mut offsets,
257            &mut f,
258        ),
259        3 => kernel_3d_inner(
260            &ordered_dims,
261            &ordered_blocks,
262            &ordered_strides_refs,
263            &mut offsets,
264            &mut f,
265        ),
266        4 => kernel_4d_inner(
267            &ordered_dims,
268            &ordered_blocks,
269            &ordered_strides_refs,
270            &mut offsets,
271            &mut f,
272        ),
273        5 => kernel_5d_inner(
274            &ordered_dims,
275            &ordered_blocks,
276            &ordered_strides_refs,
277            &mut offsets,
278            &mut f,
279        ),
280        6 => kernel_6d_inner(
281            &ordered_dims,
282            &ordered_blocks,
283            &ordered_strides_refs,
284            &mut offsets,
285            &mut f,
286        ),
287        7 => kernel_7d_inner(
288            &ordered_dims,
289            &ordered_blocks,
290            &ordered_strides_refs,
291            &mut offsets,
292            &mut f,
293        ),
294        8 => kernel_8d_inner(
295            &ordered_dims,
296            &ordered_blocks,
297            &ordered_strides_refs,
298            &mut offsets,
299            &mut f,
300        ),
301        _ => kernel_nd_inner_iterative(
302            &ordered_dims,
303            &ordered_blocks,
304            &ordered_strides_refs,
305            &mut offsets,
306            &mut f,
307        ),
308    }
309}
310
311// ============================================================================
312// Macro-generated rank-specialized kernels (inner-block callback)
313// ============================================================================
314
315// Every loop below advances an offset only when another position along its
316// level follows, and each loop rewinds its own level on completion. Offsets
317// therefore only ever hold reachable positions of the validated layouts (plus
318// the caller's initial offsets), so no intermediate value can overflow even
319// when a layout ends within one stride of `isize::MAX` (issue #243
320// follow-up). The rewind distance is the difference of two reachable offsets,
321// so it is representable as well.
322
323/// Element-level nested loops for ranks >= 2.
324///
325/// Iterates over the element block, calling `f` at each innermost position.
326/// Levels are listed from outermost to innermost (excluding level 0 which is
327/// the callback level). For a rank-N kernel, element levels are N-1, N-2, ..., 1.
328/// Each level leaves the offsets where it found them.
329macro_rules! elem_loops {
330    // Base case: single level (innermost element level).
331    // Iterates blens[$lv] times, calling f and advancing by stride[$lv]
332    // between calls.
333    ($offsets:ident, $strides:ident, $f:ident, $blens:ident, $is:ident; $lv:literal) => {
334        for _i in 0..$blens[$lv] {
335            $f($offsets, $blens[0], &$is)?;
336            if _i + 1 < $blens[$lv] {
337                for (o, s) in $offsets.iter_mut().zip($strides.iter()) {
338                    *o += s[$lv];
339                }
340            }
341        }
342        let _back = $blens[$lv].saturating_sub(1) as isize;
343        for (o, s) in $offsets.iter_mut().zip($strides.iter()) {
344            *o -= _back * s[$lv];
345        }
346    };
347    // Recursive case: outermost level wraps inner levels, which rewind
348    // themselves; this level advances between inner passes.
349    ($offsets:ident, $strides:ident, $f:ident, $blens:ident, $is:ident;
350     $lv:literal, $next:literal $(, $rest:literal)*) => {
351        for _i in 0..$blens[$lv] {
352            elem_loops!($offsets, $strides, $f, $blens, $is; $next $(, $rest)*);
353            if _i + 1 < $blens[$lv] {
354                for (o, s) in $offsets.iter_mut().zip($strides.iter()) {
355                    *o += s[$lv];
356                }
357            }
358        }
359        let _back = $blens[$lv].saturating_sub(1) as isize;
360        for (o, s) in $offsets.iter_mut().zip($strides.iter()) {
361            *o -= _back * s[$lv];
362        }
363    };
364}
365
366/// Block-level nested while loops for ranks >= 2.
367///
368/// Each block level iterates over tiles of the corresponding dimension.
369/// At level 0 (innermost), element loops are executed. Each block level
370/// advances to the next tile only when one follows and rewinds itself on
371/// completion; inner levels rewind themselves.
372macro_rules! block_loop {
373    // Base case: single block level (the innermost).
374    ($dims:ident, $blocks:ident, $strides:ident, $offsets:ident, $f:ident,
375     $blens:ident, $is:ident; elem=[$($el:literal),+]; $lv0:literal; top=$top:literal) => {{
376        let mut _j = 0usize;
377        let mut _advanced = 0usize;
378        while _j < $dims[$lv0] {
379            $blens[$lv0] = $blocks[$lv0].max(1).min($dims[$lv0]).min($dims[$lv0] - _j);
380            elem_loops!($offsets, $strides, $f, $blens, $is; $($el),+);
381            _j += $blens[$lv0];
382            if _j < $dims[$lv0] {
383                for (o, s) in $offsets.iter_mut().zip($strides.iter()) {
384                    *o += ($blens[$lv0] as isize) * s[$lv0];
385                }
386                _advanced = _j;
387            }
388        }
389        for (o, s) in $offsets.iter_mut().zip($strides.iter()) {
390            *o -= (_advanced as isize) * s[$lv0];
391        }
392    }};
393    // Recursive case: outer block level wraps inner block levels.
394    ($dims:ident, $blocks:ident, $strides:ident, $offsets:ident, $f:ident,
395     $blens:ident, $is:ident; elem=[$($el:literal),+];
396     $lv:literal, $next:literal $(, $rest:literal)*; top=$top:literal) => {{
397        let mut _j = 0usize;
398        let mut _advanced = 0usize;
399        while _j < $dims[$lv] {
400            $blens[$lv] = $blocks[$lv].max(1).min($dims[$lv]).min($dims[$lv] - _j);
401            block_loop!($dims, $blocks, $strides, $offsets, $f, $blens, $is;
402                elem=[$($el),+]; $next $(, $rest)*; top=$top);
403            _j += $blens[$lv];
404            if _j < $dims[$lv] {
405                for (o, s) in $offsets.iter_mut().zip($strides.iter()) {
406                    *o += ($blens[$lv] as isize) * s[$lv];
407                }
408                _advanced = _j;
409            }
410        }
411        for (o, s) in $offsets.iter_mut().zip($strides.iter()) {
412            *o -= (_advanced as isize) * s[$lv];
413        }
414    }};
415}
416
417/// Generate a rank-specialized kernel function.
418///
419/// For rank 1 there are no element loops; only a single block loop on dim 0.
420/// For rank >= 2, block loops nest from outermost to innermost (dim 0), and
421/// element loops nest from dim N-1 down to dim 1 inside the innermost block.
422/// The offsets are back at their starting values on return.
423macro_rules! make_kernel {
424    // Rank 1: single block loop, no element nesting.
425    ($name:ident, rank=1) => {
426        #[inline]
427        fn $name<F>(
428            dims: &[usize],
429            blocks: &[usize],
430            strides: &[&[isize]],
431            offsets: &mut [isize],
432            f: &mut F,
433        ) -> Result<()>
434        where
435            F: FnMut(&[isize], usize, &[isize]) -> Result<()>,
436        {
437            let d0 = dims[0];
438            let b0 = blocks[0].max(1).min(d0);
439            let inner_strides: OperandVec<isize> = strides.iter().map(|s| s[0]).collect();
440
441            let mut j0 = 0usize;
442            let mut advanced = 0usize;
443            while j0 < d0 {
444                let blen0 = b0.min(d0 - j0);
445                f(offsets, blen0, &inner_strides)?;
446                j0 += blen0;
447                if j0 < d0 {
448                    for (o, s) in offsets.iter_mut().zip(strides.iter()) {
449                        *o += (blen0 as isize) * s[0];
450                    }
451                    advanced = j0;
452                }
453            }
454            for (o, s) in offsets.iter_mut().zip(strides.iter()) {
455                *o -= (advanced as isize) * s[0];
456            }
457            Ok(())
458        }
459    };
460    // Rank >= 2: nested block loops + element loops.
461    //   block=[outermost, ..., 0]  - block loop levels from outermost to innermost
462    //   elem=[N-1, ..., 1]         - element loop levels from outermost to innermost
463    //   top=N-1                    - topmost element level (= rank - 1)
464    ($name:ident, rank=$rank:literal,
465     block=[$($blk:literal),+], elem=[$($el:literal),+], top=$top:literal) => {
466        #[inline]
467        fn $name<F>(
468            dims: &[usize],
469            blocks: &[usize],
470            strides: &[&[isize]],
471            offsets: &mut [isize],
472            f: &mut F,
473        ) -> Result<()>
474        where
475            F: FnMut(&[isize], usize, &[isize]) -> Result<()>,
476        {
477            let inner_strides: OperandVec<isize> = strides.iter().map(|s| s[0]).collect();
478            let mut blens = [0usize; $rank];
479            block_loop!(dims, blocks, strides, offsets, f, blens, inner_strides;
480                elem=[$($el),+]; $($blk),+; top=$top);
481            Ok(())
482        }
483    };
484}
485
486make_kernel!(kernel_1d_inner, rank = 1);
487make_kernel!(
488    kernel_2d_inner,
489    rank = 2,
490    block = [1, 0],
491    elem = [1],
492    top = 1
493);
494make_kernel!(
495    kernel_3d_inner,
496    rank = 3,
497    block = [2, 1, 0],
498    elem = [2, 1],
499    top = 2
500);
501make_kernel!(
502    kernel_4d_inner,
503    rank = 4,
504    block = [3, 2, 1, 0],
505    elem = [3, 2, 1],
506    top = 3
507);
508make_kernel!(
509    kernel_5d_inner,
510    rank = 5,
511    block = [4, 3, 2, 1, 0],
512    elem = [4, 3, 2, 1],
513    top = 4
514);
515make_kernel!(
516    kernel_6d_inner,
517    rank = 6,
518    block = [5, 4, 3, 2, 1, 0],
519    elem = [5, 4, 3, 2, 1],
520    top = 5
521);
522make_kernel!(
523    kernel_7d_inner,
524    rank = 7,
525    block = [6, 5, 4, 3, 2, 1, 0],
526    elem = [6, 5, 4, 3, 2, 1],
527    top = 6
528);
529make_kernel!(
530    kernel_8d_inner,
531    rank = 8,
532    block = [7, 6, 5, 4, 3, 2, 1, 0],
533    elem = [7, 6, 5, 4, 3, 2, 1],
534    top = 7
535);
536
537/// N-dimensional kernel with inner block callback (iterative form).
538///
539/// Fallback for rank >= 9. Uses a carry-style increment over outer levels
540/// instead of compile-time unrolled nested loops.
541#[inline]
542fn kernel_nd_inner_iterative<F>(
543    dims: &[usize],
544    blocks: &[usize],
545    strides: &[&[isize]],
546    offsets: &mut [isize],
547    f: &mut F,
548) -> Result<()>
549where
550    F: FnMut(&[isize], usize, &[isize]) -> Result<()>,
551{
552    let rank = dims.len();
553    debug_assert!(rank >= 9);
554
555    let d0 = dims[0];
556    let b0 = blocks[0].max(1).min(d0);
557    let inner_strides: OperandVec<isize> = strides.iter().map(|s| s[0]).collect();
558
559    // Current position for each outer level (1..rank-1). Level 0 uses block loop.
560    let mut idx: Vec<usize> = vec![0usize; rank];
561
562    // As in the rank-specialized kernels, offsets advance only when another
563    // position follows and each level rewinds from its last position, so they
564    // never leave the reachable span.
565    if dims.contains(&0) {
566        return Ok(());
567    }
568    loop {
569        // Level 0: callback over contiguous block fragments.
570        let mut j0 = 0usize;
571        let mut advanced = 0usize;
572        while j0 < d0 {
573            let blen0 = b0.min(d0 - j0);
574            f(offsets, blen0, &inner_strides)?;
575            j0 += blen0;
576            if j0 < d0 {
577                for (offset, s) in offsets.iter_mut().zip(strides.iter()) {
578                    *offset += (blen0 as isize) * s[0];
579                }
580                advanced = j0;
581            }
582        }
583        for (offset, s) in offsets.iter_mut().zip(strides.iter()) {
584            *offset -= (advanced as isize) * s[0];
585        }
586
587        // Carry-style increment for outer levels.
588        let mut level = 1usize;
589        loop {
590            if idx[level] + 1 < dims[level] {
591                idx[level] += 1;
592                for (offset, s) in offsets.iter_mut().zip(strides.iter()) {
593                    *offset += s[level];
594                }
595                break;
596            }
597
598            let last = (dims[level] - 1) as isize;
599            idx[level] = 0;
600            for (offset, s) in offsets.iter_mut().zip(strides.iter()) {
601                *offset -= last * s[level];
602            }
603            level += 1;
604            if level == rank {
605                return Ok(());
606            }
607        }
608    }
609}
610
611// ============================================================================
612// Pre-ordered iteration (for threaded leaf functions)
613// ============================================================================
614
615/// Iterate over blocks with pre-ordered dimensions and initial offsets.
616///
617/// Unlike `for_each_inner_block`, this function assumes that `dims`, `blocks`,
618/// and `strides` are **already in iteration order** (i.e., identity ordering).
619/// It also accepts `initial_offsets` which are added to the starting offsets
620/// before iteration begins.
621///
622/// This avoids the redundant re-ordering and per-callback `Vec` allocation
623/// that `for_each_inner_block_with_offsets` previously incurred.
624///
625/// The block-walking machinery is compiled once (`preordered_dyn`): a generic
626/// caller only instantiates its own callback, reached through one indirect call
627/// per inner block (a run of elements, never per element). Keeping the walk
628/// generic would duplicate it for every operation, dtype and element-op
629/// combination of every downstream crate.
630#[inline]
631pub(crate) fn for_each_inner_block_preordered<S: AsRef<[isize]>, F>(
632    dims: &[usize],
633    blocks: &[usize],
634    strides: &[S],
635    initial_offsets: &[isize],
636    mut f: F,
637) -> Result<()>
638where
639    F: FnMut(&[isize], usize, &[isize]) -> Result<()>,
640{
641    let refs: OperandVec<&[isize]> = strides.iter().map(|s| s.as_ref()).collect();
642    preordered_dyn(dims, blocks, &refs, initial_offsets, &mut f)
643}
644
645type BlockFn<'a> = &'a mut dyn FnMut(&[isize], usize, &[isize]) -> Result<()>;
646
647#[inline(never)]
648fn preordered_dyn(
649    dims: &[usize],
650    blocks: &[usize],
651    strides: &[&[isize]],
652    initial_offsets: &[isize],
653    mut f: BlockFn<'_>,
654) -> Result<()> {
655    let rank = dims.len();
656    if rank == 0 {
657        return f(initial_offsets, 1, &[]);
658    }
659
660    // Start from initial_offsets (kernel functions reset to starting values at end)
661    let mut offsets: OperandVec<isize> = initial_offsets.iter().copied().collect();
662
663    match rank {
664        1 => kernel_1d_inner(dims, blocks, strides, &mut offsets, &mut f),
665        2 => kernel_2d_inner(dims, blocks, strides, &mut offsets, &mut f),
666        3 => kernel_3d_inner(dims, blocks, strides, &mut offsets, &mut f),
667        4 => kernel_4d_inner(dims, blocks, strides, &mut offsets, &mut f),
668        5 => kernel_5d_inner(dims, blocks, strides, &mut offsets, &mut f),
669        6 => kernel_6d_inner(dims, blocks, strides, &mut offsets, &mut f),
670        7 => kernel_7d_inner(dims, blocks, strides, &mut offsets, &mut f),
671        8 => kernel_8d_inner(dims, blocks, strides, &mut offsets, &mut f),
672        _ => kernel_nd_inner_iterative(dims, blocks, strides, &mut offsets, &mut f),
673    }
674}
675
676// ============================================================================
677// Utility functions
678// ============================================================================
679
680/// Check exact shape agreement before prevalidated replay.
681///
682/// # Examples
683///
684/// ```
685/// use strided_basic::execution::ensure_same_shape;
686/// ensure_same_shape(&[2, 3], &[2, 3]).unwrap();
687/// assert!(ensure_same_shape(&[2, 3], &[3, 2]).is_err());
688/// ```
689///
690/// # Errors
691///
692/// Returns [`StridedError::RankMismatch`] when the two shapes have different
693/// ranks, and [`StridedError::ShapeMismatch`] when their extents differ.
694pub fn ensure_same_shape(a: &[usize], b: &[usize]) -> Result<()> {
695    if a.len() != b.len() {
696        return Err(crate::StridedError::RankMismatch(a.len(), b.len()));
697    }
698    if a != b {
699        return Err(crate::StridedError::ShapeMismatch(a.to_vec(), b.to_vec()));
700    }
701    Ok(())
702}
703
704#[derive(Copy, Clone, Debug, Eq, PartialEq)]
705pub(crate) enum ContiguousLayout {
706    /// C-like layout: last axis varies fastest.
707    RowMajor,
708    /// Julia/Fortran-like layout: first axis varies fastest.
709    ColMajor,
710}
711
712/// Returns the contiguous memory layout kind for the given (dims, strides).
713///
714/// Notes:
715/// - Ignores axes with `dim <= 1` since they do not affect addressability.
716/// - Does not treat negative-stride views as contiguous for fast-path purposes.
717pub(crate) fn contiguous_layout(dims: &[usize], strides: &[isize]) -> Option<ContiguousLayout> {
718    if dims.len() != strides.len() {
719        return None;
720    }
721    if dims.is_empty() {
722        return Some(ContiguousLayout::RowMajor);
723    }
724
725    // Row-major: check from last to first.
726    let mut expected = 1isize;
727    let mut row_ok = true;
728    for (&dim, &stride) in dims.iter().rev().zip(strides.iter().rev()) {
729        if dim <= 1 {
730            continue;
731        }
732        if stride != expected {
733            row_ok = false;
734            break;
735        }
736        expected = expected.saturating_mul(dim as isize);
737    }
738    if row_ok {
739        return Some(ContiguousLayout::RowMajor);
740    }
741
742    // Col-major: check from first to last.
743    let mut expected = 1isize;
744    for (&dim, &stride) in dims.iter().zip(strides.iter()) {
745        if dim <= 1 {
746            continue;
747        }
748        if stride != expected {
749            return None;
750        }
751        expected = expected.saturating_mul(dim as isize);
752    }
753    Some(ContiguousLayout::ColMajor)
754}
755
756/// Checked element count of `dims`.
757///
758/// A shape containing a zero extent has zero elements even when the product
759/// of its other extents would overflow; such views pass
760/// `strided_view::validate_bounds`, so this must not form that product. A
761/// nonempty shape whose element count exceeds `usize::MAX` (for example a
762/// huge stride-0 broadcast) returns [`StridedError::OffsetOverflow`].
763pub(crate) fn total_len(dims: &[usize]) -> Result<usize> {
764    if dims.contains(&0) {
765        return Ok(0);
766    }
767    dims.iter()
768        .try_fold(1usize, |acc, &dim| acc.checked_mul(dim))
769        .ok_or(StridedError::OffsetOverflow)
770}
771
772/// Whether the sequential contiguous fast path should be used.
773///
774/// When a fork over `total` elements of `class` pays and `exec` has a second slot,
775/// the contiguous fast path must not be taken so that the parallel kernel path
776/// can be reached. A serial token has no threaded path to reach and the
777/// sequential slice loop is the right kernel.
778#[inline]
779pub(crate) fn use_sequential_fast_path(
780    class: crate::cost::KernelClass,
781    total: usize,
782    exec: &Exec<'_>,
783) -> bool {
784    !crate::threading::is_parallel(class, total, exec)
785}
786
787/// Returns the common contiguous layout if **all** provided stride arrays
788/// share the same contiguous layout for the given `dims`.
789///
790/// Returns `None` if `strides_list` is empty, any array is not contiguous,
791/// or any two arrays have different contiguous layouts.
792#[inline]
793pub(crate) fn same_contiguous_layout(
794    dims: &[usize],
795    strides_list: &[&[isize]],
796) -> Option<ContiguousLayout> {
797    let first = contiguous_layout(dims, strides_list.first()?)?;
798    for strides in &strides_list[1..] {
799        if contiguous_layout(dims, strides)? != first {
800            return None;
801        }
802    }
803    Some(first)
804}
805
806/// Returns the common contiguous layout only when the sequential fast path
807/// should be used (a fork over the elements does not pay for `class`, or a serial token).
808///
809/// `class` is the cost class of the kernel the caller would otherwise fork:
810/// a copy asks as `Copy`, a reduction as `Reduce`, an element map as `Map`.
811///
812/// Returns [`StridedError::OffsetOverflow`] when the element count of `dims`
813/// does not fit in `usize`.
814#[inline]
815pub(crate) fn sequential_contiguous_layout(
816    class: crate::cost::KernelClass,
817    dims: &[usize],
818    strides_list: &[&[isize]],
819    exec: &Exec<'_>,
820) -> Result<Option<ContiguousLayout>> {
821    if !use_sequential_fast_path(class, total_len(dims)?, exec) {
822        return Ok(None);
823    }
824    Ok(same_contiguous_layout(dims, strides_list))
825}
826
827#[cfg(test)]
828#[path = "kernel/tests/tests.rs"]
829mod tests;