The rule application timing instrumentation from #798 (implemented in #799) immediately surfaced a hotspot. Running Resyntax on a large file from the DrRacket codebase (drracket-test/tests/drracket/syncheck-test.rkt, ~2150 lines) spent ~7.5 seconds total checking 179 rules, and the four syntax-tree-based flattening rules account for 51% of that time:
| Rule | Total time |
|---|
nested-and-to-flat-and | 1009 ms |
nested-or/c-to-flat-or/c | 946 ms |
nested-and/c-to-flat-and/c | 927 ms |
nested-or-to-flat-or | 921 ms |
let-to-define (next slowest) | 136 ms |
Every other rule falls in a smooth tail from ~136 ms down to ~12 ms, so these four are each roughly 7× more expensive than any ordinary syntax-parse-based rule.
Cause
The syntax-tree syntax class in default-recommendations/private/syntax-tree.rkt parses subterms before checking the head identifier:
(pattern (id:id subtree ...)
#:declare subtree (syntax-tree branch-identifier)
#:when (free-identifier=? #'id branch-identifier)
#:cut...)
syntax-parse matches the pattern left to right, so for every list form the rule is tested against, it first recursively parses every subform as a syntax-tree (descending through the entire subtree), and only afterwards runs the #:when check that rejects forms whose head isn't the branch identifier. Nearly all of that recursive work is thrown away, and since rules are tested against every visited form, the cost compounds on large files. All four flattening rules pay this penalty independently.
Suggested fix
Fail fast on the head identifier before recursively parsing subtrees, e.g. by checking free-identifier=? immediately after matching id (via ~fail/~and on the head position, or by matching subforms as plain patterns first and only reparsing them as syntax-trees after the head check passes). The rank/leaf attributes only need to be computed for forms that actually have a matching head.
The rule application timing instrumentation from #798 (implemented in #799) immediately surfaced a hotspot. Running Resyntax on a large file from the DrRacket codebase (
drracket-test/tests/drracket/syncheck-test.rkt, ~2150 lines) spent ~7.5 seconds total checking 179 rules, and the foursyntax-tree-based flattening rules account for 51% of that time:nested-and-to-flat-andnested-or/c-to-flat-or/cnested-and/c-to-flat-and/cnested-or-to-flat-orlet-to-define(next slowest)Every other rule falls in a smooth tail from ~136 ms down to ~12 ms, so these four are each roughly 7× more expensive than any ordinary
syntax-parse-based rule.Cause
The
syntax-treesyntax class indefault-recommendations/private/syntax-tree.rktparses subterms before checking the head identifier:syntax-parsematches the pattern left to right, so for every list form the rule is tested against, it first recursively parses every subform as asyntax-tree(descending through the entire subtree), and only afterwards runs the#:whencheck that rejects forms whose head isn't the branch identifier. Nearly all of that recursive work is thrown away, and since rules are tested against every visited form, the cost compounds on large files. All four flattening rules pay this penalty independently.Suggested fix
Fail fast on the head identifier before recursively parsing subtrees, e.g. by checking
free-identifier=?immediately after matchingid(via~fail/~andon the head position, or by matching subforms as plain patterns first and only reparsing them assyntax-trees after the head check passes). The rank/leaf attributes only need to be computed for forms that actually have a matching head.