AssociativeCommutativePatternMatching · benchmark

Four pattern matchers, one set of patterns

Summary

A case is matched when the matcher finds at least one match. All matches sums every match found (for rule2, which stops at the first, this is the number matched). Times are per call, measured warm: for the first match (what a rule uses: _match, _cmatch, SymbolicUtils' matcher returning its first bindings, and rule2) and for finding every match (collecting _eachmatch, _ceachmatch, and SymbolicUtils' matcher with a continuation that records each match and backtracks). rule2 finds only one match. The matchers find different numbers of matches, so the all-matches times do not measure the same work. Compare times only within this run.

What stands out

  1. No matcher returns a wrong match. Each match was substituted back into the pattern and the result compared numerically with the subject; all agree.
  2. Associativity is the largest difference. Only _eachmatch lets a slot take several terms: it matches ~x + ~y against a + b + c six ways (cases 18–22). The other three need the pattern and the subject to have the same number of arguments.
  3. Segments are enumerated, or not. For ~~x + ~~y against a + b + c, _eachmatch finds all 8 splits, while _ceachmatch and SymbolicUtils find one. rule2 allows a segment only as the sole argument (+(~~x)), and then binds the whole term rather than its arguments. SymbolicUtils does not accept ~~~y, and rule2 errors on it.
  4. The first match can differ, which is what a rule uses. For (~!a + ~!b*~x)^(~!m) against (1 + x)^4, both ACPM matchers first return a => x, b => 1, x => 1, which is valid, while SymbolicUtils and rule2 return a => 1, b => 1, x => x (case 54). In an integration rule, where ~x is bound to the variable beforehand, this does not arise. For ~!a * (~x)^(~!m) against 5x^2, _ceachmatch first returns a => x^2, m => 1, x => 5; _eachmatch keeps only matches using the fewest defaults (case 36). SymbolicUtils matches (~u)^(~m) against 1/sqrt(x) as u => sqrt(x), m => -1, and the others as u => x, m => -1//2 (case 45).
  5. The ACPM matchers also return role swaps. They also match the coefficient and the variable the other way round, e.g. a => x, x => 3 for ~!a * ~x against 3x (cases 14, 30, 32, 53). SymbolicUtils' enumeration does not, and rule2 stops at the first match.
  6. A quotient as a product. SymbolicUtils' @rule does not match (~u)^(~m) * ~v against a / b, or (~u)^(~m) * (~v)^(~n) against a^2 / b^3 (cases 50–51). The other three do, by reading the quotient as a * b^-1. All four read 1/x, sqrt(x) and exp(x) as powers.
  7. Guards that throw. Enumerating every match of ~a::isinteger * ~x against 3x makes SymbolicUtils call isinteger(x), which throws (case 40). A rule only uses the first match, a => 3, so this stays hidden. The ACPM matchers treat a guard that throws as false.
  8. Operation slots. rule2 does not match (~F)(~x) (cases 57–58); the others do.
  9. Speed. For a first match, rule2 takes µs at the median and SymbolicUtils µs. With its pattern compiled, the commutative matcher takes µs, the same as rule2. Without compiling, _cmatch takes µs, and _eachmatch µs. The slowest case for _eachmatch is the product of two binomial powers, case 55, at µs. Finding every match, the medians are µs for SymbolicUtils, µs compiled, µs for _ceachmatch and µs for _eachmatch. These are close to the first-match medians, as most cases have only one match. The difference shows where there are several: for ~x + ~y + ~z against a + b + c (six matches each), the times are 3.0 µs compiled, 6.9 µs for SymbolicUtils, 9.7 µs for _ceachmatch and 73 µs for _eachmatch. _cmatch stops at the first match, so it rarely reaches a guard that throws: ~a::isinteger * ~x takes µs, while _ceachmatch, finding every match, calls isinteger(x) and takes µs.
  10. Compiling a pattern. compile_pattern works out once what the commutative matcher would otherwise ask of the pattern at every call: which parts are slots, segments or defslots, what each guard is, which operations are commutative and in which order to try their arguments, and which forms of a power apply. The matching then takes the same steps, so the matches are the same, in the same order, on all 62 cases. Most of the time saved comes from not re-reading the pattern, from comparing operations by nameof instead of printing them, from binding a slot without the general match_dict, and from loops specialized on the type of the arguments. @rule compiles its pattern when the rule is made.
  11. Two bugs in _eachmatch were found and fixed in this comparison. On SymbolicUtils terms it threw on 7 of these cases: it compared terms with ==, which is not a Bool for SymbolicUtils, and indexed the arguments with a vector of positions, which SymbolicUtils' argument type does not support.

Cases

matches (count; distinct in parentheses if fewer) no match error times in matcher order; all matches omit rule2