Skip to content

perf(parser): build AST lists in thread-local scratch buffers#24539

Draft
Boshen wants to merge 1 commit into
mainfrom
parser-scratch-buffers
Draft

perf(parser): build AST lists in thread-local scratch buffers#24539
Boshen wants to merge 1 commit into
mainfrom
parser-scratch-buffers

Conversation

@Boshen

@Boshen Boshen commented Jul 15, 2026

Copy link
Copy Markdown
Member

Building a list by pushing into an ArenaVec reallocates within the arena as the vec grows. Child AST nodes are allocated between pushes, so the growing buffer is almost never the arena's most recent allocation — every doubling allocates a new buffer and abandons the old one as permanent dead space in the arena. A list of N elements costs ~⌈log2 N⌉ grow events and ~2-4× its final size in arena bytes.

This PR builds every list in a scratch std::Vec instead, and moves the completed list into the arena with a single exact-sized allocation (a memcpy).

Design

  • One scratch vec per list element type (ScratchBuffers, ~27 fields). Nested lists with the same element type (statements of nested blocks, arguments of nested calls) share one vec, used like a stack via watermarks: record the vec's length at list start, push elements, drain your own tail at completion. List parsing is strictly LIFO — parse errors are stored rather than thrown, and element closures cannot early-exit their caller — so a list always drains its own elements before its enclosing list resumes. (This is the scratch pattern used by Zig's std.zig parser, split per element type since our lists are heterogeneous.)
  • The buffers are checked out of a thread-local cache when the parser is created and returned emptied when it is dropped (panics included, via a drop guard). They are never freed, staying grown to high-water capacity across parses on the same thread — once a thread is warm, list building performs no heap allocation at all. The only unsafe is an empty-struct lifetime cast at checkout/checkin.
  • The cursor.rs list helpers carry the discipline for almost all sites; comma-separated lists with no closing token get new parse_separated_list/parse_separated_list_from helpers. A debug assert at parse end catches any future site that pushes without draining (checked by every conformance run, which uses debug-assertions = true).

Results

just allocs (Arena allocs, Sys allocs, Sys reallocs are all unchanged):

File Arena reallocs
checker.ts 22,860 → 59
antd.js 55,355 → 1,285
kitchen-sink.tsx 11,905 → 249
pdf.mjs 8,153 → 112
App.tsx 3,537 → 64
binder.ts 1,476 → 24

The residue is mostly lexer StringBuilder escape paths and the comments vec, which are not converted.

Parser benchmarks improve up to ~10% (parser/App.tsx, parser/react.development.js, estree/checker.ts) and regress nowhere; conformance output is byte-identical across all suites.

🤖 Generated with Claude Code

@Boshen
Boshen force-pushed the parser-scratch-buffers branch from 2a7bd08 to 9991374 Compare July 15, 2026 09:01
@github-actions github-actions Bot added the A-parser Area - Parser label Jul 15, 2026
@codspeed-hq

codspeed-hq Bot commented Jul 15, 2026

Copy link
Copy Markdown

Merging this PR will not alter performance

✅ 62 untouched benchmarks
⏩ 9 skipped benchmarks1


Comparing parser-scratch-buffers (e1c7432) with main (71c2f53)2

Open in CodSpeed

Footnotes

  1. 9 benchmarks were skipped, so the baseline results were used instead. If they were deleted from the codebase, click here and archive them to remove them from the performance reports.

  2. No successful run was found on main (510c435) during the generation of this report, so 71c2f53 was used instead as the comparison base. There might be some changes unrelated to this pull request in this report.

@Boshen
Boshen force-pushed the parser-scratch-buffers branch from 9991374 to 0fee28e Compare July 15, 2026 09:32
@Boshen
Boshen changed the base branch from main to allocs-snap-bytes July 15, 2026 09:32
@Boshen
Boshen force-pushed the allocs-snap-bytes branch from c2d05ea to fa30393 Compare July 15, 2026 09:35
@Boshen
Boshen force-pushed the parser-scratch-buffers branch from 0fee28e to 7589f35 Compare July 15, 2026 09:39

Boshen commented Jul 15, 2026

Copy link
Copy Markdown
Member Author

