Conversation
JelteF
force-pushed
the
split-collapse
branch
from
September 22, 2026 07:38
a0756f7 to
d4b8221
Compare
JelteF
force-pushed
the
split-collapse
branch
3 times, most recently
from
September 22, 2026 09:56
f8690c2 to
274309e
Compare
An expression like the literal `42` is parsed through the full operator precedence hierarchy: `Expression`, `LambdaArrowExpression`, `LogicalOr`, `LogicalAnd`, `LogicalNot`, `Is`, `IsDistinctFrom`, `Comparison`, `BetweenInLike`, `OtherOperator`, `Bitwise`, `Additive`, `Multiplicative`, `Exponentiation`, `Collate`, `AtTimeZone`, `Prefix` and `BaseExpression`. Every one of those rules has the shape `X <- Y Tail*` and a transformer that returns Y's result untouched when no tail matched, yet each level allocated its own `ListParseResult` wrapper around the single child and later cost a transform frame just to unwrap it again. For a query with a few thousand literals that is tens of thousands of parse results and transform processes carrying no information. The hierarchy is the worst case but not the only one: a hundred more rules exist only to name something and forward it. Rules can now be registered with `MatcherFactory::AddCollapsibleRule`. When such a rule finishes matching and exactly one child produced a result, with every other child an optional that matched nothing, `ListMatchProcess` hands out that child's parse result in place of its own and marks it `collapsed`. `TransformInput::GetRule` then transforms a collapsed result with its own rule even when the parent asked for the collapsed rule, which is correct precisely because the collapsed rule would have returned the child's value unchanged. A result handed out this way has to carry a rule of its own, since it is transformed as itself; where it does not, the rule keeps its frame. Which rules those are is read off the transformers rather than listed, because a list of a hundred names drifts from the grammar. Two shapes are recognised once the trampolines have been emitted: - a generated finalizer that takes its one child result and returns it, which is what a rule that only names something compiles to, and - a hand-written transformer that moves its operand into a local and returns that local when the optional tail did not match, which is what every level of the precedence hierarchy is written as. That accounts for 120 of the 123 rules, the 18 precedence levels among them. `grammar_types.yml` is left naming three that neither shape catches, each with the reason: `LogicalOrExpression` and `LogicalAndExpression` forward inside a shared `FoldConjunctionExpression` helper rather than in their own body, and `PrefixExpression` has no hand-written transformer to read the shape off.
JelteF
force-pushed
the
split-collapse
branch
from
September 22, 2026 16:46
274309e to
1f3a7b0
Compare
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Every level of the operator precedence hierarchy —
Expression,LogicalOrExpression,LogicalAndExpression, down toBaseExpression— has the shapeX <- Y Tail*, with a transformer that returns Y untouched when no tail matched. Each level still allocated aListParseResultaround its single child and later spent a transform frame unwrapping it again; for a literal like42that is eighteen wrappers carrying no information. Rules can now be registered as collapsible: when such a rule matches and exactly one child produced a result, the matcher hands out that child's parse result instead of wrapping it. A result handed out that way is transformed as itself, so it has to carry a rule of its own; where it does not, the rule keeps its frame.Which rules those are is read off the transformers rather than listed by hand, because a list of a hundred names drifts from the grammar — this one already did once, when regenerating deleted it. Two shapes are recognised: a generated finalizer that returns its one child result, and a hand-written transformer that moves its operand into a local and returns it when the optional tail did not match. That covers 120 of the 123 rules, and
grammar_types.ymlis left naming the three that neither shape catches, each with the reason. Deriving the set measures the same to within 0.02%, since the precedence hierarchy is where essentially all of the waste is, and costs 1.3 of the 2.3 points onParserGrammarConstruction, paid once perDatabaseInstance. What it buys is that the list cannot drift, plus the rule-of-its-own guard.v2.0-cyanopteraParserAoCParserFlummiParserGrammarConstructionParserKeywordIdentifiersParserMalformedSelectParserNestedExpressionsParserStatementsParserStress*ParserTPCDSParserTPCHParserValuesList*ParserWideSelectRows marked
*come from the benchmarks added by duckdb#26015How this was measured
This repository's
benchmark_runner, builtBUILD_BENCHMARK=1 BUILD_JEMALLOC=1 make release(clang21.1.8, plain release — no LTO, matching what the parser regression CI builds). Every branch and
v2.0-cyanopterawere built from the same worktree and each benchmark ran under all of them in turn,within each of three rounds, so machine state is shared; each figure is the median of those rounds,
over a median of three timed runs each.
BUILD_BENCHMARK=1 make release build/release/benchmark/benchmark_runner 'Parser.*'AMD EPYC 9R14, 32 cores, no SMT, Ubuntu 24.04. The full suite passes on this branch.
These parser changes are being sent as separate branches, and they overlap — several remove work from
the same expression matching — so if more than one lands, the second will measure smaller than quoted
here.