Skip to content

A commutative pattern costs allocation on a hot rule set, because it cannot take the single-match path #1079

Description

@Rafael-SOWNet

MatchedRule.TryApply has two paths. A pattern that IsDeterministic is asked for a single
match and threads its bindings through without allocating; anything else is enumerated through
MatchPattern.Match, which is a chain of iterator state machines, one per pattern node.

MatchPattern.Commutative<T> is never deterministic — NodePattern.deterministic is
!commutative && children.All(...) — so a rule using one always takes the enumerating path,
even though a binary commutative node whose children are all deterministic has at most two
candidate matches
: the written order and the swapped one.

On a set that fires on a shape this is nothing. On a set that runs at every node of every pass
it is measurable. RewriteRules.Power as data, with two commutative rules replacing six
switch arms:

SolveMediumHard, allocated
master 165,054,016 B
two commutative rules 171,367,976 B (+3.8%)
the same six orientations as node patterns 166,534,536 B (+0.90%)

The kernel performance gate fails allocation at 3% in either direction, so the commutative form
was red — SolveHard +4.4% and SolveMediumHard +5.0% on the runner. It was shipped as six
node patterns instead (#1076), which say exactly the same thing and are proven to by the
agreement run, but are six rules where two would do.

What would fix it

A bounded-choice path between the two that exist. A commutative node with deterministic children
knows it has two candidates; a rule could ask for the nth match without an iterator:

internal virtual int AttemptCount => 1;
internal virtual bool TryMatchNth(Entity expr, Bindings bindings, int attempt, out Bindings result);

TryApply would loop attempt from 0 while AttemptCount is bounded, and fall back to
Match otherwise — so Gathered and anything genuinely open-ended is unaffected. Nested
commutative patterns multiply their counts, which is still bounded and still small.

This matters beyond the two sets above: it is the difference between "a rule set says the
mathematics once" and "a rule set writes out every orientation the way the switch it replaced
had to", which is most of what
#746 tier 1 is exchanging the
switch for.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions