Skip to content

Hand out the child of a rule that only forwards it - #7

Open
JelteF wants to merge 1 commit into
v2.0-cyanopterafrom
split-collapse
Open

JelteF wants to merge 1 commit into
v2.0-cyanopterafrom
split-collapse

Conversation

@JelteF

@JelteF JelteF commented Sep 21, 2026

Copy link
Copy Markdown
Owner

Every level of the operator precedence hierarchy — Expression, LogicalOrExpression, LogicalAndExpression, down to BaseExpression — has the shape X <- Y Tail*, with a transformer that returns Y untouched when no tail matched. Each level still allocated a ListParseResult around its single child and later spent a transform frame unwrapping it again; for a literal like 42 that 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.yml is 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 on ParserGrammarConstruction, paid once per DatabaseInstance. What it buys is that the list cannot drift, plus the rule-of-its-own guard.

benchmark v2.0-cyanoptera this branch
ParserAoC 1.631s 1.379s -15.4%
ParserFlummi 2.579s 2.210s -14.3%
ParserGrammarConstruction 1.478s 1.505s +1.8%
ParserKeywordIdentifiers 0.789s 0.654s -17.2%
ParserMalformedSelect 0.549s 0.549s -0.1%
ParserNestedExpressions 1.310s 0.882s -32.7%
ParserStatements 1.129s 0.840s -25.6%
ParserStress * 11.043s 8.340s -24.5%
ParserTPCDS 2.509s 2.091s -16.7%
ParserTPCH 1.113s 0.931s -16.3%
ParserValuesList * 12.276s 9.467s -22.9%
ParserWideSelect 2.629s 2.147s -18.3%
geometric mean -17.4%

Rows marked * come from the benchmarks added by duckdb#26015

How this was measured

This repository's benchmark_runner, built BUILD_BENCHMARK=1 BUILD_JEMALLOC=1 make release (clang
21.1.8, plain release — no LTO, matching what the parser regression CI builds). Every branch and
v2.0-cyanoptera were 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.

@JelteF JelteF changed the title Collapse precedence-ladder rules that matched only their operand Hand out the child of a rule that only forwards it Sep 22, 2026
@JelteF
JelteF force-pushed the split-collapse branch 3 times, most recently from f8690c2 to 274309e Compare September 22, 2026 09:56
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.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

1 participant