Benchmark evidence

Performance evidence for the matcher and the walker: what is measured, where it runs, how to reproduce it, and what it does not establish.

Wall-time numbers are decision support: no CI job fails on a timing threshold, no release is blocked on a benchmark measurement, and nothing here is a claim to be the fastest library. Two deterministic counts are the exception, and neither is a timing threshold: allocation-count invariants run as ordinary tests, and the user-space CPU gate fails a pull request whose walk executes more instructions than its merge base by more than a documented margin. Deferred follow-up records the same distinction for releases.

The lanes

Why the timing lanes measure wall time. An earlier revision ran the matcher under CodSpeed's simulation instrument, which counts instructions in a virtual machine. It was removed on 2026-08-19: over the period it ran it produced four false alarms and no true finding, every one of them a stale baseline rather than a change in the code under test. For a library of this scope the back-to-back measurement a contributor takes on one machine, before and after, proved to be the evidence that actually caught things. The walker wall-time lane therefore builds the merge base and pull-request head separately and measures them back to back on the same runner. It publishes their ratio for visibility but does not fail on it; push and manual runs publish one snapshot.

That instrument was never right for the walker in any case: it serializes threads and does not model syscall cost, so a parallel-versus-serial comparison there measures instruction count rather than speedup. The user-space CPU lane counts instructions on purpose, for the question wall time cannot answer, and against a merge base built in the same job rather than a stored baseline; the 2026-09-04 amendment to ADR-0012 records why it returned.

What each lane does not establish. The matcher lane says nothing about syscall-bound work. The walker lanes run on synthetic trees written immediately before measurement, so every result describes a warm page cache; cold-cache behavior is a different measurement and is not made anywhere here. Shared runners are noisy: compare arms measured in the same invocation, not numbers from different runs. And no lane says anything about API or semantic scope — the engines compared below do not all offer the same guarantees, and speed is one input among several.

The user-space CPU gate

On a pull request the CPU lane builds cpu_walk twice, from the pull request's head commit and from its merge base, walks one fixture with each binary under Callgrind, and fails when either arm's head count exceeds its merge-base count by more than 2%. The threshold is declared once, as CPU_GATE_PERCENT in walker-bench.yml; the comparison lives in compare_callgrind.rs. A decrease of any size passes. A merge base too old to build the harness is reported without a comparison rather than gated, and push and manual runs have no merge base and publish counts only.

The head is the pull request's own commit, as in the wall-time lane, not the merge commit GitHub checks out. Against the merge base, a merge commit would also carry everything that landed on main since the branch forked, and the gate would charge that work to the pull request.

How 2% was chosen. Issue #358 proposed 5% as a starting point and issue #365 asked for the number to come from observed variance instead. The data is every pull-request run of the lane from when it landed in #364 to the day the gate was enabled: 97 runs across 39 pull requests between 2026-09-04 and 2026-09-24, plus 34 push runs on main, all on ubuntu-latest with Rust 1.98.1. Each count is the summary: total from the run's walker-cpu-portable artifact.

