perf(config): literal-suffix reject and prune irrelevant globs per base by bartlomieju · Pull Request #35688 · denoland/deno

bartlomieju · 2026-07-01T16:53:47Z

Two follow-ups to #35039, both on the file-discovery hot path shared by
fmt, lint, and test. #35039 already precomputes a pattern's literal
base prefix and matches against the shorter relative path; this builds on
that with the two remaining ideas from #21830.

The first is a literal-suffix reject. GlobPattern now precomputes the
maximal trailing glob-free run of its pattern (for example .ts for
**/*.ts). Any path matched by the pattern must end with that run, so
matches_path() checks it and bails before touching the glob engine when
it doesn't. The comparison is ASCII case-insensitive to match the glob
engine's own case_sensitive: false option. To keep the suffix a genuine
necessary condition, the run stops at any glob metacharacter, including
the escaped brackets [[] and []] that literal brackets are rewritten
to, and at any non-ASCII byte. This is the optimization suggested in the
issue comment (globs ending in a static string can check that part
first). Since the suffix is computed from the pattern text normalized to
/ while matches_path() receives OS paths, the comparison treats \
and / as equivalent; otherwise a suffix spanning a directory boundary
(such as /deno.json) would reject every workspace member config file on
Windows. Normalizing only widens what passes the pre-filter (the glob
engine still runs afterward), so it never drops a genuine match.

The second prunes irrelevant patterns per base. When split_by_base()
builds the include set for a base directory it walks the base's ancestors
and inherits their patterns. A new can_match_under() check now drops
inherited patterns that can provably never match anything under that
base, so for includes like src/a*/**/*.ts and src/b/**/*.ts the walk
of src/b no longer tests every file against the a* pattern. The check
is segment-wise, understands *, ?, and **, and errs toward keeping a
pattern whenever a match is still possible, so it only removes dead weight
and never changes which files are collected. This resolves the
long-standing todo() in that loop.

Pruning exposed an edge in split_by_base(): it collapses an empty
applicable-include set to include: None, which means include-everything
under the base. That was safe when the set could only be empty because no
include pattern was anchored at or above the base, but pruning added a
second way to empty it: a base can inherit candidate patterns that are
all dropped as unable to match under it. Collapsing that case to None
flipped a closed include set into include-everything and collected files
that were never included (for example a negated exclude base sitting
outside every glob include's reach). split_by_base() now tracks whether
any candidate pattern existed before pruning and keeps a closed (empty)
include set when pruning removed them all.

Added unit tests covering suffix extraction (case folding, escaped
brackets, and non-ASCII boundaries), suffix-based rejection including
negated patterns and backslash-separated paths, can_match_under, and a
regression test for the pruned-to-empty include set.

Refs #21830.

Two follow-ups to #35039 on the fmt/lint/test file-discovery hot path. GlobPattern now precomputes the trailing glob-free ASCII run of its pattern (e.g. ".ts" for "**/*.ts"). matches_path() rejects any path that doesn't end with that suffix before running the glob engine, using an ASCII case-insensitive compare that matches the engine's own case-insensitive options. The run stops at any glob metacharacter (including the escaped brackets "[[]"/"[]]") and at any non-ASCII byte, so the suffix stays a genuine necessary condition for a match. split_by_base() no longer hands a base every include pattern inherited from its ancestors; can_match_under() drops patterns that can provably never match anything under that base (e.g. "src/a*/**/*.ts" is not tested against files walked under "src/b"). The check is segment-wise and errs toward keeping a pattern whenever a match is still possible, so it only removes dead weight and never changes which files are collected. This resolves the long-standing todo() in that loop.

The literal_suffix is computed from the pattern text normalized to '/', but matches_path receives OS paths which on Windows use '\' as the separator. A suffix that spans a directory boundary (e.g. '/deno.json') therefore never matched a Windows path ending in '\deno.json', so every workspace member config file was rejected by the fast-path and workspace globbing broke on Windows only. Treat '\' and '/' as equivalent in path_ends_with_ascii_ci. Normalizing only widens what passes the pre-filter (the glob engine still runs afterward), so it never drops a genuine match.

split_by_base() collapses an empty applicable_includes to `include: None`, which means "include everything under this base". That was safe before per-base pruning because the set was only empty when no include pattern was anchored at or above the base (a broad path include covered it). can_match_under() introduced a second way to empty the set: a base can inherit candidate patterns that are all pruned as unable to match under it. Collapsing that to None flips a closed include set into include-everything and collects files that were never in the include set (e.g. a negated exclude base sitting outside every glob include's reach). Track whether any candidate pattern existed before pruning and, when pruning empties a non-empty candidate set, keep a closed (empty) include set instead of None so nothing under the base is collected. Add a regression test.

bartlomieju · 2026-07-01T21:24:51Z

Benchmark: file-discovery / glob-matching hot path

Measured the effect of this PR (literal-suffix reject + split_by_base
pruning) on the shared fmt/lint/test file-discovery path.

tl;dr — on a deliberately matching-heavy tree, wall-clock is ~1.1x
faster and user CPU drops ~23-27%. The large kernel/syscall (traversal)
time is common-mode, so user CPU is the metric that isolates this change, and
that is where the whole win lands.

Environment

Apple M1 Max (8P+2E, 10 cores), 64 GB, macOS 15.5
hyperfine 1.15.0, release builds (rustc 1.95.0)
baseline: system deno 2.9.1 (stable release)
branch: target/release/deno built from this branch = 2.9.1 + the two
perf commits + the pruning-correctness fix. So this is effectively an
isolated A/B of the PR.

Setup

Synthetic tree chosen to make the changed code a meaningful share of runtime:

62,400 files, of which only 6,240 are .ts; the rest use extensions
(.log, .dat, .txt, .csv, .bin, .lock, .map, .snap) that match
no include glob, so each hits the new literal-suffix fast reject.
81 include patterns (packages/*/src/keep-*/**/*.ts + one deep literal
packages/pkgNNN/src/gen/anchor/**/*.ts per package). The deep bases inherit
the shallow keep-* pattern, which can_match_under prunes (keep-* vs
gen), exercising the second optimization.
Command run inside the tree so deno.json include/exclude is picked up.

The collector calls matches_path_detail for every visited file before the
fmt/lint extension filter, so all 62k files exercise the suffix reject, most of
them against multiple patterns.

Results — `deno fmt --check` (20 runs x 3 rounds)

round	system 2.9.1 (ms)	branch (ms)	wall speedup
1	319.8 ± 35.0	272.5 ± 3.1	1.17x
2	320.8 ± 47.5	278.4 ± 15.7	1.15x
3	305.6 ± 6.1	286.3 ± 38.1	1.07x

User CPU: system ~130 ms → branch ~100 ms (~23% less). (System/kernel time
~410-540 ms, essentially unchanged.)

Results — `deno lint` (12 runs x 3 rounds)

round	system 2.9.1 (ms)	branch (ms)	wall speedup
1	305.2 ± 3.4	272.7 ± 3.7	1.12x
2	303.8 ± 3.8	272.1 ± 4.3	1.12x
3	308.3 ± 13.0	275.8 ± 12.6	1.12x

User CPU: system ~115 ms → branch ~84 ms (~27% less). The lint rounds were
very stable (1.12x every round).

Interpretation

The workload is syscall/IO-bound (directory traversal), and that portion is
identical on both binaries. So wall-clock (~1.1x) understates the change;
the honest per-CPU signal is the ~23-27% reduction in user time, which is
exactly the code path this PR touches.
Real repositories have far fewer files and patterns than this stress tree, so
they will see smaller absolute wall-clock gains, but the direction (less CPU
spent in glob matching, no extra allocations) holds.

Caveats

Synthetic microbenchmark on a single machine; a few fmt runs were flagged
as statistical outliers (background noise) — the tighter lint numbers are
the more trustworthy read. Both agree.
Correctness note unrelated to timing: the per-base pruning could previously
flip a base's closed include set to include: None (include-everything) when
every inherited pattern was pruned; fixed on this branch with a regression
test (file_patterns_split_by_base_dir_pruned_to_empty).

_{Harness (local, not committed): a small generator builds the tree +

deno.json, and hyperfine compares the two binaries running fmt --check /

lint inside it.}

bartlomieju added 3 commits July 1, 2026 18:53

bartlomieju merged commit a126271 into main Jul 3, 2026
137 checks passed

bartlomieju deleted the perf/glob-suffix-and-base-filter branch July 3, 2026 09:21

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

perf(config): literal-suffix reject and prune irrelevant globs per base#35688

perf(config): literal-suffix reject and prune irrelevant globs per base#35688
bartlomieju merged 3 commits into
mainfrom
perf/glob-suffix-and-base-filter

bartlomieju commented Jul 1, 2026 •

edited

Loading

Uh oh!

bartlomieju commented Jul 1, 2026

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

1 participant

Uh oh!

Conversation

bartlomieju commented Jul 1, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

bartlomieju commented Jul 1, 2026

Benchmark: file-discovery / glob-matching hot path

Environment

Setup

Results — deno fmt --check (20 runs x 3 rounds)

Results — deno lint (12 runs x 3 rounds)

Interpretation

Caveats

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

1 participant

bartlomieju commented Jul 1, 2026 •

edited

Loading

Results — `deno fmt --check` (20 runs x 3 rounds)

Results — `deno lint` (12 runs x 3 rounds)