Warning

This pull request is not mergeable via GitHub because a downstack PR is open. Once all requirements are satisfied, merge this PR as a stack on Graphite.
Learn more


How to use the Graphite Merge Queue

Add either label to this PR to merge it via the merge queue:

  • 0-merge - adds this PR to the back of the merge queue
  • hotfix - for urgent changes, fast-track this PR to the front of the merge queue

You must have a Graphite account in order to use the merge queue. Sign up using this link.

An organization admin has enabled the Graphite Merge Queue in this repository.

Please do not merge from GitHub as this will restart CI on PRs being processed by the merge queue.

This stack of pull requests is managed by Graphite. Learn more about stacking.

@graphite-app
graphite-app Bot force-pushed the allocs-snap-bytes branch 2 times, most recently from 69068b0 to 6573f83 Compare July 15, 2026 12:25
@graphite-app
graphite-app Bot force-pushed the parser-scratch-buffers branch from 7589f35 to 1b647b5 Compare July 15, 2026 12:25
@Boshen
Boshen force-pushed the allocs-snap-bytes branch 2 times, most recently from 906b58c to f83d4e0 Compare July 15, 2026 12:36
@Boshen
Boshen changed the base branch from allocs-snap-bytes to graphite-base/24539 July 15, 2026 13:04
@graphite-app
graphite-app Bot force-pushed the graphite-base/24539 branch from f83d4e0 to 073e5a0 Compare July 15, 2026 13:26
@graphite-app
graphite-app Bot force-pushed the parser-scratch-buffers branch from 1b647b5 to 6f3dda8 Compare July 15, 2026 13:26
@graphite-app
graphite-app Bot changed the base branch from graphite-base/24539 to allocs-snap-bytes July 15, 2026 13:27
@graphite-app
graphite-app Bot force-pushed the parser-scratch-buffers branch from 6f3dda8 to 81cc312 Compare July 15, 2026 13:27
@Boshen
Boshen force-pushed the parser-scratch-buffers branch from 81cc312 to 5e49c55 Compare July 15, 2026 13:40
@Boshen
Boshen changed the base branch from allocs-snap-bytes to main July 15, 2026 13:40
Building a list by pushing into an `ArenaVec` reallocates within the arena
as the vec grows. Child AST nodes are allocated between pushes, so the
growing buffer is almost never the arena's most recent allocation - every
doubling allocates a new buffer and abandons the old one as permanent dead
space in the arena.

Instead, build every list in a scratch `std::Vec` and move it into the
arena with a single exact-sized allocation (memcpy) once complete. There is
one scratch vec per list element type (`ScratchBuffers`); nested lists with
the same element type share one vec stack-like via watermarks: record the
length at list start, push, drain your own tail at completion. List parsing
is strictly LIFO (errors are stored, not thrown), so a list always drains
its own elements before its enclosing list resumes. This is the scratch
pattern used by Zig's `std.zig` parser, split per element type.

The buffers are checked out of a thread-local cache when the parser is
created and returned emptied when it is dropped, so they are never freed
and stay grown to high-water capacity across parses on the same thread.
Once a thread is warm, list building performs no heap allocation at all.

Arena reallocs during parsing drop by 98-99.7% (checker.ts 22860 -> 59,
antd.js 55355 -> 1285); arena allocs and system allocs are unchanged.
Parser benchmarks improve by up to ~10% (App.tsx, react.development.js)
and regress nowhere. Conformance output is byte-identical.

🤖 Generated with [Claude Code](https://claude.com/claude-code)

Co-Authored-By: Claude <[email protected]>
@Boshen
Boshen force-pushed the parser-scratch-buffers branch from 5e49c55 to e1c7432 Compare July 15, 2026 13:48
graphite-app Bot pushed a commit that referenced this pull request Jul 22, 2026
…taging buffers (#24583)

Apply #24539, share `ScratchBuffer`'s buffer.

NOTE: checked-in vectors keep their high-water capacity for the thread's lifetime (same policy as #24539). This is ~KB for regular sources, and fine.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

A-parser Area - Parser

Projects

None yet

Development

Successfully merging this pull request may close these issues.

1 participant