• One thread is exact for practical purposes. In the 35 runs whose diff touches no file the harness compiles — anything outside crates/*/src, the manifests, Cargo.lock, rust-toolchain.toml, and tools/bench/src — head and merge base differed by 31 to 84 instructions out of 66.7 million, and the ratio rounds to 1.00000 in every one. The same holds in all 83 runs whose serial count did not move, which adds pull requests that touched those files without changing what the walk executes: doc comments, version bumps, attributes, code the harness does not call.
• Four threads carries work-stealing noise. In the same 35 runs the ratio ranged from 0.9984 to 1.0025, standard deviation 0.10%; across the 83 runs from 0.9962 to 1.0055, standard deviation 0.15%. One code state measured 124 times — both arms of every run on the 1.0.0-rc.1-era main — spans 0.35% with a standard deviation of 0.08%, so the ratio's spread is what two such draws produce. The serial arm of the same runs does not move, which places the noise in how work is distributed between threads.
• Real changes are small and legible. #425 made excludes apply inside hidden directories and added 1.06% serial and 1.15% on four threads; #415 added up to 0.38% and 0.55%; #413 removed 1.34% and 1.46%. The regression this lane exists for is of another order: after #352 a four-thread walk executed 40% more instructions than a serial one, 244 M against 174 M, measured locally before the lane existed, and the fix removed a third of the four-thread count.

2% is 3.6 times the largest four-thread deviation any unchanged walk produced and about thirteen standard deviations, above every legitimate increase seen, and a small fraction of #352's. One number serves both arms: the serial arm has no noise to clear, so its threshold is a judgement about effect size, and the same margin leaves the four-thread arm well clear of its noise. The data does not support 5%, which would pass a walk that executes 4% more for no reason.

Replaying the gate over all 131 runs confirms the choice: at 2% none fails; at 1% only #425 does, twice; at 0.5% #415 and #416 join it, the second an attribute-and-documentation change that moved only the four-thread arm, by 0.53%; at 0.25%, seven runs fail. The documentation-, CI-, and test-only pull requests of 2026-09-24 — #412, #426, and #427 — measured at most +0.25%, and the ones whose diff reached source files without changing code — #406, #414, #416, and #421 — at most +0.53%.

Accepting an intended increase. A pull request that legitimately adds work — a new correctness check per entry, say — puts a line starting CPU-Increase-Accepted: followed by the reason in its body, then re-runs the failed job. The job reads the body when it evaluates the gate rather than from the event, which a re-run replays unchanged, and publishes the reason beside the counts. The marker without a reason accepts nothing. The check is not a required status, so a maintainer can still merge past it, but the marker is the documented path because it writes the reason down where the increase is reviewed.

When to revisit the number. The comparison is immune to toolchain updates, because both revisions build with the same compiler in the same job, but not to a harness or scheduler change that alters how much the four-thread arm moves. If an unchanged walk ever lands within half a percentage point of the gate, collect the ratios again and re-derive it here.

The per-pull-request data, as head over merge base (ranges cover every run of that pull request, and runs of the same pull request can have different heads or merge bases):

Reproducing

Rust-only, no extra toolchain:

# Matcher, against globset and fast-glob. Add --output-format bencher for one
# line per benchmark instead of criterion's reports.
cargo bench -p bench --bench matcher

# Pattern sets against a loop of patterns and globset::GlobSet.
cargo bench -p bench --bench pattern_set -- --output-format bencher

# Walker wall time, the shape the pull-request lane measures.
cargo bench -p bench --bench walker -- --warm-up-time 1 --measurement-time 5 --sample-size 20

# Engine comparison on a repository-shaped 53k-file tree. This includes
# walkdir, jwalk, globwalk, and wax in addition to the existing arms.
cargo bench -p bench --bench walker_palamedes -- --output-format bencher --noplot

# Opt-in scaling curve. The available point is labeled with the host's actual
# available_parallelism; it remains explicit even when it duplicates 1/2/4/8.
cargo bench -p bench --bench walker_palamedes --features thread-sweep -- \
  thread_sweep/ --output-format bencher --noplot

Node.js ecosystem context requires the exact Node 26.8.1 version recorded in the harness package. Install the locked dependencies once, then run the self-validating harness:

cd tools/bench/node
npm ci
npm run bench

Both walker benches measure the portable backend unless a feature says otherwise. The native backends are separate code paths and are only measured when they are asked for, on the platform that has them:

cargo bench -p bench --bench walker_palamedes --features native-macos
cargo bench -p bench --bench walker_palamedes --features native-linux

Leaving the feature off is how the macOS bulk reader spent its whole life unmeasured: every lane and every reproduction command here read directories through std::fs, so a native backend that was slower than the portable one produced no number that said so. The walker wall-time lane now runs one job per backend, macOS included; the engine comparison stays portable-only in CI and is compared against a native build locally.

Optional zlob context, which needs Zig 0.16 and libclang because the pinned zlob Rust crate 1.6.5 builds through build.rs and bindgen:

# macOS setup used for the current local run: Zig plus Xcode's libclang.
brew install zig
export LIBCLANG_PATH=/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/lib

cargo bench -p bench --bench walker_palamedes --features zlob-oracle,thread-sweep
cargo bench -p bench --bench walker_zlob --features zlob-oracle
cargo bench -p bench --bench walker_zlob_ablation --features native-macos,zlob-oracle
cargo bench -p bench --bench matcher_zlob --features zlob-oracle

zlob is context, never a baseline anything depends on: its benches are behind the zlob-oracle feature, its workflow is manual dispatch only, and no automatic lane requires Zig. The dispatch workflow includes walker_palamedes with thread-sweep, so its Rust and zlob arms provide same-invocation Linux ratios and scaling curves over the 53k-file tree.

The two zlob versions on this page are deliberate. The semantic oracle in tools/oracle is pinned to the 1.6.3 source commit recorded in NOTICE and ADR-0007, so an upstream release can never move the corpus expectations under it; the performance harness in tools/bench pins =1.6.5, the latest registry release, because a speed comparison is only useful against what a consumer would install today. Cargo keeps the two 1.6.x packages apart because one comes from Git and the other from the registry. The current local run used Zig 0.16.0 and Apple libclang 21.0.0 from Xcode.

The engine-comparison measurements in the next section were taken with:

Engine comparison, repository shape

The RFC that started this project opened with one local measurement of a 50,000-file tree — serial ignore + globset at 2,355 ms, ignore parallel with hand-written subtree pruning at 150 ms, zlob at 140 ms — and concluded that existing Rust crates already recovered nearly all of zlob's advantage. That measurement was made against a different codebase on different hardware and was never re-runnable. walker_palamedes.rs rebuilds the shape so the comparison can be repeated: 53,601 files, 2,600 of them TypeScript sources under src/ and packages/, the rest a node_modules tree of 400 top-level packages and 200 nested dependency packages, plus the checked-in .gitignore fixture copied to the benchmark root.

Absolute numbers are not comparable with the RFC's; the ratios between engines on one host are.

The RFC's question — whether existing Rust crates already recover zlob's advantage — was also answered on two real repositories rather than a reconstruction, by a consumer who built the ignore arm the comparison needs and then measured against it over four releases. See Palamedes adoption.

Every arm is run once before timing and has to return the same file count, so no arm can be fast by finding less. The unscoped query can match anywhere and must inspect the whole tree; it finds 7,400 files. The scoped query names src and packages as its only possible roots, so a pattern-aware walker can skip node_modules; it finds 2,600 files. Here, scoped describes the query's root constraint, not a benchmark or process isolation boundary.

The harness also measures an exclude-pruned query: the unscoped include paired with exclude("**/node_modules/**"). It must return the same 2,600 files as the scoped query, but exercises covering-exclude pruning instead. A walker exclude covers hidden descendants too, so a covered node_modules subtree stays closed whatever the include names. A companion arm obtains the same policy from respect_git_ignore(true) and the fixture's node_modules/ rule. Their refreshed values are reported alongside the engine tables below.

The deterministic guard for that performance property is the mock-backend walker test covering_excludes_prune_whatever_the_includes_name: it uses the same **/*.{rs,toml} shape and asserts the exact directories read, so post-filtering the covered subtree fails ordinary CI even though wall-time measurements remain non-gating.

