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

    Fields

    No fields configured for issues without a type.

    Projects

    Status
    No status

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions