1use std::collections::{HashMap, HashSet};
2use std::fmt;
3use std::mem::{size_of, size_of_val};
4
5use omeco::{
6 CodeOptimizer, EinCode as OmecoEinCode, Initializer, NestedEinsum, ScoreFunction, TreeSA,
7};
8
9use crate::cache::{saturating_sum, vec_of_vec_retained_bytes, vec_retained_bytes};
10use crate::planning::plan::{compile_step_plans, DiagPlan, GemmPlan, ReducePlan, StepPlan};
11use crate::syntax::subscripts::Subscripts;
12use crate::util::{build_size_dict, intermediate_subs};
13use crate::{Error, Result};
14
15#[derive(Clone)]
17pub(crate) struct ContractionStep {
18 pub(crate) left: usize,
19 pub(crate) right: usize,
20}
21
22#[derive(Debug, Clone)]
38pub struct ContractionOptimizerOptions {
39 pub betas: Vec<f64>,
41 pub ntrials: usize,
43 pub niters: usize,
45 pub score: ScoreFunction,
47}
48
49impl Default for ContractionOptimizerOptions {
50 fn default() -> Self {
51 Self {
52 betas: Vec::new(),
53 ntrials: 1,
54 niters: 0,
55 score: ScoreFunction::default(),
56 }
57 }
58}
59
60impl ContractionOptimizerOptions {
61 fn to_treesa(&self) -> TreeSA {
62 TreeSA::new(
63 self.betas.clone(),
64 self.ntrials,
65 self.niters,
66 Initializer::Greedy,
67 self.score.clone(),
68 )
69 }
70
71 pub(crate) fn anneals(&self) -> bool {
73 self.niters > 0 && !self.betas.is_empty()
74 }
75
76 pub(crate) fn validate(&self) -> Result<()> {
77 if self.ntrials == 0 {
78 return Err(Error::planning(
79 "contraction optimizer ntrials must be at least 1",
80 ));
81 }
82 if self.betas.iter().any(|value| value.is_nan()) {
83 return Err(Error::planning(
84 "contraction optimizer betas must not contain NaN",
85 ));
86 }
87 if self.score.tc_weight.is_nan()
88 || self.score.sc_weight.is_nan()
89 || self.score.rw_weight.is_nan()
90 || self.score.sc_target.is_nan()
91 {
92 return Err(Error::planning(
93 "contraction optimizer score fields must not contain NaN",
94 ));
95 }
96 Ok(())
97 }
98}
99
100#[derive(Clone)]
112pub struct ContractionTree {
113 pub(crate) subscripts: Subscripts,
115 pub(crate) steps: Vec<ContractionStep>,
117 pub(crate) size_dict: HashMap<u32, usize>,
119 pub(crate) operand_subs: Vec<Vec<u32>>,
121 pub(crate) step_plans: Vec<StepPlan>,
123}
124
125impl fmt::Debug for ContractionTree {
126 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
127 f.debug_struct("ContractionTree")
128 .field("input_count", &self.subscripts.inputs.len())
129 .field("output_rank", &self.subscripts.output.len())
130 .field("steps_len", &self.steps.len())
131 .field("size_dict_len", &self.size_dict.len())
132 .field("operand_subs_len", &self.operand_subs.len())
133 .field("step_plans_len", &self.step_plans.len())
134 .finish_non_exhaustive()
135 }
136}
137
138impl ContractionTree {
139 pub fn optimize(subscripts: &Subscripts, shapes: &[&[usize]]) -> Result<Self> {
173 Self::optimize_with_options(subscripts, shapes, &ContractionOptimizerOptions::default())
174 }
175
176 pub fn optimize_with_options(
193 subscripts: &Subscripts,
194 shapes: &[&[usize]],
195 options: &ContractionOptimizerOptions,
196 ) -> Result<Self> {
197 options.validate()?;
198 let input_count = subscripts.inputs.len();
199 if input_count <= 1 {
200 return Self::from_pairs(subscripts, shapes, &[]);
201 }
202 if input_count == 2 {
203 return Self::from_pairs(subscripts, shapes, &[(0, 1)]);
204 }
205
206 let size_dict = build_size_dict(subscripts, shapes, None)?;
207 let pairs = if !options.anneals() {
211 optimize_self_greedy_pairs(subscripts, &size_dict)?
212 } else if let Some(omeco_pairs) = optimize_omeco_pairs(subscripts, &size_dict, options)? {
213 omeco_pairs
214 } else {
215 optimize_self_greedy_pairs(subscripts, &size_dict)?
216 };
217 Self::from_pairs(subscripts, shapes, &pairs)
218 }
219
220 pub fn from_pairs(
254 subscripts: &Subscripts,
255 shapes: &[&[usize]],
256 pairs: &[(usize, usize)],
257 ) -> Result<Self> {
258 let input_count = subscripts.inputs.len();
259 let required_steps = input_count.saturating_sub(1);
260 if pairs.len() != required_steps {
261 return Err(Error::planning(format!(
262 "explicit contraction path for {input_count} operands must have {required_steps} steps, got {}",
263 pairs.len()
264 )));
265 }
266 let size_dict = build_size_dict(subscripts, shapes, None)?;
267
268 let mut operand_subs: Vec<Vec<u32>> = subscripts.inputs.clone();
269 let mut live = vec![false; input_count + pairs.len()];
270 for slot in live.iter_mut().take(input_count) {
271 *slot = true;
272 }
273 let mut steps = Vec::new();
274
275 for (step_idx, &(left, right)) in pairs.iter().enumerate() {
276 let next_idx = input_count + step_idx;
277 if left == right {
278 return Err(Error::planning(format!(
279 "pair ({left}, {right}) must reference two distinct live operands"
280 )));
281 }
282 if left >= next_idx || right >= next_idx {
283 return Err(Error::planning(format!(
284 "pair ({left}, {right}) references non-existent operand"
285 )));
286 }
287 if !live[left] || !live[right] {
288 return Err(Error::planning(format!(
289 "pair ({left}, {right}) references an operand or intermediate that is no longer live"
290 )));
291 }
292
293 let mut needed: HashSet<u32> = subscripts.output.iter().copied().collect();
295 for (idx, subs) in operand_subs.iter().enumerate() {
296 if idx != left && idx != right && live[idx] {
297 needed.extend(subs.iter().copied());
298 }
299 }
300
301 let new_subs = intermediate_subs(&operand_subs[left], &operand_subs[right], &needed);
302 operand_subs.push(new_subs);
303 live[left] = false;
304 live[right] = false;
305 live[next_idx] = true;
306 steps.push(ContractionStep { left, right });
307 }
308
309 let live_count = live.iter().filter(|&&is_live| is_live).count();
310 if live_count != 1 {
311 return Err(Error::planning(format!(
312 "explicit contraction path must leave exactly one live result, got {live_count}"
313 )));
314 }
315
316 let mut tree = Self {
317 subscripts: subscripts.clone(),
318 steps,
319 size_dict,
320 operand_subs,
321 step_plans: Vec::new(),
322 };
323 tree.step_plans = compile_step_plans(&tree)?;
324 Ok(tree)
325 }
326
327 #[must_use]
344 pub fn step_count(&self) -> usize {
345 self.steps.len()
346 }
347
348 pub(crate) fn label_size(&self, label: u32) -> Option<usize> {
349 self.size_dict.get(&label).copied()
350 }
351
352 pub(crate) fn output_shape(&self) -> Vec<usize> {
353 self.subscripts
354 .output
355 .iter()
356 .filter_map(|label| self.label_size(*label))
357 .collect()
358 }
359
360 #[must_use]
380 pub fn step_pair(&self, step_idx: usize) -> Option<(usize, usize)> {
381 self.steps.get(step_idx).map(|step| (step.left, step.right))
382 }
383
384 #[must_use]
407 pub fn step_subscripts(&self, step_idx: usize) -> Option<(&[u32], &[u32], &[u32])> {
408 let input_count = self.subscripts.inputs.len();
409 let step = self.steps.get(step_idx)?;
410 let result_idx = input_count + step_idx;
411 let output_subs = if step_idx + 1 == self.steps.len() {
412 &self.subscripts.output
413 } else {
414 &self.operand_subs[result_idx]
415 };
416 Some((
417 &self.operand_subs[step.left],
418 &self.operand_subs[step.right],
419 output_subs,
420 ))
421 }
422
423 #[must_use]
436 pub fn step_plan(&self, step_idx: usize) -> Option<crate::lowering::PairwiseStepPlan<'_>> {
437 self.step_plans
438 .get(step_idx)
439 .map(crate::lowering::PairwiseStepPlan::new)
440 }
441
442 #[doc(hidden)]
443 #[must_use]
444 pub(crate) fn retained_bytes_for_cache_stats(&self) -> usize {
445 saturating_sum([
446 size_of::<Self>(),
447 subscripts_retained_bytes(&self.subscripts),
448 self.steps
449 .capacity()
450 .saturating_mul(size_of::<ContractionStep>()),
451 self.size_dict
452 .capacity()
453 .saturating_mul(size_of::<u32>().saturating_add(size_of::<usize>())),
454 vec_of_vec_retained_bytes(&self.operand_subs),
455 self.step_plans
456 .capacity()
457 .saturating_mul(size_of::<StepPlan>()),
458 saturating_sum(self.step_plans.iter().map(step_plan_retained_bytes)),
459 ])
460 }
461}
462
463fn subscripts_retained_bytes(subscripts: &Subscripts) -> usize {
464 saturating_sum([
465 vec_of_vec_retained_bytes(&subscripts.inputs),
466 vec_retained_bytes(&subscripts.output),
467 ])
468}
469
470fn reduce_plan_retained_bytes(plan: &ReducePlan) -> usize {
471 saturating_sum([
472 vec_retained_bytes(&plan.original_subs),
473 vec_retained_bytes(&plan.kept_subs),
474 vec_retained_bytes(&plan.out_shape),
475 ])
476}
477
478fn diag_plan_retained_bytes(plan: &DiagPlan) -> usize {
479 saturating_sum([
480 vec_retained_bytes(&plan.stages),
481 saturating_sum(plan.stages.iter().map(|stage| {
482 saturating_sum([
483 vec_retained_bytes(&stage.axis_pairs),
484 vec_retained_bytes(&stage.result_subs),
485 ])
486 })),
487 vec_retained_bytes(&plan.result_subs),
488 ])
489}
490
491fn gemm_plan_retained_bytes(plan: &GemmPlan) -> usize {
492 saturating_sum([
493 plan.reduce_a.as_ref().map_or(0, reduce_plan_retained_bytes),
494 plan.reduce_b.as_ref().map_or(0, reduce_plan_retained_bytes),
495 vec_retained_bytes(&plan.subs_a),
496 vec_retained_bytes(&plan.subs_b),
497 vec_retained_bytes(&plan.lo_modes),
498 vec_retained_bytes(&plan.ro_modes),
499 vec_retained_bytes(&plan.sum_modes),
500 vec_retained_bytes(&plan.lo_sizes),
501 vec_retained_bytes(&plan.ro_sizes),
502 vec_retained_bytes(&plan.sum_sizes),
503 vec_retained_bytes(&plan.batch_sizes),
504 vec_retained_bytes(&plan.target_a),
505 vec_retained_bytes(&plan.target_b),
506 vec_retained_bytes(&plan.c_gemm_shape),
507 vec_retained_bytes(&plan.expanded_shape),
508 vec_retained_bytes(&plan.canonical_modes),
509 vec_retained_bytes(&plan.a_gemm_shape),
510 vec_retained_bytes(&plan.b_gemm_shape),
511 ])
512}
513
514fn step_plan_retained_bytes(plan: &StepPlan) -> usize {
515 saturating_sum([
516 plan.diag_a.as_ref().map_or(0, diag_plan_retained_bytes),
517 plan.diag_b.as_ref().map_or(0, diag_plan_retained_bytes),
518 plan.strict_binary.as_ref().map_or(0, size_of_val),
519 gemm_plan_retained_bytes(&plan.gemm),
520 ])
521}
522
523fn optimize_omeco_pairs(
524 subscripts: &Subscripts,
525 size_dict: &HashMap<u32, usize>,
526 options: &ContractionOptimizerOptions,
527) -> Result<Option<Vec<(usize, usize)>>> {
528 #[cfg(test)]
529 tests::OMECO_CALLS.with(|count| count.set(count.get() + 1));
530 let code = OmecoEinCode::new(subscripts.inputs.clone(), subscripts.output.clone());
531 let optimizer = options.to_treesa();
532 let Some(nested) = optimizer.optimize(&code, size_dict) else {
533 return Ok(None);
534 };
535
536 let mut next_operand = subscripts.inputs.len();
537 let mut pairs = Vec::with_capacity(subscripts.inputs.len().saturating_sub(1));
538 nested_to_pairs(&nested, &mut next_operand, &mut pairs)?;
539 Ok(Some(pairs))
540}
541
542fn nested_to_pairs(
543 nested: &NestedEinsum<u32>,
544 next_operand: &mut usize,
545 pairs: &mut Vec<(usize, usize)>,
546) -> Result<usize> {
547 match nested {
548 NestedEinsum::Leaf { tensor_index } => Ok(*tensor_index),
549 NestedEinsum::Node { args, .. } => {
550 if args.len() != 2 {
551 return Err(Error::planning(format!(
552 "omeco returned non-binary contraction node with {} children",
553 args.len()
554 )));
555 }
556 let left = nested_to_pairs(&args[0], next_operand, pairs)?;
557 let right = nested_to_pairs(&args[1], next_operand, pairs)?;
558 pairs.push((left, right));
559 let result_idx = *next_operand;
560 *next_operand += 1;
561 Ok(result_idx)
562 }
563 }
564}
565
566fn build_operand_label_sets(operand_subs: &[Vec<u32>]) -> Vec<HashSet<u32>> {
567 operand_subs
568 .iter()
569 .map(|subs| subs.iter().copied().collect())
570 .collect()
571}
572
573fn build_needed_label_counts(
574 output_subs: &[u32],
575 available: &[usize],
576 operand_label_sets: &[HashSet<u32>],
577) -> HashMap<u32, usize> {
578 let mut counts = HashMap::new();
579 for &label in output_subs {
580 counts.entry(label).or_insert(1);
581 }
582 for &idx in available {
583 add_labels_to_counts(&mut counts, &operand_label_sets[idx]);
584 }
585 counts
586}
587
588fn add_labels_to_counts(counts: &mut HashMap<u32, usize>, labels: &HashSet<u32>) {
589 for &label in labels {
590 *counts.entry(label).or_insert(0) += 1;
591 }
592}
593
594fn remove_labels_from_counts(counts: &mut HashMap<u32, usize>, labels: &HashSet<u32>) {
595 for &label in labels {
596 match counts.get(&label).copied() {
597 Some(1) => {
598 counts.remove(&label);
599 }
600 Some(count) => {
601 counts.insert(label, count - 1);
602 }
603 None => {}
604 }
605 }
606}
607
608fn candidate_label_is_needed(
609 label: u32,
610 left: usize,
611 right: usize,
612 operand_label_sets: &[HashSet<u32>],
613 needed_label_counts: &HashMap<u32, usize>,
614) -> bool {
615 let mut selected_count = 0;
616 if operand_label_sets[left].contains(&label) {
617 selected_count += 1;
618 }
619 if operand_label_sets[right].contains(&label) {
620 selected_count += 1;
621 }
622 needed_label_counts.get(&label).copied().unwrap_or(0) > selected_count
623}
624
625fn collect_candidate_intermediate_subs(
626 subs_left: &[u32],
627 subs_right: &[u32],
628 left: usize,
629 right: usize,
630 operand_label_sets: &[HashSet<u32>],
631 needed_label_counts: &HashMap<u32, usize>,
632 output: &mut Vec<u32>,
633) {
634 output.clear();
635 for &label in subs_left.iter().chain(subs_right.iter()) {
636 if candidate_label_is_needed(label, left, right, operand_label_sets, needed_label_counts)
637 && !output.contains(&label)
638 {
639 output.push(label);
640 }
641 }
642}
643
644#[derive(Clone, Copy)]
645struct CandidateCostContext<'a> {
646 operand_label_sets: &'a [HashSet<u32>],
647 needed_label_counts: &'a HashMap<u32, usize>,
648 size_dict: &'a HashMap<u32, usize>,
649}
650
651fn candidate_contraction_cost(
652 subs_left: &[u32],
653 subs_right: &[u32],
654 left: usize,
655 right: usize,
656 context: CandidateCostContext<'_>,
657 candidate_subs: &mut Vec<u32>,
658) -> Result<usize> {
659 collect_candidate_intermediate_subs(
660 subs_left,
661 subs_right,
662 left,
663 right,
664 context.operand_label_sets,
665 context.needed_label_counts,
666 candidate_subs,
667 );
668 let mut cost = 1usize;
669 for &label in candidate_subs.iter() {
670 let size = context.size_dict.get(&label).copied().ok_or_else(|| {
671 Error::planning(format!(
672 "unknown size for label {label} in contraction cost"
673 ))
674 })?;
675 cost = cost.saturating_mul(size);
676 }
677 Ok(cost.max(1))
678}
679
680fn optimize_self_greedy_pairs(
699 subscripts: &Subscripts,
700 size_dict: &HashMap<u32, usize>,
701) -> Result<Vec<(usize, usize)>> {
702 use std::cmp::Reverse;
703 use std::collections::{BTreeMap, BTreeSet, BinaryHeap};
704
705 #[cfg(test)]
706 tests::SELF_GREEDY_CALLS.with(|count| count.set(count.get() + 1));
707 let input_count = subscripts.inputs.len();
708 let available: Vec<usize> = (0..input_count).collect();
709 let mut operand_subs: Vec<Vec<u32>> = subscripts.inputs.clone();
710 let mut operand_label_sets = build_operand_label_sets(&operand_subs);
711 let mut needed_label_counts =
712 build_needed_label_counts(&subscripts.output, &available, &operand_label_sets);
713 let mut live: BTreeSet<usize> = available.into_iter().collect();
714 let mut label_owners: BTreeMap<u32, BTreeSet<usize>> = BTreeMap::new();
715 for (operand, labels) in operand_label_sets.iter().enumerate() {
716 for &label in labels {
717 label_owners.entry(label).or_default().insert(operand);
718 }
719 }
720
721 let mut candidate_subs = Vec::new();
722 let mut heap: BinaryHeap<Reverse<(usize, usize, usize)>> = BinaryHeap::new();
723 let mut score = |left: usize,
724 right: usize,
725 operand_subs: &[Vec<u32>],
726 operand_label_sets: &[HashSet<u32>],
727 needed_label_counts: &HashMap<u32, usize>|
728 -> Result<Reverse<(usize, usize, usize)>> {
729 let cost = candidate_contraction_cost(
730 &operand_subs[left],
731 &operand_subs[right],
732 left,
733 right,
734 CandidateCostContext {
735 operand_label_sets,
736 needed_label_counts,
737 size_dict,
738 },
739 &mut candidate_subs,
740 )?;
741 Ok(Reverse((cost, left, right)))
742 };
743
744 let mut initial_pairs = BTreeSet::new();
745 for owners in label_owners.values() {
746 for &left in owners {
747 for &right in owners.range(left + 1..) {
748 initial_pairs.insert((left, right));
749 }
750 }
751 }
752 for (left, right) in initial_pairs {
753 heap.push(score(
754 left,
755 right,
756 &operand_subs,
757 &operand_label_sets,
758 &needed_label_counts,
759 )?);
760 }
761
762 let mut pairs: Vec<(usize, usize)> = Vec::with_capacity(input_count.saturating_sub(1));
763 while live.len() > 1 {
764 let mut chosen = None;
765 while let Some(Reverse((_, left, right))) = heap.pop() {
766 if live.contains(&left) && live.contains(&right) {
767 chosen = Some((left, right));
768 break;
769 }
770 }
771 let (left, right) = match chosen {
772 Some(pair) => pair,
773 None => {
774 let mut smallest = live.iter().copied();
775 match (smallest.next(), smallest.next()) {
776 (Some(left), Some(right)) => (left, right),
777 _ => break,
778 }
779 }
780 };
781 pairs.push((left, right));
782
783 let mut new_subs = Vec::new();
784 collect_candidate_intermediate_subs(
785 &operand_subs[left],
786 &operand_subs[right],
787 left,
788 right,
789 &operand_label_sets,
790 &needed_label_counts,
791 &mut new_subs,
792 );
793 let new_idx = operand_subs.len();
794 let new_label_set: HashSet<u32> = new_subs.iter().copied().collect();
795 remove_labels_from_counts(&mut needed_label_counts, &operand_label_sets[left]);
796 remove_labels_from_counts(&mut needed_label_counts, &operand_label_sets[right]);
797 add_labels_to_counts(&mut needed_label_counts, &new_label_set);
798 for operand in [left, right] {
799 for label in &operand_label_sets[operand] {
800 if let Some(owners) = label_owners.get_mut(label) {
801 owners.remove(&operand);
802 }
803 }
804 }
805 let mut neighbors = BTreeSet::new();
806 for &label in &new_subs {
807 let owners = label_owners.entry(label).or_default();
808 neighbors.extend(owners.iter().copied());
809 owners.insert(new_idx);
810 }
811 live.remove(&left);
812 live.remove(&right);
813 live.insert(new_idx);
814 operand_subs.push(new_subs);
815 operand_label_sets.push(new_label_set);
816 for neighbor in neighbors {
817 heap.push(score(
818 neighbor,
819 new_idx,
820 &operand_subs,
821 &operand_label_sets,
822 &needed_label_counts,
823 )?);
824 }
825 }
826
827 Ok(pairs)
828}
829
830#[cfg(test)]
831mod tests;