**/*.{ts,tsx} alone — nothing can be pruned

{src,packages}/**/*.{ts,tsx} — the query names its roots

Reading these

• Where the whole tree must be read, Ferralk now leads the portable run: 20.83 ms against 30.09 ms for zlob and 23.15 ms for four-thread jwalk. With native-macos the two engines are level instead — 20.83 ms against 21.45 ms in a separate invocation — so the portable margin is partly zlob paying for a comparison against std::fs, and the level native reading is the more careful claim.
• Where the query names its roots, Ferralk is ahead, and it gets there from the pattern alone. The ignore arm that comes close needs a hand-written filter_entry; the arm that only passes the globs as overrides is 7.1x behind, because overrides decide what is yielded, not what is opened. zlob reads the whole tree for this query, which is why it lands near its unscoped time.
• Serial Ferralk beats parallel ignore on the scoped query (10.75 ms against 30.60 ms) purely by not opening node_modules. Pruning is worth more than threads on this shape.
• The 2,355 ms in the RFC's table was a serial walk doing more per file than this reconstruction does; the 72.23 ms here is the same approach, not the same code.

Which backend those rows measure

The portable one. cargo bench -p bench --bench walker_palamedes compiles ferralk without a native feature, so both ferralk arms above read directories through std::fs, on macOS as everywhere else.

Expanded library comparison on this machine, 2026-09-04 (refreshed)

The comparison was refreshed on the current checkout. It covers four popular Rust libraries plus zlob as the optional cross-language reference, and now includes a separate Node.js ecosystem harness on the same fixture shape:

ignore + globset, globset, fast-glob, Ferralk, and zlob remain in the existing lanes. Every walker arm was checked for the exact same result count before it was timed: 7,400 files for the unscoped query and 2,600 for the scoped query. The new caller-side arms compile their globset inside the timed operation, as the existing Ferralk and ignore arms compile their selection inside the operation. globwalk and wax likewise include their builder work in their timed operation. Matcher-only baselines are compiled once outside their match loop.

Host and method

The complete refresh used these commands. +stable selects the installed 1.97.1 toolchain explicitly:

cargo +stable bench -p bench --bench matcher -- --output-format bencher --noplot
LIBCLANG_PATH=/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/lib cargo +stable bench -p bench --bench matcher_zlob --features zlob-oracle -- --output-format bencher --noplot
cargo +stable bench -p bench --bench walker -- --warm-up-time 1 --measurement-time 5 --sample-size 20 --output-format bencher
cargo +stable bench -p bench --bench walker --features native-macos -- --warm-up-time 1 --measurement-time 5 --sample-size 20 --output-format bencher
LIBCLANG_PATH=/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/lib cargo +stable bench -p bench --bench walker_palamedes --features zlob-oracle -- --output-format bencher --noplot
LIBCLANG_PATH=/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/lib cargo +stable bench -p bench --bench walker_palamedes --features native-macos,zlob-oracle -- --output-format bencher --noplot
LIBCLANG_PATH=/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/lib cargo +stable bench -p bench --bench walker_palamedes --features zlob-oracle,thread-sweep -- thread_sweep/ --output-format bencher --noplot # three times
LIBCLANG_PATH=/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/lib cargo +stable bench -p bench --bench walker_zlob --features zlob-oracle -- --output-format bencher --noplot
LIBCLANG_PATH=/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/lib cargo +stable bench -p bench --bench walker_zlob_ablation --features native-macos,zlob-oracle -- --output-format bencher --noplot
cd tools/bench/node && fnm exec --using=26.8.1 npm run bench

The tables report Criterion's point estimates in milliseconds. They are indicative wall times, not a performance gate. Lower is better. The zlob arm is inside both walker invocations, so each table's Rust and zlob rows share the same fixture and host load.

Portable backend

Ferralk is the fastest arm on both queries here, at 20.83 ms unscoped and 4.32 ms scoped. The unscoped margin is 10% over four-thread jwalk and 31% over the zlob arm in the same invocation; the scoped margin comes from pruning node_modules out of the pattern itself, which the ignore arm reaches only with an extra caller policy at 7.61 ms.

These numbers replace a set roughly 60% higher that was published on 2026-09-04. Nothing in the walker changed between them. The earlier session ran the complete refresh — every backend, the ablations, and three thread sweeps — back to back on a laptop, and its sustained clocks, not the code, are what the old table recorded. That is what "run the arms you want to compare in one invocation, on an idle machine" is protecting against, and it is why no row here is comparable with a row from a different session.

macOS-native backend

The native backend takes the serial walk from 56.91 ms to 46.35 ms. Its parallel arm lands at 20.83 ms against the 21.45 ms zlob arm in the same invocation — a 2.9% margin, which is inside what these two arms vary by between invocations and is not a claim to be faster. The honest reading is that the two engines are level on this query and this host. Scoped Ferralk stays clearly ahead at 3.68 ms because it never opens the dependency subtree.

The portable and native tables come from separate invocations, so their rows are not comparable with each other; the paired ablations below are what a claim about a code change should rest on.

