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//! - [`replay_map_raw_fused`] and [`replay_map_raw_uninit_fused`]: the same
81//! replay, but fuse the pair inside the call for callers that hold unfused
82//! axes
83//! - [`replay_map_raw_serial`]: the serial replay of [`replay_map_raw`] for an
84//! `FnMut` and for elements that are not `Send + Sync`
85//! - [`copy_scale_raw`], [`axpy_raw`] and their `conj` forms: serial copies
86//! that fuse the layout on every call
87//!
88//! # Example
89//!
90//! ```rust
91//! use strided_basic::{StridedView, StridedViewMut, StridedArray, Identity, Exec, map_into};
92//!
93//! // Create a column-major array (Julia default)
94//! let src = StridedArray::<f64>::from_fn_col_major(&[2, 3], |idx| {
95//! (idx[0] * 10 + idx[1]) as f64
96//! });
97//! let mut dest = StridedArray::<f64>::col_major(&[2, 3]);
98//!
99//! // Map with view-based API
100//! map_into(&mut dest.view_mut(), &src.view(), |x| x * 2.0, Exec::serial()).unwrap();
101//! assert_eq!(dest.get(&[1, 2]), 24.0); // (1*10 + 2) * 2
102//! ```
103//!
104//! # Cache Optimization
105//!
106//! The library uses Julia's blocking strategy for cache efficiency:
107//! - Dimensions are sorted by stride magnitude for optimal memory access
108//! - Operations are blocked into tiles fitting L1 cache ([`BLOCK_MEMORY_SIZE`] = 32KB)
109//! - Contiguous arrays use fast paths bypassing the blocking machinery
110
111mod block;
112mod complex_div;
113mod copy_plan;
114mod cost;
115mod dense_update;
116mod erased;
117mod erased_common;
118pub mod execution;
119mod fuse;
120mod inline;
121mod kernel;
122mod layout_check;
123mod map_view;
124mod nan_select;
125mod ops_view;
126mod order;
127mod raw_ops;
128mod reduce_view;
129mod simd;
130mod threading;
131mod update_view;
132pub use complex_div::{robust_complex_divide_f32, robust_complex_divide_f64};
133pub use copy_plan::{CopyPlan, UpdatePlan};
134pub use dense_update::{
135 axpby_accum, embed_diagonal_into_uninit, embed_diagonal_view_into_uninit,
136 triangular_mask_into_uninit, triangular_mask_view_into_uninit,
137};
138pub use erased::{
139 ArgReduceOp, ErasedArgReducePlan, ErasedConcatenatePlan, ErasedCopyPlan, ErasedNormPlan,
140 ErasedReducePlan, ErasedScanPlan, ErasedUpdatePlan, NormKind, NormSpec, ReduceOp, ScanOp,
141 ScanOptions, UpdateOp,
142};
143pub use inline::{InlineVec, OperandVec, OPERAND_CAP};
144pub use map_view::{
145 broadcast_mul_into, broadcast_mul_into_uninit, compare_into, compare_into_uninit, map_into,
146 map_into_uninit_with_kernel, mul_into, mul_into_uninit, zip_map2_into, zip_map3_into,
147 zip_map4_into, Classed, CompareOp, MapFn,
148};
149pub use nan_select::{nan_propagating_maximum, nan_propagating_minimum};
150pub use ops_view::{
151 add_acc, axpy_acc, copy_conj_into, copy_into, copy_into_col_major, copy_into_uninit,
152 copy_scale_into, copy_transpose_scale_into, dot, fma_acc, mul_acc, sum, symmetrize_conj_into,
153 symmetrize_into,
154};
155pub use raw_ops::{
156 axpy_conj_raw, axpy_raw, copy_scale_conj_raw, copy_scale_raw, replay_copy_raw,
157 replay_copy_raw_uninit, replay_map_raw, replay_map_raw_fused, replay_map_raw_serial,
158 replay_map_raw_uninit, replay_map_raw_uninit_fused, RAW_FUSED_RANK_LIMIT,
159};
160pub use reduce_view::{reduce, reduce_axis, reduce_axis_into, zip_reduce};
161pub use simd::MaybeSimdOps;
162pub use strided_view::view;
163pub use strided_view::*;
164pub use threadteam::{Exec, Pool, PoolBuilder};
165pub use update_view::{map_update_into, zip_update2_into, zip_update3_into};
166/// Block memory size for cache-optimized iteration (L1 cache target).
167///
168/// Operations are blocked into tiles that fit within this size to maximize cache hits.
169/// Default: 32KB (typical L1 data cache size).
170pub const BLOCK_MEMORY_SIZE: usize = 32 * 1024;
171
172/// Cache line size in bytes.
173///
174/// Used for memory region calculations in block size computation.
175pub const CACHE_LINE_SIZE: usize = 64;
176
177/// Associativity of the L1 data cache the tiles target.
178///
179/// With [`BLOCK_MEMORY_SIZE`] it fixes the way size, `BLOCK_MEMORY_SIZE /
180/// L1_WAYS` = 4 KiB: addresses that differ by a multiple of it fall in the same
181/// set, and a set holds at most `L1_WAYS` lines. 32 KiB 8-way (Zen 1-4,
182/// Skylake) and 48 KiB 12-way (Ice Lake and later, Zen 5) L1d caches share the
183/// 4 KiB way, and 8 is the smaller associativity, so the bound stays safe on
184/// both. See `block::fit_l1_sets` (#287).
185pub(crate) const L1_WAYS: usize = 8;
186
187/// Lines a tile may keep live in one L1 set: [`L1_WAYS`] less a quarter of
188/// them (6 of 8).
189///
190/// The quarter is headroom, not geometry: the replacement policy of these
191/// caches is a pseudo-LRU that does not always evict the oldest line, and the
192/// L1 stride prefetcher of a strided operand pulls its next lines into the
193/// same set, so a set filled to exactly its ways still evicts lines before
194/// they are reused. The value was calibrated on the #287 diagnostic; the
195/// measurement is in `docs/worklogs/2026-11-10-issue-287-l1-set-tiles.md`.
196pub(crate) const L1_LIVE_LINES_PER_SET: usize = L1_WAYS - L1_WAYS / 4;
197
198/// Measurement hooks for benchmarks only; compiled out of every other build.
199#[cfg(feature = "bench-hooks")]
200pub mod bench_hooks {
201 use core::sync::atomic::AtomicBool;
202
203 /// Whether [`crate::block::declines_tiles`] may decline the tiles
204 /// ([#428]). Clearing it times the model's tiles against the flat walk in
205 /// one process; see `benches/view_decline_428.rs`.
206 ///
207 /// [#428]: https://github.com/tensor4all/strided-rs/issues/428
208 pub static DECLINE_TILES: AtomicBool = AtomicBool::new(true);
209
210 /// The per-set line budget `block::fit_l1_sets` enforces ([#287]); `0`
211 /// turns the step off. Storing `0` and the default alternately
212 /// times the model's tiles against the fitted ones in one process; see
213 /// `benches/block_l1_sets_287.rs`.
214 ///
215 /// [#287]: https://github.com/tensor4all/strided-rs/issues/287
216 pub static L1_SET_BUDGET: core::sync::atomic::AtomicUsize =
217 core::sync::atomic::AtomicUsize::new(crate::L1_LIVE_LINES_PER_SET);
218
219 /// Tiles the pointwise planner uses instead of its own when non-empty and
220 /// of the fused rank: a diagnostic to time an arbitrary tile through the
221 /// production walk ([#287]).
222 ///
223 /// [#287]: https://github.com/tensor4all/strided-rs/issues/287
224 pub static FORCED_TILES: std::sync::Mutex<Vec<usize>> = std::sync::Mutex::new(Vec::new());
225
226 /// The tiles the raw pair replay picks for `dims` as given (no fusion or
227 /// reordering; extent-1 axes are dropped, as the model drops them), or
228 /// `None` for its column-major walk. The extents must have a checked,
229 /// nonzero product.
230 pub fn pair_blocks<T>(dims: &[usize], dst: &[isize], src: &[isize]) -> Option<Vec<usize>> {
231 crate::raw_ops::with_given_route::<T, T, _>(dims, dst, src, |route| {
232 route.blocks().map(<[usize]>::to_vec)
233 })
234 }
235
236 /// The fused dims and block vector the pointwise planner hands a kernel
237 /// whose destination is operand `dest`, for the bench's report.
238 pub fn pointwise_blocks(
239 dims: &[usize],
240 strides_list: &[&[isize]],
241 elem_sizes: &[usize],
242 dest: usize,
243 ) -> (Vec<usize>, Vec<usize>) {
244 let (dims, _, plan) =
245 crate::kernel::build_plan_fused(dims, strides_list, Some(dest), elem_sizes);
246 (dims.as_slice().to_vec(), plan.block.as_slice().to_vec())
247 }
248
249 /// The view path's block vector for axes that are already in iteration
250 /// order, i.e. the decision the bench toggles above.
251 pub fn planned_blocks(
252 dims: &[usize],
253 strides_list: &[&[isize]],
254 elem_sizes: &[usize],
255 ) -> Vec<usize> {
256 crate::block::compute_block_sizes(dims, strides_list, elem_sizes)
257 .as_slice()
258 .to_vec()
259 }
260}
261
262mod gather_plan;
263mod outer_product;
264mod run_sum;
265mod static_indexing_plan;
266pub use gather_plan::{
267 DynamicSlicePlan, DynamicUpdateSlicePlan, GatherIndex, GatherPlan, GatherSpec, ScatterPlan,
268 ScatterSpec,
269};
270pub use outer_product::{
271 batched_outer_product_into, batched_outer_product_into_uninit, plan_lazy_outer_product,
272 LazyOuterProductLayout,
273};
274pub use run_sum::{RunIndex, RunSumPlan};
275pub use static_indexing_plan::{ConcatenatePlan, PadPlan, ReversePlan, SlicePlan};