Skip to content

Rewire redundancy analysis to growth dominance; delete bespoke polynomial machinery #1081

Description

@isPANN

Background

src/rules/analysis.rs detects redundant reduction rules: a direct edge is redundant if some composite path dominates it on every size field. To compare overheads it carries its own ~200-line polynomial machinery (Monomial, NormalizedPoly, normalize_polynomial, poly_leq, monomial_dominated_by, prepare_expr_for_comparison) — a third, independent expansion-and-compare implementation, which rejects exp/log/sqrt outright and returns Unknown for anything with negative coefficients. The growth domain (#1075) now provides one trusted dominance order used by Big-O rendering (#1078); redundancy analysis should use the same one — one comparison semantics everywhere, and another few hundred lines of bespoke machinery deleted.

Full design (shared overview for this batch): docs/design/symbolic-growth-domain.md, section M3 (former feature F5).

Objective

Rewire compare_overhead to growth dominance and delete the bespoke polynomial machinery from analysis.rs. find_dominated_rules's semantics are unchanged. Close #15's sibling loose end in this file (the canonical_form call already stubbed by #1078).

Interface (Input → Output)

  • pub fn compare_overhead(primitive: &ReductionOverhead, composite: &ReductionOverhead) -> ComparisonStatus — signature and the ComparisonStatus enum unchanged. Per common field: Dominated iff the composite's growth is dominated-or-equal by the primitive's on every common field (composite ≤ primitive); NotDominated if worse on any field; Unknown only when a field's growth is Growth::Unknown.
  • Deleted: Monomial, NormalizedPoly, normalize_polynomial, poly_leq, monomial_dominated_by, prepare_expr_for_comparison.

Technical recommendations (non-binding)

  • Fields present in one overhead but not the other keep today's skip semantics — don't change the common-field logic, only the per-field comparison.
  • New capability for free: the one log-carrying overhead and subtraction-carrying overheads become comparable (the old machinery returned Unknown or errored on them); expect the dominated-rule report to gain decisions, not lose them.

Verification

  1. cargo test analysis green, with unit tests updated to the new semantics; at least one existing Unknown case that involved log or subtraction now yields a decided status (Dominated/NotDominated) — assert the specific pair and status in a test.
  2. Run the redundancy sanity check (cargo run --example detect_redundant_rules if present, otherwise the topology-sanity-check redundancy skill path) before and after the change: every rule reported as dominated before is still reported as dominated after (no lost detections); newly decided pairs are listed in the PR description with a one-line justification each.
  3. grep -n "NormalizedPoly\|normalize_polynomial\|poly_leq" src/rules/analysis.rs returns nothing and check 1–2 pass — proving the machinery was replaced, not renamed.

Negative control: a unit test where the composite is strictly worse on one common field (e.g. primitive num_vertices = n^2 vs composite num_vertices = n^3, all other fields equal) asserts NotDominated — a comparison rewire that accidentally inverts the direction or ignores a field fails it.

Dependencies

Depends on #1075 and #1078. Milestone: Symbolic Growth Domain & Pareto Search. When this lands, close #15 with a comment linking docs/design/symbolic-growth-domain.md (the asymptotic-search half of #15 is closed by the Pareto-front issue).

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    Status
    No status

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions