strided_basic/lib.rs
1#![doc = include_str!("../README.md")]
2
3//! Cache-optimized kernels for strided multidimensional array operations.
4//!
5//! This crate is a Rust port of Julia's [Strided.jl](https://github.com/Jutho/Strided.jl)
6//! and [StridedViews.jl](https://github.com/Jutho/StridedViews.jl) libraries, providing
7//! efficient operations on strided multidimensional array views.
8//!
9//! # Core Types
10//!
11//! - [`StridedView`] / [`StridedViewMut`]: Dynamic-rank strided views over existing data
12//! - [`StridedArray`]: Owned strided multidimensional array
13//! - [`ElementOp`] trait and implementations ([`Identity`], [`Conj`], [`Transpose`], [`Adjoint`]):
14//! Type-level element operations applied lazily on access
15//! - [`Exec`] / [`Pool`]: the placement token every fan-out entry takes as its
16//! last parameter (re-exported from `threadteam`)
17//!
18//! # Primary API (view-based, Julia-compatible)
19//!
20//! ## Map Operations
21//!
22//! - [`map_into`]: Apply a function element-wise from source to destination
23//! - [`zip_map2_into`], [`zip_map3_into`], [`zip_map4_into`]: Multi-array element-wise operations
24//!
25//! ## In-place Update Operations
26//!
27//! - [`map_update_into`], [`zip_update2_into`], [`zip_update3_into`]: `dest[i] = f(dest[i], inputs...)`,
28//! reading the old destination without a second view of it
29//!
30//! ## Reduce Operations
31//!
32//! - [`reduce`]: Full reduction with map function
33//! - [`zip_reduce`]: Two-input full reduction with a map function (the
34//! widening route, e.g. `f32` operands accumulated in `f64`)
35//! - [`reduce_axis`]: Reduce along a single axis
36//!
37//! A reduction that can fan out (`reduce`, `zip_reduce`, `sum`) gives a result
38//! that is independent of the token's budget only for a serial token; `dot`
39//! never enters a parallel branch, so its result does not depend on the token at
40//! all. See each entry's evaluation-order section.
41//!
42//! # Threading
43//!
44//! Every operation that can fan out takes `exec: Exec<'_>` by value as its last
45//! parameter. [`Exec::serial`] runs on the calling thread; a token minted from a
46//! [`Pool`] with [`Exec::new`] splits the work within its budget. Whether and how
47//! wide is decided by the token: the serial time of the region (elements times the
48//! throughput of its `execution::KernelClass`) against the dispatch cost of the
49//! sections it opens (`Exec::pays`, `Exec::width_for`), so a region too small to
50//! repay a fork stays on the calling thread whatever the budget. Without the
51//! `parallel` feature every token runs inline.
52//!
53//! ## Suffix Vocabulary
54//!
55//! Accumulation is `*_acc`, overwrite is `*_into`, and `*_view` returns metadata
56//! only; the table and the names still outside it are in `REPOSITORY_RULES.md`
57//! ("Suffix Vocabulary"). `*_into` never reads the previous `dest[i]`, except
58//! the update family ([`map_update_into`], [`zip_update2_into`],
59//! [`zip_update3_into`]), which updates `dest[i]` in place from its old value.
60//!
61//! ## Basic Operations
62//!
63//! - [`copy_into`]: Copy array contents
64//! - [`add_acc`], [`mul_acc`]: Accumulating element-wise arithmetic (`dest[i] += src[i]`,
65//! `dest[i] *= src[i]`)
66//! - [`axpy_acc`]: y = alpha*x + y (array version)
67//! - [`fma_acc`]: `dest[i] += a[i] * b[i]`
68//! - [`sum`], [`dot`]: Reductions
69//! - [`symmetrize_into`], [`symmetrize_conj_into`]: Matrix symmetrization
70//!
71//! ## Raw Strided Copies
72//!
73//! Over borrowed [`RawStridedRef`] / [`RawStridedMut`] layouts:
74//!
75//! - [`CopyPlan`], [`UpdatePlan`]: compile a layout pair once, replay it on
76//! exactly that layout
77//! - [`replay_copy_raw`], [`replay_map_raw`] and their `_uninit` forms: replay
78//! already-fused dims and strides as given, compiling nothing, serially or
79//! across the token's budget
80//! - [`copy_scale_raw`], [`axpy_raw`] and their `conj` forms: serial copies
81//! that fuse the layout on every call
82//!
83//! # Example
84//!
85//! ```rust
86//! use strided_basic::{StridedView, StridedViewMut, StridedArray, Identity, Exec, map_into};
87//!
88//! // Create a column-major array (Julia default)
89//! let src = StridedArray::<f64>::from_fn_col_major(&[2, 3], |idx| {
90//! (idx[0] * 10 + idx[1]) as f64
91//! });
92//! let mut dest = StridedArray::<f64>::col_major(&[2, 3]);
93//!
94//! // Map with view-based API
95//! map_into(&mut dest.view_mut(), &src.view(), |x| x * 2.0, Exec::serial()).unwrap();
96//! assert_eq!(dest.get(&[1, 2]), 24.0); // (1*10 + 2) * 2
97//! ```
98//!
99//! # Cache Optimization
100//!
101//! The library uses Julia's blocking strategy for cache efficiency:
102//! - Dimensions are sorted by stride magnitude for optimal memory access
103//! - Operations are blocked into tiles fitting L1 cache ([`BLOCK_MEMORY_SIZE`] = 32KB)
104//! - Contiguous arrays use fast paths bypassing the blocking machinery
105
106mod block;
107mod complex_div;
108mod copy_plan;
109mod cost;
110mod dense_update;
111mod erased;
112mod erased_common;
113pub mod execution;
114mod fuse;
115mod inline;
116mod kernel;
117mod layout_check;
118mod map_view;
119mod nan_select;
120mod ops_view;
121mod order;
122mod raw_ops;
123mod reduce_view;
124mod simd;
125mod threading;
126mod update_view;
127pub use complex_div::{robust_complex_divide_f32, robust_complex_divide_f64};
128pub use copy_plan::{CopyPlan, UpdatePlan};
129pub use dense_update::{
130 axpby_accum, embed_diagonal_into_uninit, embed_diagonal_view_into_uninit,
131 triangular_mask_into_uninit, triangular_mask_view_into_uninit,
132};
133pub use erased::{
134 ArgReduceOp, ErasedArgReducePlan, ErasedConcatenatePlan, ErasedCopyPlan, ErasedNormPlan,
135 ErasedReducePlan, ErasedScanPlan, ErasedUpdatePlan, NormKind, NormSpec, ReduceOp, ScanOp,
136 ScanOptions, UpdateOp,
137};
138pub use inline::{InlineVec, OperandVec, OPERAND_CAP};
139pub use map_view::{
140 broadcast_mul_into, broadcast_mul_into_uninit, compare_into, compare_into_uninit, map_into,
141 map_into_uninit_with_kernel, mul_into, mul_into_uninit, zip_map2_into, zip_map3_into,
142 zip_map4_into, Classed, CompareOp, MapFn,
143};
144pub use nan_select::{nan_propagating_maximum, nan_propagating_minimum};
145pub use ops_view::{
146 add_acc, axpy_acc, copy_conj_into, copy_into, copy_into_col_major, copy_into_uninit,
147 copy_scale_into, copy_transpose_scale_into, dot, fma_acc, mul_acc, sum, symmetrize_conj_into,
148 symmetrize_into,
149};
150pub use raw_ops::{
151 axpy_conj_raw, axpy_raw, copy_scale_conj_raw, copy_scale_raw, replay_copy_raw,
152 replay_copy_raw_uninit, replay_map_raw, replay_map_raw_uninit, RAW_FUSED_RANK_LIMIT,
153};
154pub use reduce_view::{reduce, reduce_axis, reduce_axis_into, zip_reduce};
155pub use simd::MaybeSimdOps;
156pub use strided_view::view;
157pub use strided_view::*;
158pub use threadteam::{Exec, Pool, PoolBuilder};
159pub use update_view::{map_update_into, zip_update2_into, zip_update3_into};
160/// Block memory size for cache-optimized iteration (L1 cache target).
161///
162/// Operations are blocked into tiles that fit within this size to maximize cache hits.
163/// Default: 32KB (typical L1 data cache size).
164pub const BLOCK_MEMORY_SIZE: usize = 32 * 1024;
165
166/// Cache line size in bytes.
167///
168/// Used for memory region calculations in block size computation.
169pub const CACHE_LINE_SIZE: usize = 64;
170
171mod gather_plan;
172mod outer_product;
173mod static_indexing_plan;
174pub use gather_plan::{
175 DynamicSlicePlan, DynamicUpdateSlicePlan, GatherIndex, GatherPlan, GatherSpec, ScatterPlan,
176 ScatterSpec,
177};
178pub use outer_product::{
179 batched_outer_product_into, batched_outer_product_into_uninit, plan_lazy_outer_product,
180 LazyOuterProductLayout,
181};
182pub use static_indexing_plan::{ConcatenatePlan, PadPlan, ReversePlan, SlicePlan};