The same invocations also measured the newer covering-exclude and Gitignore queries. Both select the same 2,600 paths as the scoped query:

The targeted, before/after comparisons attribute a 4.9% improvement to parent-relative directory opens and a further 10.3% to depth-first local queues. These are separate wall-time runs, not percentages that can be summed into a complete-table improvement.

Windows, the platform with no number

Windows ships the portable backend and nothing else, and until this lane existed it was the only supported platform whose walker had never produced a published measurement. The lane is a snapshot on push and manual dispatch rather than a per-pull-request comparison: building the fixture set twice on the slowest filesystem in the matrix is a large budget for a tier-2 target. The complete run takes about seven and a half minutes, which is what settled the "if the bounded fixture set remains practical there" condition in issue #358.

The Linux column is the portable engine-comparison run above, on a different runner, and is there only to place the order of magnitude: Windows is several times slower than either Unix platform on the same portable code. That is the finding the lane exists to make visible, not a defect this repository can fix from Rust. Nothing here is a comparison between the two rows.

The deep-chain arm runs 80 levels here against 400 elsewhere, because Windows rejects a full path beyond 260 bytes unless long-path support is enabled and a runner does not guarantee it. Its number is therefore not comparable with the Unix one and never appears beside it; each lane compares against its own merge base.

The same comparison on Linux

The engine-comparison lane in walker-bench.yml runs the identical bench on a GitHub-hosted ubuntu-latest runner. It is manual dispatch, Rust only — the zlob arm needs Zig and stays a local concern — and it measures the portable backend, which is what every arm below uses.

Two things are worth reading off this rather than the absolute numbers, which belong to a shared runner and should not be compared with the M1 Pro tables above.

The ordering is the same on both platforms, and the margin is wider here. Ferralk leads the unscoped query by 2.07x over the next-fastest arm, against 1.11x on macOS, and the scoped query by 3.4x. Linux is also the faster platform in absolute terms for both: 6.11 ms against 20.83 ms for the same portable arm. The macOS syscall costs that the default worker budget section measures are what that gap is made of, and they are why the worker ceiling is a macOS ceiling.

Serial Ferralk beats every parallel arm except one. At 15.76 ms it is ahead of four-thread jwalk at 19.56 ms and behind only parallel ignore at 12.64 ms — on the query where nothing can be pruned, which is the query that should favor threads most.

The exclude-pruned and Gitignore-pruned arms select the same 2,600 paths as the scoped query and land at 1.39 ms and 1.27 ms on four threads, against 2.96 ms serial for the exclude.

Wide-frontier wall time

The regular walker lane includes a shallow fixture with 2,000 sibling directories and 8,000 files. It exercises the bounded serial frontier added in revision 0590fa6; the parallel and ignore arms provide same-run context. The change bounds retained traversal state rather than promising a wall-time speedup, so these are current point estimates, not a before/after claim:

Thread-count sweep, M1 Pro

The opt-in sweep was run three times on the same 10-core (8 performance in two clusters of four, 2 efficiency) M1 Pro host, macOS 26.6.2, rustc 1.97.1, Zig 0.16.0, and zlob 1.6.5. Ferralk used its portable backend so both rows extend the portable single-point comparison above. Each cell is the median of the three Criterion point estimates; parentheses give the range across runs, in milliseconds.

One run of the same sweep with native-macos puts the two engines level rather than leaving Ferralk behind: 45.72 / 28.94 / 18.77 / 29.63 / 35.35 ms against zlob's 47.45 / 29.42 / 18.66 / 30.15 / 36.12 ms. The portable rows above are what the std::fs reader costs, not what the walker costs.

The curve does not show a zlob advantage that grows with core count, and it does not show either walker scaling with the core count at all. Both reach their lowest median at four threads and get slower from there: Ferralk gives back 30% between four and eight threads and 52% between four and ten, and zlob gives back the same. The two engines track each other point for point, which is the first sign that the shape belongs to the platform rather than to either scheduler. What that means for the default worker budget is measured below.

The manual Linux dispatch now emits the same ten bencher lines with its actual available_parallelism embedded in the final label. The label is intentionally kept even when it duplicates one of 1/2/4/8, so artifacts state what the host reported rather than requiring that fact to be reconstructed later.

The new references answer a comparison question, not an adoption question. jwalk is deprecated, walkdir has no matching or pruning policy, globwalk uses a different override contract, and wax accepts UTF-8 expressions rather than Ferralk's arbitrary-byte matcher. Exact semantic compatibility still comes from the checked-in corpus and caller parity tests, not from these wall-time rows. zlob was run in the same fixture and invocation as the other walker arms with Zig 0.16.0 and Apple libclang 21.0.0 installed locally. It remains an optional context lane rather than an automated baseline.

The default worker budget

The sweep above raises a question the sweep alone cannot answer: is the knee at four threads a property of Ferralk's scheduler, of zlob's, or of the machine? Three controls settle it, all on the same host and fixture.

A profile. sample over the four-thread macOS-native walk attributes 95.3% of all CPU across every thread to three syscalls: getdirentries64 65.9%, openat 28.2%, close 1.2%. Everything Ferralk itself does — matching, ignore rules, path building, scheduling, allocation — is under 3% put together. The serial walk is the same picture at 91%. A walk of this shape is not CPU work, so "how many cores are idle" is the wrong question to size it by.

