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.
MatchedRule.TryApplyhas two paths. A pattern thatIsDeterministicis asked for a singlematch 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.deterministicis!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.Poweras data, with two commutative rules replacing sixswitcharms:SolveMediumHard, allocatedThe kernel performance gate fails allocation at 3% in either direction, so the commutative form
was red —
SolveHard+4.4% andSolveMediumHard+5.0% on the runner. It was shipped as sixnode 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:
TryApplywould loopattemptfrom 0 whileAttemptCountis bounded, and fall back toMatchotherwise — soGatheredand anything genuinely open-ended is unaffected. Nestedcommutative 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
switchit replacedhad to", which is most of what
#746 tier 1 is exchanging the
switchfor.