Skip to main content

tenferro_einsum/
optimize.rs

1use std::hash::Hasher;
2
3use omeco::ScoreFunction;
4
5use crate::{
6    ContractionOptimizerOptions, ContractionTree, Error, NestedEinsum, Result, Subscripts,
7};
8
9/// Controls how the contraction path is determined for N-ary einsum.
10///
11/// The traced API resolves this enum into a shape-independent plan
12/// specification and stores that specification in the einsum extension
13/// payload. Concrete traced inputs can resolve a [`ContractionTree`] while the
14/// op is built; symbolic traced inputs carry the plan specification until the
15/// extension runtime sees concrete execution shapes.
16///
17/// Planner options and explicit paths are part of the extension payload
18/// identity. Two otherwise identical traced einsum ops with different
19/// optimizer options, explicit paths, or fixed plan identities are not treated
20/// as the same extension op, and their compile/runtime plan cache entries are
21/// kept separate.
22///
23/// # Examples
24///
25/// ```
26/// use tenferro_einsum::{EinsumOptimize, EinsumOptions, TracedEinsumOps};
27/// use tenferro_runtime::TraceContext;
28///
29/// let trace = TraceContext::new();
30/// let lhs = trace.from_vec_col_major(vec![2, 3], vec![1.0_f64; 6]).unwrap();
31/// let rhs = trace.from_vec_col_major(vec![3, 2], vec![1.0_f64; 6]).unwrap();
32/// let out = trace
33///     .einsum_with(
34///         &[&lhs, &rhs],
35///         "ij,jk->ik",
36///         &EinsumOptions::default().optimize(EinsumOptimize::False),
37///     )
38///     .unwrap();
39///
40/// let graph = trace.finish(&[out.trace_value()]).unwrap();
41/// assert_eq!(
42///     graph.program().value_metadata(graph.program().outputs()[0]).unwrap().shape().len(),
43///     2,
44/// );
45/// ```
46#[derive(Clone, Debug)]
47pub enum EinsumOptimize {
48    /// Automatic optimization via omeco TreeSA.
49    Auto(ContractionOptimizerOptions),
50    /// No optimization: fold the operands left to right.
51    ///
52    /// Step 0 contracts inputs `0` and `1`; every later step contracts the running result with the
53    /// next input in written order, so the intermediate before step `k` is always the accumulated
54    /// contraction of inputs `0..=k`. The tree is resolved from the shapes at execution time, so
55    /// this policy is also usable with symbolic traced inputs.
56    ///
57    /// This is the predictable order, not a good one: [`Self::Auto`] usually finds a far cheaper
58    /// one. Use [`Self::Path`] when a specific order must be enforced.
59    False,
60    /// Parenthesized notation specifying contraction order.
61    Nested(NestedEinsum),
62    /// JAX-compatible position-based contraction path.
63    ///
64    /// Each pair references positions in a shrinking operand list. After each
65    /// contraction, the two operands are removed and the result is appended.
66    /// Because this representation is independent of concrete dimension
67    /// values, it can be used with symbolic traced inputs.
68    Path(Vec<(usize, usize)>),
69    /// Pre-computed contraction tree.
70    ///
71    /// A tree contains concrete shape-dependent planning results. It is
72    /// accepted when shapes are concrete, then converted into fixed contraction
73    /// pairs for the extension payload. A binary tree with the single pair
74    /// `(0, 1)` or `(1, 0)` may bypass the extension path and lower directly to
75    /// `dot_general`, including with symbolic traced inputs. Use
76    /// [`EinsumOptimize::Path`] instead when building a symbolic traced graph
77    /// for N-ary contraction.
78    Tree(ContractionTree),
79}
80
81impl Default for EinsumOptimize {
82    /// Default: time-optimized automatic planning.
83    fn default() -> Self {
84        Self::Auto(default_auto_options())
85    }
86}
87
88#[derive(Clone, Debug)]
89pub(crate) enum EinsumPlanSpec {
90    Auto(ContractionOptimizerOptions),
91    LeftToRight,
92    Path(Vec<(usize, usize)>),
93    FixedPairs(Vec<(usize, usize)>),
94}
95
96/// Return the default automatic optimizer options.
97#[must_use]
98pub(crate) fn default_auto_options() -> ContractionOptimizerOptions {
99    ContractionOptimizerOptions {
100        score: ScoreFunction::time_optimized(),
101        ..Default::default()
102    }
103}
104
105pub(crate) fn plan_spec_from_optimize(
106    optimize: EinsumOptimize,
107    subscripts: &Subscripts,
108) -> Result<EinsumPlanSpec> {
109    match optimize {
110        EinsumOptimize::Auto(options) => {
111            options.validate()?;
112            Ok(EinsumPlanSpec::Auto(options))
113        }
114        EinsumOptimize::False => Ok(EinsumPlanSpec::LeftToRight),
115        EinsumOptimize::Nested(nested) => {
116            let pairs = nested_to_v1_pairs(&nested, subscripts.inputs.len())?;
117            validate_fixed_pairs(&pairs, subscripts.inputs.len())?;
118            Ok(EinsumPlanSpec::FixedPairs(pairs))
119        }
120        EinsumOptimize::Path(path) => {
121            let _ = jax_path_to_v1_pairs(&path, subscripts.inputs.len())?;
122            Ok(EinsumPlanSpec::Path(path))
123        }
124        EinsumOptimize::Tree(_) => Err(Error::planning(
125            "precomputed contraction tree requires concrete input shapes; use Path or parenthesized notation for symbolic traced einsum",
126        )),
127    }
128}
129
130pub(crate) fn resolve_einsum_strategy_with_spec(
131    optimize: EinsumOptimize,
132    subscripts: &Subscripts,
133    shapes: &[&[usize]],
134) -> Result<(EinsumPlanSpec, ContractionTree)> {
135    match optimize {
136        EinsumOptimize::Tree(tree) => {
137            let pairs = tree_pairs(&tree);
138            let spec = EinsumPlanSpec::FixedPairs(pairs);
139            let tree = resolve_plan_spec(&spec, subscripts, shapes)?;
140            Ok((spec, tree))
141        }
142        optimize => {
143            let spec = plan_spec_from_optimize(optimize, subscripts)?;
144            let tree = resolve_plan_spec(&spec, subscripts, shapes)?;
145            Ok((spec, tree))
146        }
147    }
148}
149
150pub(crate) fn resolve_plan_spec(
151    spec: &EinsumPlanSpec,
152    subscripts: &Subscripts,
153    shapes: &[&[usize]],
154) -> Result<ContractionTree> {
155    match spec {
156        EinsumPlanSpec::Auto(options) => {
157            ContractionTree::optimize_with_options(subscripts, shapes, options)
158        }
159        EinsumPlanSpec::LeftToRight => {
160            // Fold left: step 0 contracts inputs `0` and `1`; step `k` contracts the running result
161            // (`n + k - 1`) with input `k + 1`. Not the `(0, 1)`-repeated JAX path resolved through
162            // `jax_path_to_v1_pairs`: that resolver appends a result instead of keeping it at the
163            // front, which contracts pairs of untouched inputs and can build an outer product.
164            let n = subscripts.inputs.len();
165            let pairs: Vec<(usize, usize)> = (0..n.saturating_sub(1))
166                .map(|step| {
167                    if step == 0 {
168                        (0, 1)
169                    } else {
170                        (step + 1, n + step - 1)
171                    }
172                })
173                .collect();
174            ContractionTree::from_pairs(subscripts, shapes, &pairs)
175        }
176        EinsumPlanSpec::Path(path) => {
177            let pairs = jax_path_to_v1_pairs(path, subscripts.inputs.len())?;
178            ContractionTree::from_pairs(subscripts, shapes, &pairs)
179        }
180        EinsumPlanSpec::FixedPairs(pairs) => ContractionTree::from_pairs(subscripts, shapes, pairs),
181    }
182}
183
184pub(crate) fn hash_einsum_plan_spec(spec: &EinsumPlanSpec, state: &mut dyn Hasher) {
185    match spec {
186        EinsumPlanSpec::Auto(options) => {
187            state.write_u8(0);
188            hash_optimizer_options(options, state);
189        }
190        EinsumPlanSpec::LeftToRight => state.write_u8(1),
191        EinsumPlanSpec::Path(path) => {
192            state.write_u8(2);
193            hash_pairs(path, state);
194        }
195        EinsumPlanSpec::FixedPairs(pairs) => {
196            state.write_u8(3);
197            hash_pairs(pairs, state);
198        }
199    }
200}
201
202pub(crate) fn plan_specs_equal(lhs: &EinsumPlanSpec, rhs: &EinsumPlanSpec) -> bool {
203    match (lhs, rhs) {
204        (EinsumPlanSpec::Auto(lhs), EinsumPlanSpec::Auto(rhs)) => {
205            optimizer_options_equal_by_bits(lhs, rhs)
206        }
207        (EinsumPlanSpec::LeftToRight, EinsumPlanSpec::LeftToRight) => true,
208        (EinsumPlanSpec::Path(lhs), EinsumPlanSpec::Path(rhs)) => lhs == rhs,
209        (EinsumPlanSpec::FixedPairs(lhs), EinsumPlanSpec::FixedPairs(rhs)) => lhs == rhs,
210        _ => false,
211    }
212}
213
214fn tree_pairs(tree: &ContractionTree) -> Vec<(usize, usize)> {
215    (0..tree.step_count())
216        .filter_map(|step| tree.step_pair(step))
217        .collect()
218}
219
220fn validate_fixed_pairs(pairs: &[(usize, usize)], input_count: usize) -> Result<()> {
221    let required_steps = input_count.saturating_sub(1);
222    if pairs.len() != required_steps {
223        return Err(Error::planning(format!(
224            "explicit contraction path for {input_count} operands must have {required_steps} steps, got {}",
225            pairs.len()
226        )));
227    }
228
229    let mut live = vec![false; input_count + pairs.len()];
230    for slot in live.iter_mut().take(input_count) {
231        *slot = true;
232    }
233
234    for (step_idx, &(left, right)) in pairs.iter().enumerate() {
235        let next_idx = input_count + step_idx;
236        if left == right {
237            return Err(Error::planning(format!(
238                "pair ({left}, {right}) must reference two distinct live operands"
239            )));
240        }
241        if left >= next_idx || right >= next_idx {
242            return Err(Error::planning(format!(
243                "pair ({left}, {right}) references non-existent operand"
244            )));
245        }
246        if !live[left] || !live[right] {
247            return Err(Error::planning(format!(
248                "pair ({left}, {right}) references an operand or intermediate that is no longer live"
249            )));
250        }
251
252        live[left] = false;
253        live[right] = false;
254        live[next_idx] = true;
255    }
256
257    let live_count = live.iter().filter(|&&is_live| is_live).count();
258    if live_count != 1 {
259        return Err(Error::planning(format!(
260            "explicit contraction path must leave exactly one live result, got {live_count}"
261        )));
262    }
263
264    Ok(())
265}
266
267fn hash_pairs(pairs: &[(usize, usize)], state: &mut dyn Hasher) {
268    state.write_usize(pairs.len());
269    for &(left, right) in pairs {
270        state.write_usize(left);
271        state.write_usize(right);
272    }
273}
274
275fn hash_optimizer_options(options: &ContractionOptimizerOptions, state: &mut dyn Hasher) {
276    state.write_usize(options.ntrials);
277    state.write_usize(options.niters);
278    state.write_usize(options.betas.len());
279    for value in &options.betas {
280        state.write_u64(value.to_bits());
281    }
282    state.write_u64(options.score.tc_weight.to_bits());
283    state.write_u64(options.score.sc_weight.to_bits());
284    state.write_u64(options.score.rw_weight.to_bits());
285    state.write_u64(options.score.sc_target.to_bits());
286}
287
288fn optimizer_options_equal_by_bits(
289    lhs: &ContractionOptimizerOptions,
290    rhs: &ContractionOptimizerOptions,
291) -> bool {
292    lhs.ntrials == rhs.ntrials
293        && lhs.niters == rhs.niters
294        && f64_slices_equal_by_bits(&lhs.betas, &rhs.betas)
295        && score_functions_equal_by_bits(&lhs.score, &rhs.score)
296}
297
298/// Convert JAX-style position-based path to fixed-ID pairs.
299///
300/// JAX format: each pair `(i, j)` refers to positions in a shrinking list.
301/// After contraction, the two operands are removed and the result is appended.
302/// Fixed-ID format keeps original operands at `0..input_count` and gives
303/// intermediate at step `k` the ID `input_count + k`.
304///
305/// # Errors
306///
307/// Returns an error if a path step references the same position twice or a
308/// position outside the current shrinking list.
309pub(crate) fn jax_path_to_v1_pairs(
310    jax_path: &[(usize, usize)],
311    input_count: usize,
312) -> Result<Vec<(usize, usize)>> {
313    let required_steps = input_count.saturating_sub(1);
314    if jax_path.len() != required_steps {
315        return Err(Error::planning(format!(
316            "explicit contraction path for {input_count} operands must have {required_steps} steps, got {}",
317            jax_path.len()
318        )));
319    }
320
321    let mut positions: Vec<usize> = (0..input_count).collect();
322    let mut v1_pairs = Vec::with_capacity(jax_path.len());
323
324    for (step, &(pos_a, pos_b)) in jax_path.iter().enumerate() {
325        if pos_a == pos_b {
326            return Err(Error::planning(format!(
327                "path step {step} references the same operand position twice: {pos_a}"
328            )));
329        }
330        let current_len = positions.len();
331        if pos_a >= current_len || pos_b >= current_len {
332            return Err(Error::planning(format!(
333                "path step {step} references operand positions ({pos_a}, {pos_b}) with only {current_len} live operands"
334            )));
335        }
336
337        let (lo, hi) = if pos_a < pos_b {
338            (pos_a, pos_b)
339        } else {
340            (pos_b, pos_a)
341        };
342        let id_a = positions[lo];
343        let id_b = positions[hi];
344        v1_pairs.push((id_a, id_b));
345
346        positions.remove(hi);
347        positions.remove(lo);
348        positions.push(input_count + step);
349    }
350
351    Ok(v1_pairs)
352}
353
354/// Convert a [`NestedEinsum`] tree into fixed-ID pairs.
355///
356/// # Errors
357///
358/// Returns an error if a leaf references an input outside `0..input_count` or if
359/// a node has no children.
360pub(crate) fn nested_to_v1_pairs(
361    nested: &NestedEinsum,
362    input_count: usize,
363) -> Result<Vec<(usize, usize)>> {
364    let mut pairs = Vec::with_capacity(input_count.saturating_sub(1));
365    let mut next_id = input_count;
366    let root_id = walk_nested(nested, input_count, &mut pairs, &mut next_id)?;
367    if input_count == 0 || root_id >= next_id {
368        return Err(Error::planning(
369            "nested einsum did not produce a valid root operand",
370        ));
371    }
372    Ok(pairs)
373}
374
375fn walk_nested(
376    nested: &NestedEinsum,
377    input_count: usize,
378    pairs: &mut Vec<(usize, usize)>,
379    next_id: &mut usize,
380) -> Result<usize> {
381    match nested {
382        NestedEinsum::Leaf(idx) => {
383            if *idx >= input_count {
384                return Err(Error::planning(format!(
385                    "nested einsum leaf {idx} is outside 0..{input_count}"
386                )));
387            }
388            Ok(*idx)
389        }
390        NestedEinsum::Node { children, .. } => {
391            let Some(first) = children.first() else {
392                return Err(Error::planning(
393                    "nested einsum node must have at least one child",
394                ));
395            };
396            let mut result_id = walk_nested(first, input_count, pairs, next_id)?;
397            for child in &children[1..] {
398                let child_id = walk_nested(child, input_count, pairs, next_id)?;
399                pairs.push((result_id, child_id));
400                result_id = *next_id;
401                *next_id += 1;
402            }
403            Ok(result_id)
404        }
405    }
406}
407
408fn f64_slices_equal_by_bits(lhs: &[f64], rhs: &[f64]) -> bool {
409    lhs.len() == rhs.len()
410        && lhs
411            .iter()
412            .zip(rhs)
413            .all(|(lhs, rhs)| lhs.to_bits() == rhs.to_bits())
414}
415
416fn score_functions_equal_by_bits(lhs: &ScoreFunction, rhs: &ScoreFunction) -> bool {
417    lhs.tc_weight.to_bits() == rhs.tc_weight.to_bits()
418        && lhs.sc_weight.to_bits() == rhs.sc_weight.to_bits()
419        && lhs.rw_weight.to_bits() == rhs.rw_weight.to_bits()
420        && lhs.sc_target.to_bits() == rhs.sc_target.to_bits()
421}
422
423#[cfg(test)]
424mod tests;