A floor. A 70-line C walker that issues the same syscalls and does nothing else traverses the fixture's 1,723 directories in 37.6 ms serially; the macOS-native walk takes 41.6 ms. The syscall counts are already minimal — one openat, one getdirentries64, one close per directory, the extended EOF flag removing the second read — so there is no traversal work left to remove. Threaded over the same tree, that C walker shows the identical knee: 38.9 ms at one thread, 21.5 at four, 32.9 at eight, 39.2 at ten.

A control. A pure-CPU workload on the same host holds flat from one to eight threads and only degrades at ten, where the efficiency cores come in. pmset -g therm reports no thermal or performance limit during any of it, and the machine carries no third-party system extensions or kexts. The knee is therefore neither thermal nor scheduling noise: it is what the kernel's namespace layer does under concurrency.

Four is this host's hw.perflevel0.cpusperl2 — the performance cores sharing one L2. Threads inside one performance cluster keep the kernel's contended namespace state in that cluster's cache; spilling into the second cluster turns every one of those lines into cross-cluster traffic. Two further measurements support that mechanism over the alternatives. Capping concurrent syscalls with a semaphore of four while running ten threads barely helps (36.7 → 34.0 ms, against 22.2 ms at four threads), so it is not the number of threads inside the kernel at once. And ten threads of which six run at QOS_CLASS_BACKGROUND, which parks them on the efficiency cores, returns to 22.0 ms — the four foreground threads carry the walk and the rest neither help nor hurt.

So the default worker budget is min(available_parallelism, cluster width) on Apple Silicon macOS, read from that sysctl rather than hard-coded, and unbounded elsewhere. Explicit Walker::threads budgets are unaffected. For a caller who sizes no budget on this host, the unscoped query moves from the available_parallelism row of the sweep to the four-thread row:

What this costs. A walk whose per-entry matching dwarfs its filesystem work does scale past four threads, and now has to ask. The crossover is far outside ordinary patterns: **/*.{ts,tsx} costs 46 ms serially and prefers four threads by 36%; a deliberately adversarial **/*{a,b,c}*{1,2}*.{ts,tsx,js,json} costs 94 ms serially and still prefers four threads; only at **/*{a,b,c,d,e,f}*{0,1,2,3}*.{ts,tsx,js,json,md,css}, 199 ms serially and roughly four times the whole filesystem cost, does eight threads win, by 1.5x. A 360-rule .gitignore — the realistic way to add per-entry cost — scales flat from four threads to ten and loses nothing. An adaptive ramp was considered and rejected: it would put clock reads and a nondeterministic policy on the hot path of a scheduler that is otherwise loom-modeled, to recover a case that Walker::threads already covers.

How to reproduce it. The sweep is the standing lane and is reproduced by the thread-sweep command above. The three controls are not lanes and ship no command: the profile is sample <pid> 8 over a loop of walks, and the C floor and its threaded variant are throwaway programs that issue openat, getdirentries64 and close and count entries. They are recorded here because they are what turned "Ferralk is slower above four threads" into "the platform is", and rerunning them means writing them again rather than invoking a lane.

What this does not establish. One host, one microarchitecture. The ceiling is read from a sysctl so that a different Apple Silicon cluster width applies itself, but the rule — that the cluster width is the right ceiling — is measured on an M1 Pro only. It is not applied to Intel macOS, where hw.perflevel0.cpusperl2 counts an SMT pair rather than a cluster, nor to Linux, where no equivalent measurement has been made. Cold-cache behavior was spot-checked on a detached and remounted APFS disk image and is flat from two threads to ten, so the ceiling costs nothing there either; a high-latency network filesystem, where concurrency hides round trips, is not measured anywhere here and is exactly the case for naming a budget explicitly.

Where zlob's earlier unscoped lead came from

zlob led the unscoped query when this section was written. It no longer does: the paired native arms above are level, and the changes recorded here are part of why. The audit and the ablations are kept because they are the evidence for what Ferralk adopted, not because the gap is still open.

A source audit found no single matcher shortcut hidden behind the unscoped number. Its walker combines several low-level choices: a raw getdirentries64 scanner on macOS, retained parent directory handles with openat for children, last-in-first-out local work queues, fixed per-worker path storage, contiguous name bytes with compact entry records, and lazy helper startup. Ferralk already used the raw scanner and lazy startup. The ablation lane tested the remaining plausible differences one at a time on the same 53,600-file fixture.

The two retained changes copy zlob's useful shape, not its implementation. Ferralk uses safe queue primitives and keeps unsafe descriptor operations inside the native backends. Local LIFO processing also preserves the public contract: unsorted parallel result order is deliberately unspecified. The ablation benchmark is diagnostic rather than a headline; its collect/count and path microbenchmarks explain where time can go, while walker_palamedes remains the complete engine comparison. The ablation numbers last published for the current code — 33.26 ms for Ferralk against 32.55 ms for zlob collecting every file — come from the same over-loaded 2026-09-04 session as the old single-point tables and have not been re-measured since; treat them as ordering evidence for the variants above rather than as current wall times.

Matcher refresh

The matcher lane was run in the same environment. These rows use the current point estimates and add wax and zlob to the existing compiled baselines:

wax is faster than globset on the long-path and adversarial rows here, but that does not erase the API and byte-semantics differences. zlob is competitive on short non-matches and the adversarial case, while Ferralk remains faster on the matching and long-path cases. The Ferralk/baseline output is produced by matcher.rs, and the optional zlob rows by matcher_zlob.rs.

Node/TypeScript brace catalogs

The matcher refresh now includes the pattern shape that motivated the latest optimization. One compiled brace expression covers the six common Node/TypeScript extensions; the catalog arm compiles six independent patterns and asks them in order. The scoped expression additionally proves the cross product of three roots and six extensions. All three forms select 768 of the same 1,024 generated paths.

The catalog can win when its first pattern matches, but its cost depends on where a suffix appears. The brace trie keeps first and last extensions close and filters the full list 41% faster than the six-pattern catalog. The scoped row is not a pure suffix comparison: it also checks the allowed-root set.

Node.js ecosystem context

tools/bench/node recreates the same fixture and queries through Node's built-in glob plus current locked ecosystem packages:

The walker harness takes two warmups and ten order-rotated samples, and reports the median. Every candidate must return 7,400 files for the unscoped query and 2,600 for the scoped query before it is timed.

The fastest Node medians are 35.12 ms unscoped and 6.34 ms scoped. The Criterion runs from the same session put portable Ferralk at 20.83 and 4.32 ms and native Ferralk at 20.83 and 3.68 ms. That is useful same-host context, not a formal ranking: the Rust table uses Criterion point estimates while the Node harness reports a median of ten samples, and the APIs do not offer identical semantics.

The matcher harness takes five warmups and fifteen order-rotated samples of 100,000 matches per case. The adversarial case uses 100 matches per sample so a backtracking engine cannot make the run unbounded.

Ferralk's corresponding rows are 11/3 ns for the common case, 11/3 ns for the long case, and 3 ns for the adversarial rejection. This is compiled native Rust against JavaScript libraries, not a Node binding comparison; it isolates matcher work and says nothing about interop or application-level throughput.

The macOS native backend, 2026-08-20

Every lane and every reproduction command in this file left --features native-macos off, so the macOS backend had never appeared in a number here. Turning it on found it losing to the portable backend it exists to beat: getattrlistbulk assembles a per-entry attribute record, and a listing keeps an entry's name, is-dir and is-symlink — the two facts getdirentries64 already returns, in a record a third the size. Routing the reader to getdirentries64 is what the rows below measure.

Four walker_palamedes invocations on one host — the same M1 Pro as above, macOS 26.5.2, rustc 1.97.1, four threads — each with the zlob 1.6.3 arm timed inside the same invocation as its anchor. Read down a column against that anchor rather than across rows: these ran while the host had other work on it, which the unscoped serial spreads show plainly (±13.6 ms on the portable row against ±0.5 ms on the second getdirentries64 round).

Unscoped, **/*.{ts,tsx} — the query that has to read the whole tree:

