Template Function sequant::canonical_operand_cmp

Function Documentation

template<typename TreeNode>
std::strong_ordering sequant::canonical_operand_cmp(TreeNode const &a, TreeNode const &b)

3-way comparison establishing the canonical order of a commutative (Product) node’s two operands.

A contraction is commutative, so the binarizer emits its two operands in whichever order the single-term DP’s contraction sequence yields, i.e. in the order in which the pair lands on the DP’s stack. The node id and the canonical connectivity graph both fold that choice, so the two spellings are one value; this comparison lets the equality comparator (and anything else deriving identity from the children) see them as one, by reading the children through canonical_children instead of through the emitted left/right. Nothing is reordered: the tree keeps the evaluation order the DP chose, because cost &#8212; peak in particular &#8212; is order dependent.

The order is a function of the operands’ values only, and is decided in O(1), reading nothing but the two nodes’ own already-computed data, never their subtrees:

  1. a scalar operand sorts after a non-scalar one, matching how binarize builds a scalar * tensor node (tensor left, Constant right) and keeping c * T and T * c one value;

  2. then ascending node id (hash::value, the operand-order-independent EvalExpr hash);

  3. operands agreeing on both are equivalent, and are read in the order in which they were emitted.

Case 3 is exactly right for the case that occurs: two operands that are one value have one node id, either order is canonical for them, and an ordered comparison of two swapped spellings succeeds whichever way each is read. The only other way to reach it is a genuine 64-bit hash collision between distinct values, and there the cost is a missed fold &#8212; the two spellings stay two cache entries &#8212; never a wrong fold, because TreeNodeEqualityComparator still compares both subtrees in full and rejects a mismatch. Resolving such a collision instead would mean comparing the operand subtrees here, and a full comparison per visit turns the comparator quadratic on nested hash-equal operands (a t2 * t2 self-contraction is enough): T(n) = 4 T(n/2). Keeping this O(1) is what makes the comparator provably linear.

Parameters:

  • a – one operand of a commutative node

  • b – the other operand of that node

Returns:

std::strong_ordering::less if a belongs first, std::strong_ordering::greater if b does, and std::strong_ordering::equal if the two are interchangeable (read them in the order in which they were emitted).