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