Scoped, {src,packages}/**/*.{ts,tsx} — the query that prunes:

The serial arm is where the reader shows. 81.0 ms to 58.7 ms is 28% off a walk that is nothing but directory reads and classification, and it is the row with the least to hide behind: one thread, one syscall stream. The bulk reader was 3% behind the portable backend there, which is the finding this section exists to record.

The parallel arm moves less because it is not reader-bound. 36.6 ms to 33.1–33.9 ms is 7–10%, and against the anchor 1.22x to 1.08–1.15x. Four threads against a warm page cache spend a good share of the walk in the coordination and classification the reader change does not touch.

What this does not establish. One host, one tree shape, a warm cache, and an APFS volume. getattrlistbulk returns more than a name and a type, and a future walk that wanted those attributes would be reading a different trade; today nothing downstream of Listing::push can accept one. The spread on the noisier rows is real, which is why the anchor is inside each run and why the getdirentries64 measurement was taken twice.

Final-batch EOF flag, 2026-08-27

Darwin's extended __getdirentries64 buffer reserves its final four bytes for GETDIRENTRIES64_EOF when the buffer is at least 1024 bytes. A small-directory C probe on the same APFS setup returned data and this flag on its first call; the old reader then issued one empty terminal syscall. The native reader now checks that tail only after parsing buffer[..byte_count], so the flag cannot expand parser input or weaken record bounds. A final flagged batch now follows open + read + close, rather than open + read + empty read + close: one directory-read syscall is removed for directories that fit their final batch. This is a syscall-count observation, not a new wall-time benchmark; cache, tree shape, filesystem and concurrent work determine the realized speedup.

Serial descriptor retention, 2026-09-02

0.11.0 made every suspended serial frame release its retained directory descriptor and reopen the directory by full path when it resumed, so a deep tree no longer pinned one descriptor per ancestor. On the far more common wide shapes that cost one open, one close and two identity fstat calls per child directory: strace -c on the medium fixture below counted 3,247 openat calls against 1,648 for the release before, and the serial native walk fell behind the portable backend. A suspended frame now keeps its descriptor while fewer than half of the retention budget is in use and releases it only past that threshold, where a deep chain would otherwise crowd out the directories below it and the other walkers sharing the budget.

Serial collect, --features native-linux, Linux x86_64 container on tmpfs, warm cache; medians of 20 iterations, three rounds interleaved between the two binaries so host noise lands on both. Before is 0.11.0 (f287a96).

The deep chain keeps the 0.11.0 result because it is the shape the release threshold exists for: past 128 retained descriptors the walk releases and reopens exactly as before. The parallel arm never suspends and is unchanged. The descriptor high-water mark of a serial walk over a 300-level chain moves from one to 128 above the baseline, the threshold, and stays there. The wide/ arm of the walker bench lane was added with this change so a per-directory cost on the serial route shows up per pull request.

Listing batch width, 2026-09-03

