1use crate::fuse::{compress_dims, fuse_dims};
7use crate::inline::{InlineVec, OperandVec};
8use crate::{block, order, Exec, Result, StridedError};
9
10pub const SMALL_TENSOR_THRESHOLD: usize = 1024;
14
15#[derive(Debug)]
17pub struct KernelPlan {
18 #[cfg_attr(not(test), allow(dead_code))]
19 pub(crate) order: InlineVec<usize>, pub block: InlineVec<usize>,
21}
22
23#[cfg(test)]
31pub(crate) fn build_plan(
32 dims: &[usize],
33 strides_list: &[&[isize]],
34 dest_index: Option<usize>,
35 elem_size: usize,
36) -> KernelPlan {
37 let order = order::compute_order(dims, strides_list, dest_index);
38 let ordered_dims: InlineVec<usize> = order.iter().map(|&d| dims[d]).collect();
39 let ordered_strides: OperandVec<InlineVec<isize>> = strides_list
40 .iter()
41 .map(|strides| order.iter().map(|&d| strides[d]).collect())
42 .collect();
43 let ordered_strides_refs: OperandVec<&[isize]> =
44 ordered_strides.iter().map(|s| s.as_slice()).collect();
45 let block = block::compute_block_sizes(&ordered_dims, &ordered_strides_refs, elem_size);
46 KernelPlan { order, block }
47}
48
49pub(crate) fn build_plan_fused(
61 dims: &[usize],
62 strides_list: &[&[isize]],
63 dest_index: Option<usize>,
64 elem_size: usize,
65) -> (InlineVec<usize>, OperandVec<InlineVec<isize>>, KernelPlan) {
66 let order = order::compute_order(dims, strides_list, dest_index);
68
69 let ordered_dims: InlineVec<usize> = order.iter().map(|&d| dims[d]).collect();
71 let ordered_strides: OperandVec<InlineVec<isize>> = strides_list
72 .iter()
73 .map(|strides| order.iter().map(|&d| strides[d]).collect())
74 .collect();
75 let ordered_strides_refs: OperandVec<&[isize]> =
76 ordered_strides.iter().map(|s| s.as_slice()).collect();
77
78 let fused_dims = fuse_dims(&ordered_dims, &ordered_strides_refs);
80
81 let (compressed_dims, compressed_strides) = compress_dims(&fused_dims, &ordered_strides_refs);
83 let compressed_strides_refs: OperandVec<&[isize]> =
84 compressed_strides.iter().map(|s| s.as_slice()).collect();
85
86 let identity: InlineVec<usize> = (0..compressed_dims.len()).collect();
88 let block = block::compute_block_sizes(&compressed_dims, &compressed_strides_refs, elem_size);
89
90 (
91 compressed_dims,
92 compressed_strides,
93 KernelPlan {
94 order: identity,
95 block,
96 },
97 )
98}
99
100pub(crate) fn build_plan_fused_small(
109 dims: &[usize],
110 strides_list: &[&[isize]],
111) -> (InlineVec<usize>, OperandVec<InlineVec<isize>>, KernelPlan) {
112 let fused = fuse_dims(dims, strides_list);
114 let (fused_dims, fused_strides) = compress_dims(&fused, strides_list);
115
116 let block = fused_dims.clone();
118 let identity: InlineVec<usize> = (0..fused_dims.len()).collect();
119
120 (
121 fused_dims,
122 fused_strides,
123 KernelPlan {
124 order: identity,
125 block,
126 },
127 )
128}
129
130#[cfg(test)]
140#[inline]
141pub(crate) fn for_each_inner_block<F>(
142 dims: &[usize],
143 plan: &KernelPlan,
144 strides_list: &[&[isize]],
145 mut f: F,
146) -> Result<()>
147where
148 F: FnMut(&[isize], usize, &[isize]) -> Result<()>,
149{
150 let rank = dims.len();
151 if rank == 0 {
152 let offsets: OperandVec<isize> = strides_list.iter().map(|_| 0isize).collect();
153 return f(&offsets, 1, &[]);
154 }
155
156 let ordered_dims: InlineVec<usize> = plan.order.iter().map(|&d| dims[d]).collect();
158 let ordered_blocks: InlineVec<usize> = plan.block.clone();
159
160 let mut ordered_strides: OperandVec<InlineVec<isize>> = OperandVec::new();
162 for strides in strides_list {
163 ordered_strides.push(plan.order.iter().map(|&d| strides[d]).collect());
164 }
165 let ordered_strides_refs: OperandVec<&[isize]> =
166 ordered_strides.iter().map(|s| s.as_slice()).collect();
167
168 let mut offsets: OperandVec<isize> = strides_list.iter().map(|_| 0isize).collect();
170
171 match rank {
173 1 => kernel_1d_inner(
174 &ordered_dims,
175 &ordered_blocks,
176 &ordered_strides_refs,
177 &mut offsets,
178 &mut f,
179 ),
180 2 => kernel_2d_inner(
181 &ordered_dims,
182 &ordered_blocks,
183 &ordered_strides_refs,
184 &mut offsets,
185 &mut f,
186 ),
187 3 => kernel_3d_inner(
188 &ordered_dims,
189 &ordered_blocks,
190 &ordered_strides_refs,
191 &mut offsets,
192 &mut f,
193 ),
194 4 => kernel_4d_inner(
195 &ordered_dims,
196 &ordered_blocks,
197 &ordered_strides_refs,
198 &mut offsets,
199 &mut f,
200 ),
201 5 => kernel_5d_inner(
202 &ordered_dims,
203 &ordered_blocks,
204 &ordered_strides_refs,
205 &mut offsets,
206 &mut f,
207 ),
208 6 => kernel_6d_inner(
209 &ordered_dims,
210 &ordered_blocks,
211 &ordered_strides_refs,
212 &mut offsets,
213 &mut f,
214 ),
215 7 => kernel_7d_inner(
216 &ordered_dims,
217 &ordered_blocks,
218 &ordered_strides_refs,
219 &mut offsets,
220 &mut f,
221 ),
222 8 => kernel_8d_inner(
223 &ordered_dims,
224 &ordered_blocks,
225 &ordered_strides_refs,
226 &mut offsets,
227 &mut f,
228 ),
229 _ => kernel_nd_inner_iterative(
230 &ordered_dims,
231 &ordered_blocks,
232 &ordered_strides_refs,
233 &mut offsets,
234 &mut f,
235 ),
236 }
237}
238
239macro_rules! elem_loops {
258 ($offsets:ident, $strides:ident, $f:ident, $blens:ident, $is:ident; $lv:literal) => {
262 for _i in 0..$blens[$lv] {
263 $f($offsets, $blens[0], &$is)?;
264 if _i + 1 < $blens[$lv] {
265 for (o, s) in $offsets.iter_mut().zip($strides.iter()) {
266 *o += s[$lv];
267 }
268 }
269 }
270 let _back = $blens[$lv].saturating_sub(1) as isize;
271 for (o, s) in $offsets.iter_mut().zip($strides.iter()) {
272 *o -= _back * s[$lv];
273 }
274 };
275 ($offsets:ident, $strides:ident, $f:ident, $blens:ident, $is:ident;
278 $lv:literal, $next:literal $(, $rest:literal)*) => {
279 for _i in 0..$blens[$lv] {
280 elem_loops!($offsets, $strides, $f, $blens, $is; $next $(, $rest)*);
281 if _i + 1 < $blens[$lv] {
282 for (o, s) in $offsets.iter_mut().zip($strides.iter()) {
283 *o += s[$lv];
284 }
285 }
286 }
287 let _back = $blens[$lv].saturating_sub(1) as isize;
288 for (o, s) in $offsets.iter_mut().zip($strides.iter()) {
289 *o -= _back * s[$lv];
290 }
291 };
292}
293
294macro_rules! block_loop {
301 ($dims:ident, $blocks:ident, $strides:ident, $offsets:ident, $f:ident,
303 $blens:ident, $is:ident; elem=[$($el:literal),+]; $lv0:literal; top=$top:literal) => {{
304 let mut _j = 0usize;
305 let mut _advanced = 0usize;
306 while _j < $dims[$lv0] {
307 $blens[$lv0] = $blocks[$lv0].max(1).min($dims[$lv0]).min($dims[$lv0] - _j);
308 elem_loops!($offsets, $strides, $f, $blens, $is; $($el),+);
309 _j += $blens[$lv0];
310 if _j < $dims[$lv0] {
311 for (o, s) in $offsets.iter_mut().zip($strides.iter()) {
312 *o += ($blens[$lv0] as isize) * s[$lv0];
313 }
314 _advanced = _j;
315 }
316 }
317 for (o, s) in $offsets.iter_mut().zip($strides.iter()) {
318 *o -= (_advanced as isize) * s[$lv0];
319 }
320 }};
321 ($dims:ident, $blocks:ident, $strides:ident, $offsets:ident, $f:ident,
323 $blens:ident, $is:ident; elem=[$($el:literal),+];
324 $lv:literal, $next:literal $(, $rest:literal)*; top=$top:literal) => {{
325 let mut _j = 0usize;
326 let mut _advanced = 0usize;
327 while _j < $dims[$lv] {
328 $blens[$lv] = $blocks[$lv].max(1).min($dims[$lv]).min($dims[$lv] - _j);
329 block_loop!($dims, $blocks, $strides, $offsets, $f, $blens, $is;
330 elem=[$($el),+]; $next $(, $rest)*; top=$top);
331 _j += $blens[$lv];
332 if _j < $dims[$lv] {
333 for (o, s) in $offsets.iter_mut().zip($strides.iter()) {
334 *o += ($blens[$lv] as isize) * s[$lv];
335 }
336 _advanced = _j;
337 }
338 }
339 for (o, s) in $offsets.iter_mut().zip($strides.iter()) {
340 *o -= (_advanced as isize) * s[$lv];
341 }
342 }};
343}
344
345macro_rules! make_kernel {
352 ($name:ident, rank=1) => {
354 #[inline]
355 fn $name<F>(
356 dims: &[usize],
357 blocks: &[usize],
358 strides: &[&[isize]],
359 offsets: &mut [isize],
360 f: &mut F,
361 ) -> Result<()>
362 where
363 F: FnMut(&[isize], usize, &[isize]) -> Result<()>,
364 {
365 let d0 = dims[0];
366 let b0 = blocks[0].max(1).min(d0);
367 let inner_strides: OperandVec<isize> = strides.iter().map(|s| s[0]).collect();
368
369 let mut j0 = 0usize;
370 let mut advanced = 0usize;
371 while j0 < d0 {
372 let blen0 = b0.min(d0 - j0);
373 f(offsets, blen0, &inner_strides)?;
374 j0 += blen0;
375 if j0 < d0 {
376 for (o, s) in offsets.iter_mut().zip(strides.iter()) {
377 *o += (blen0 as isize) * s[0];
378 }
379 advanced = j0;
380 }
381 }
382 for (o, s) in offsets.iter_mut().zip(strides.iter()) {
383 *o -= (advanced as isize) * s[0];
384 }
385 Ok(())
386 }
387 };
388 ($name:ident, rank=$rank:literal,
393 block=[$($blk:literal),+], elem=[$($el:literal),+], top=$top:literal) => {
394 #[inline]
395 fn $name<F>(
396 dims: &[usize],
397 blocks: &[usize],
398 strides: &[&[isize]],
399 offsets: &mut [isize],
400 f: &mut F,
401 ) -> Result<()>
402 where
403 F: FnMut(&[isize], usize, &[isize]) -> Result<()>,
404 {
405 let inner_strides: OperandVec<isize> = strides.iter().map(|s| s[0]).collect();
406 let mut blens = [0usize; $rank];
407 block_loop!(dims, blocks, strides, offsets, f, blens, inner_strides;
408 elem=[$($el),+]; $($blk),+; top=$top);
409 Ok(())
410 }
411 };
412}
413
414make_kernel!(kernel_1d_inner, rank = 1);
415make_kernel!(
416 kernel_2d_inner,
417 rank = 2,
418 block = [1, 0],
419 elem = [1],
420 top = 1
421);
422make_kernel!(
423 kernel_3d_inner,
424 rank = 3,
425 block = [2, 1, 0],
426 elem = [2, 1],
427 top = 2
428);
429make_kernel!(
430 kernel_4d_inner,
431 rank = 4,
432 block = [3, 2, 1, 0],
433 elem = [3, 2, 1],
434 top = 3
435);
436make_kernel!(
437 kernel_5d_inner,
438 rank = 5,
439 block = [4, 3, 2, 1, 0],
440 elem = [4, 3, 2, 1],
441 top = 4
442);
443make_kernel!(
444 kernel_6d_inner,
445 rank = 6,
446 block = [5, 4, 3, 2, 1, 0],
447 elem = [5, 4, 3, 2, 1],
448 top = 5
449);
450make_kernel!(
451 kernel_7d_inner,
452 rank = 7,
453 block = [6, 5, 4, 3, 2, 1, 0],
454 elem = [6, 5, 4, 3, 2, 1],
455 top = 6
456);
457make_kernel!(
458 kernel_8d_inner,
459 rank = 8,
460 block = [7, 6, 5, 4, 3, 2, 1, 0],
461 elem = [7, 6, 5, 4, 3, 2, 1],
462 top = 7
463);
464
465#[inline]
470fn kernel_nd_inner_iterative<F>(
471 dims: &[usize],
472 blocks: &[usize],
473 strides: &[&[isize]],
474 offsets: &mut [isize],
475 f: &mut F,
476) -> Result<()>
477where
478 F: FnMut(&[isize], usize, &[isize]) -> Result<()>,
479{
480 let rank = dims.len();
481 debug_assert!(rank >= 9);
482
483 let d0 = dims[0];
484 let b0 = blocks[0].max(1).min(d0);
485 let inner_strides: OperandVec<isize> = strides.iter().map(|s| s[0]).collect();
486
487 let mut idx: Vec<usize> = vec![0usize; rank];
489
490 if dims.contains(&0) {
494 return Ok(());
495 }
496 loop {
497 let mut j0 = 0usize;
499 let mut advanced = 0usize;
500 while j0 < d0 {
501 let blen0 = b0.min(d0 - j0);
502 f(offsets, blen0, &inner_strides)?;
503 j0 += blen0;
504 if j0 < d0 {
505 for (offset, s) in offsets.iter_mut().zip(strides.iter()) {
506 *offset += (blen0 as isize) * s[0];
507 }
508 advanced = j0;
509 }
510 }
511 for (offset, s) in offsets.iter_mut().zip(strides.iter()) {
512 *offset -= (advanced as isize) * s[0];
513 }
514
515 let mut level = 1usize;
517 loop {
518 if idx[level] + 1 < dims[level] {
519 idx[level] += 1;
520 for (offset, s) in offsets.iter_mut().zip(strides.iter()) {
521 *offset += s[level];
522 }
523 break;
524 }
525
526 let last = (dims[level] - 1) as isize;
527 idx[level] = 0;
528 for (offset, s) in offsets.iter_mut().zip(strides.iter()) {
529 *offset -= last * s[level];
530 }
531 level += 1;
532 if level == rank {
533 return Ok(());
534 }
535 }
536 }
537}
538
539#[inline]
559pub(crate) fn for_each_inner_block_preordered<S: AsRef<[isize]>, F>(
560 dims: &[usize],
561 blocks: &[usize],
562 strides: &[S],
563 initial_offsets: &[isize],
564 mut f: F,
565) -> Result<()>
566where
567 F: FnMut(&[isize], usize, &[isize]) -> Result<()>,
568{
569 let refs: OperandVec<&[isize]> = strides.iter().map(|s| s.as_ref()).collect();
570 preordered_dyn(dims, blocks, &refs, initial_offsets, &mut f)
571}
572
573type BlockFn<'a> = &'a mut dyn FnMut(&[isize], usize, &[isize]) -> Result<()>;
574
575#[inline(never)]
576fn preordered_dyn(
577 dims: &[usize],
578 blocks: &[usize],
579 strides: &[&[isize]],
580 initial_offsets: &[isize],
581 mut f: BlockFn<'_>,
582) -> Result<()> {
583 let rank = dims.len();
584 if rank == 0 {
585 return f(initial_offsets, 1, &[]);
586 }
587
588 let mut offsets: OperandVec<isize> = initial_offsets.iter().copied().collect();
590
591 match rank {
592 1 => kernel_1d_inner(dims, blocks, strides, &mut offsets, &mut f),
593 2 => kernel_2d_inner(dims, blocks, strides, &mut offsets, &mut f),
594 3 => kernel_3d_inner(dims, blocks, strides, &mut offsets, &mut f),
595 4 => kernel_4d_inner(dims, blocks, strides, &mut offsets, &mut f),
596 5 => kernel_5d_inner(dims, blocks, strides, &mut offsets, &mut f),
597 6 => kernel_6d_inner(dims, blocks, strides, &mut offsets, &mut f),
598 7 => kernel_7d_inner(dims, blocks, strides, &mut offsets, &mut f),
599 8 => kernel_8d_inner(dims, blocks, strides, &mut offsets, &mut f),
600 _ => kernel_nd_inner_iterative(dims, blocks, strides, &mut offsets, &mut f),
601 }
602}
603
604pub fn ensure_same_shape(a: &[usize], b: &[usize]) -> Result<()> {
623 if a.len() != b.len() {
624 return Err(crate::StridedError::RankMismatch(a.len(), b.len()));
625 }
626 if a != b {
627 return Err(crate::StridedError::ShapeMismatch(a.to_vec(), b.to_vec()));
628 }
629 Ok(())
630}
631
632#[derive(Copy, Clone, Debug, Eq, PartialEq)]
633pub(crate) enum ContiguousLayout {
634 RowMajor,
636 ColMajor,
638}
639
640pub(crate) fn contiguous_layout(dims: &[usize], strides: &[isize]) -> Option<ContiguousLayout> {
646 if dims.len() != strides.len() {
647 return None;
648 }
649 if dims.is_empty() {
650 return Some(ContiguousLayout::RowMajor);
651 }
652
653 let mut expected = 1isize;
655 let mut row_ok = true;
656 for (&dim, &stride) in dims.iter().rev().zip(strides.iter().rev()) {
657 if dim <= 1 {
658 continue;
659 }
660 if stride != expected {
661 row_ok = false;
662 break;
663 }
664 expected = expected.saturating_mul(dim as isize);
665 }
666 if row_ok {
667 return Some(ContiguousLayout::RowMajor);
668 }
669
670 let mut expected = 1isize;
672 for (&dim, &stride) in dims.iter().zip(strides.iter()) {
673 if dim <= 1 {
674 continue;
675 }
676 if stride != expected {
677 return None;
678 }
679 expected = expected.saturating_mul(dim as isize);
680 }
681 Some(ContiguousLayout::ColMajor)
682}
683
684pub(crate) fn total_len(dims: &[usize]) -> Result<usize> {
692 if dims.contains(&0) {
693 return Ok(0);
694 }
695 dims.iter()
696 .try_fold(1usize, |acc, &dim| acc.checked_mul(dim))
697 .ok_or(StridedError::OffsetOverflow)
698}
699
700#[inline]
707pub(crate) fn use_sequential_fast_path(
708 class: crate::cost::KernelClass,
709 total: usize,
710 exec: &Exec<'_>,
711) -> bool {
712 !crate::threading::is_parallel(class, total, exec)
713}
714
715#[inline]
721pub(crate) fn same_contiguous_layout(
722 dims: &[usize],
723 strides_list: &[&[isize]],
724) -> Option<ContiguousLayout> {
725 let first = contiguous_layout(dims, strides_list.first()?)?;
726 for strides in &strides_list[1..] {
727 if contiguous_layout(dims, strides)? != first {
728 return None;
729 }
730 }
731 Some(first)
732}
733
734#[inline]
743pub(crate) fn sequential_contiguous_layout(
744 class: crate::cost::KernelClass,
745 dims: &[usize],
746 strides_list: &[&[isize]],
747 exec: &Exec<'_>,
748) -> Result<Option<ContiguousLayout>> {
749 if !use_sequential_fast_path(class, total_len(dims)?, exec) {
750 return Ok(None);
751 }
752 Ok(same_contiguous_layout(dims, strides_list))
753}
754
755#[cfg(test)]
756#[path = "kernel/tests/tests.rs"]
757mod tests;