Revision 0590fa6 split every parallel listing into 64-entry batches and handed the remainder on through a continuation that takes the listing's name buffers with it. The local queue is depth-first, so a worker reading wide siblings hands every one of them off before any continuation returns to it, and each such directory costs a fresh set of buffers that its consumer later drops. On the 53,600-file repository fixture that was every lib/ directory: under callgrind a four-thread walk executed 40% more user-space instructions than a serial one (244 M against 174 M), all of them in the allocator. The batch is now 1,024 entries, so an ordinary directory is classified in one piece while the frontier bound remains for the directory that would otherwise queue a hundred thousand tasks. The same change replaces the extension prefilter's separator and period scans with a direct suffix comparison, which is where the serial instruction count below moves.

Portable and --features native-linux backends, Linux x86_64 container with four cores, the repository fixture on tmpfs, warm cache; each cell is the range of three medians of 30 iterations, the before and after binaries alternating within every round. Before is 034d816.

Instruction counts for three native walks: serial 174 M before and 158 M after; four threads 244 M before and 161 M after. The four-thread walk now executes the instructions of the serial one. Syscalls are unchanged and at the floor for the native backend, one openat, two getdents64, and one close per directory, so the saving is user-space work, and it should be a smaller share of the wall time on a host whose kernel is slower per directory. The allocation-regression test gates the property: a second 100-entry sibling on the parallel route may cost no more than the constant task budget above the backend's per-entry floor. The current macOS tables above include this change.

Per-entry scans, 2026-09-03

With the batch width settled, the serial profile of the native Linux walk put 19% of its user-space instructions in two vectorised memchr calls per directory entry, one for the record's NUL terminator and one for a separator in the name, and another 12% in the extension prefilter's memcmp calls. A name is a dozen bytes: the vectorised search's entry sequence costs more than the bytes it saves, and the two- or three-byte extension comparison cost more through memcmp than the comparison itself. The record parsers now answer both name questions in one byte-at-a-time pass for names that fit one SIMD block and keep the vectorised search above that, the extension check compares the period and the bytes directly, and each entry name is appended to the scratch path without PathBuf::push inspecting it for a root.

Same host, fixture, and method as the previous section. Before is a84ec92.

Instruction counts for three serial walks: native 158 M before and 132 M after (−16%); portable 210 M and 200 M (−5%), since the portable reader has no record parser of its own. Kernel time is unchanged, and on this host it is most of the wall time, which is why a sixth of the user-space instructions moves the total by a few percent. The change is worth its size because it is a simplification with the same validation, guarded by the parser tests for short and long names on both native backends and by unit tests for the path and extension helpers.

Selecting without a caller-side matcher

The caller_match arms in walker.rs model a caller that keeps a GlobSet of its own because the walker cannot express what it selects. WildcardMode::SeparatorCrossing removes that reason for a catalog of *.ext globs: the same 24 patterns become walker includes, and walker_includes_crossing measures the walk with nothing running per entry outside it. All three arms were checked to select the identical set before being timed.

Medians of 41 interleaved rounds on one host, both arms inside each round with the order flipped every round, because this host's load drifted enough during a sequential criterion run to charge one arm for the other's noise:

At repository scale the three are level: the includes arm lands 3% behind visit_in_worker and inside the spread of both GlobSet arms. Handing the selection to the walker costs nothing measurable, and it removes a matcher the caller had to keep in sync.

On the 12-file tree the includes arm is ~19 µs slower, and a control arm that compiles the 24 includes and never walks accounts for it: 12–16 µs. That is pattern compilation, paid once per walker, which a 12-file tree has no entries to amortize it over. A caller that builds one walker and reuses it, or walks anything larger than a toy tree, does not see it.

What this does not show: a catalog of extension globs is the case the extension prefilter handles well. A pattern set the planner can prove nothing about would run every include against every entry, which is the shape where a compiled GlobSet should still win.

When a pool is worth starting

The helper floor decides whether a walk starts threads at all, so what it weighs is a measurement question. This sweep is the evidence behind DIRECTORY_WEIGHT and HELPER_WORK_FLOOR in parallel.rs.

Thirty-six shapes, directory count against files per directory. Each is walked process-fresh — one walk per process, because thread startup is the cost under test and repeated iterations in one process amortize it away — with helpers forced off and forced on, the two arms alternating every round, medians of 51 rounds. The cell is pooled ÷ serial: below 1.00 pooling wins.

Directories cost about twenty times what an entry costs. Holding the entry count at 150 and spreading it across more directories takes the walk from 200 µs at 2 directories to 1374 µs at 75 — 16 µs per directory, with the entries unchanged — while adding 135 entries to a fixed 9 directories costs 110 µs, or 0.8 µs each. That ratio is why the floor counts a listing as twenty entries.

The break-even is one number, not one per shape. The first pooling win arrives at 24 directories of 1 file, 20 of 4, and 14 of 16 — shapes with little in common except that the serial walk takes 480 µs (509, 478, 476). Pooling wins once there is about half a millisecond of walk to divide, which is what it costs to start and join the threads.

What the sweep changed. The floor counted entries alone, which reads a tree of empty directories as trivial: 24 to 31 empty directories stayed serial although pooling wins there by up to 26%, and 32 pooled only because 32 names in the root listing are 32 entries. Weighting the listing removes that cliff and also stops one shape the old floor pooled by mistake, 14 directories of 4 files. Decisions were read from a spawn trace rather than inferred from time — a helper walking empty directories never reaches the visitor, so counting visitor threads would call a running pool serial.

What it did not change. The pair that prompted the issue, 9 directories of 16 files against 17, was already decided correctly. The entry floor never stood alone: requiring HELPER_QUEUE_FLOOR directories still queued when it is met already weighed directories, just implicitly.

Against this host, the floor now picks the better arm on all 36 shapes; the previous one missed 4. Every ratio here is one machine's, and the constants are a judgment about where a thread stops paying for itself, not a threshold any lane enforces.

Several roots, one walker or several

The multi_root arms in walker.rs walk three trees as one walk and as three, producing the same entries either way. What differs is how many times the walk pays for its setup: one thread pool instead of three, one available_parallelism query instead of three.

Medians of 41 interleaved rounds, order flipped every round:

This is not a throughput feature, and the numbers say so. The saving is a fixed per-root cost of a few microseconds, which is visible on a walk small enough for setup to matter — about 3% on the smallest shape, reproduced across runs — and is lost in the noise of anything repository-sized. Helper threads are spawned lazily and only once the work floor is crossed, so even the shape built to isolate pool startup shows no reliable difference: spawning a scoped thread is cheap next to reading a few hundred directory entries.

What one walker actually buys is structural rather than measurable here: one helper-spawn decision taken over the whole walk instead of per tree, so three small roots stay serial where three separate walkers would each weigh themselves; one independent ancestor-chain root per traversal task; and one place for the caller's patterns instead of a loop that rebuilds them per root. The independent chains preserve overlapping, duplicate and alias roots as the concatenation of their single-root walks while still ending genuine cycles. Criterion's sequential arms disagreed with the paired measurement on the smallest shape — it reported the one-walker arm slower — which is drift between arms measured minutes apart, and the reason the table above is paired.

Matcher, against Rust baselines

Wall time per match, same host, one line per benchmark (--output-format bencher). Both baselines are compiled once outside the timed region, as Ferralk's pattern is.

The last row used to be the one to keep in view. On a pattern built to force backtracking — a*a*a*a*b against a run of as — Ferralk ran 1837 ns against globset's 102 ns, because nothing in the general engine consulted the pattern's trailing literal before exploring: the memoized walk visited the whole tokens × path state space and only then failed on the final b.

Three facts are now read off the token IR when a pattern compiles — the leading run of literal and separator tokens, the trailing run, and the bytes the pattern consumes with every star empty — and checked before the engine starts. On the same host, Ferralk arms only:

The middle row is the one that matters for a walker: a traversal filter spends most of its calls on candidates that do not match. The third row is what the check costs when it passes — the engine still runs, and the filter is work on top of it. Every other row of the table above reaches a fast path and is unchanged to within a nanosecond; the full before/after listing is in the pull request that introduced this.

globset is still ahead on a literal non-match and on one deterministic match. Everywhere else the byte-first matcher is ahead, most clearly on long paths, where the baselines pay for path normalization Ferralk does not do.

Pattern compilation is measured separately (compile/* in the same bench) and is not compared against the baselines, whose builders accept different syntax.

Pattern sets, against a loop and globset

PatternSet answers exactly what a loop over its Patterns answers, so the loop is its before-state and GlobSet the external baseline. Every arm asks the same 64 root-relative paths; the table divides each run by 64. globset is built with literal_separator(true), the reading of is_match_glob_path. Apple M1 Pro, macOS, rustc 1.98.1, one --output-format bencher run with every arm interleaved, on a host that was loaded (load average 6 to 12), which is why only ratios within this run are claimed.

The keyed list rotates the shapes long include and exclude lists are made of — **/*.extN, dirN/**, **/nameN/**, **/FileN.txt, prefixN* — so every member has a literal extension, component, or prefix. The unkeyed list is **/*xNy* only: a literal with a wildcard on either side, which the set cannot index and asks for every path, exactly as the loop does.

On keyed lists the set is flat in the list length: a path costs one extension lookup, one lookup per component, and the few members those lookups name, 2.2 times less than the loop at 10 globs, 16 times at 100 and 148 times at 1000, and ahead of GlobSet at every size. On the unkeyed list the set is the loop plus about 3%, and GlobSet's regex set is ahead by the list length. Closing that gap needs a multi-literal substring screen (Aho-Corasick, or rolling hashes over the candidate) for interior literals; it is not built, because lists made only of infix globs are rare and ADR-0013 rules out the regex route. Building a 100-glob keyed set took 97 µs against 75 µs to compile the same patterns for a loop and 283 µs for the GlobSet.

Limitations

• Synthetic fixtures. Every tree here is generated: uniform file sizes, no fragmentation, no permission variety, no network filesystems. A real repository differs in ways that matter for I/O. Palamedes adoption is the one record here taken on real repositories, and carries its own limitations.
• Warm cache only. Nothing here measures a cold page cache, which is what a first walk after boot pays.
• One host per table. These numbers were taken on one machine. The lanes in CI run on shared runners and move with them; that is why nothing gates on them.
• Scope differs between engines. globset and fast-glob are matchers, walkdir is traversal only, jwalk is deprecated, globwalk is a serial wrapper around walkdir and ignore, wax is UTF-8/regex-based, ignore is a walker with gitignore support, and zlob is a Zig library behind a C ABI with its own semantics. They are compared here on the one axis they share, the shape and speed of a query, and the corpus is where behavior is compared.
• Thread count is fixed at four. A different count changes the parallel arms and would change the ordering on a machine with a different core count.