/t/tmp
vibe-coded-blog
001 Notes

zlob Optimization: Faster In-Memory Glob Matching Without More Layers

0. Abstract

This note looks at a very specific performance problem:

the paths are already in memory
the caller needs to scan a lot of them
the matcher should stop doing avoidable work before reaching for more machinery

The final zlob changes are practical rather than abstract:

  • keep more simple suffix patterns on the specialized path;
  • avoid rescanning the same path data again and again;
  • reject impossible recursive matches earlier;
  • stop materializing results when the caller only needs a count;
  • shard the scan only when the input is large enough.

The important part is not just what stayed. The important part is also what got measured and removed.

That makes the main result unusually clean:

the code got faster because it did less work
and the benchmark matrix was strict enough to reject the clever ideas that lost

1. Baseline: In-Memory Matching Still Wastes Time If The Shape Is Wrong

The input to zlob is already an array of path slices. That means the obvious expensive work should be avoidable:

  • repeated basename rescans;
  • paying full recursive matching cost when a path obviously cannot match;
  • allocating result buffers for callers that only need a match count;
  • spawning worker threads for scans too small to amortize the overhead.

The optimization order followed that logic:

  1. make the serial matcher do less work;
  2. keep specialized paths alive for the common easy cases;
  3. expose cheaper APIs for count-only or reusable-output callers;
  4. add threading only after the single-thread work is already lean.

2. Widening The Suffix Fast Path Was The First Big Win

The original specialized matcher only kept *.ext-style suffixes on the fast path when the suffix fit in 1 to 4 bytes. That left a lot of common suffixes on the generic matcher even though they were still small enough to be compared cheaply.

Old Shape

 
// SingleSuffixMatcher works for suffixes up to 4 bytes.
if (suffix.len >= 1 and suffix.len <= 4) {
    return .{ SingleSuffixMatcher.init(suffix), suffix_matcher };
}

New Shape

 
// SingleSuffixMatcher works for suffixes up to 8 bytes.
if (suffix.len >= 1 and suffix.len <= 8) {
    return .{ SingleSuffixMatcher.init(suffix), suffix_matcher };
}

Under the hood, the matcher moved from u32-sized masked suffix comparisons to u64, which also helped brace-expanded multi-suffix sets.

Measured Result

The clearest row was a deep brace-expanded case with mixed long suffixes:

WorkloadBaselineAfter widened suffix pathSpeedup
brace_multi_mixed_long_deep, 16384 paths1423.799 us/run164.045 us/run8.68x

On the larger 131072-path version of the same case, runtime moved from 10967.075 us/run to 1537.611 us/run.

That is the kind of result that tells you the specialization target was right. The fast path did not need to become more abstract. It just needed to stay alive for more of the common suffix lengths.

3. Full-Path Tail Comparison Beat Repeated Basename Rescans

The next useful change was simpler than it sounds: stop re-deriving the basename when the matcher already has the full path and only needs the tail.

That mattered most for multi-suffix batches. Once the widened suffix matcher had already cut out the generic work, repeated basename scans became the next avoidable layer.

Measured Result

On the same deep multi-suffix case:

WorkloadBeforeAfterSpeedup
brace_multi_mixed_long_deep, 16384 paths164.045 us/run127.016 us/run1.29x

At 131072 paths, the same case improved from 1537.611 us/run to 1292.853 us/run.

This is a good example of a second-stage optimization that only becomes visible after the first obvious bottleneck is removed.

4. Recursive Matching Needed Earlier Rejection, Not More Heroics

Recursive patterns such as pkg/**/module/*.swift are expensive because they invite normalization and general recursive matching. The useful question is not “can they be made clever?” but “can clearly impossible paths be rejected much earlier?”

The kept answer was a required literal-component prefilter.

If a pattern has ** and later contains a literal component, the matcher first checks whether that component is present as a path segment before paying for the full recursive match.

Measured Result

Filtered recursive benchmark, warm count-only mode:

WorkloadBeforeAfterSpeedup
recursive_long_suffix_prefilter, 131072 paths926.027 us/run838.916 us/run1.10x

Warm reusable-output mode improved from 1044.347 us/run to 954.268 us/run, or 1.09x.

Those are not glamorous numbers. They are still worth keeping because they are stable, cheap, and correct, and because they attack the real bottleneck that remained after the suffix fast paths were fixed.

5. Optional Output Materialization Was A Real API-Level Win

One of the strongest lessons in this work is that runtime cost was not only inside the matcher. Some of it was in forcing every caller through the same allocation behavior.

Two kept API shapes mattered:

  • reusable-output scans, where a retained-capacity list is cleared and reused;
  • count-only scans, where no matched-path materialization happens at all.

Reusable Output

For repeated scans over the same in-memory path arrays:

WorkloadOwned result pathReusable outputSpeedup
brace_multi_mixed_long_deep, 131072 paths, warm954.568 us/run471.258 us/run2.03x

Count-Only

For callers that only need the number of matches:

WorkloadReusable outputCount-onlySpeedup
single_long_suffix_lock, 131072 paths, warm239.021 us/run178.466 us/run1.34x

This is exactly the sort of API-level optimization that often gets missed. Sometimes the fastest matcher is the one that stops building results a caller never asked for.

6. Threading Was Valuable Only After The Serial Path Was Lean

Once the serial matcher had been trimmed down, the threaded APIs produced real wins on large scans.

Count-Only Parallelism

For pkg/**/module/*.swift over 1048576 paths, warm mode:

  • serial: 7901.191 us/run
  • 4 threads: 2636.680 us/run
  • speedup: 3.00x

Reusable-Output Parallelism

On the same workload, warm mode:

  • serial: 8262.994 us/run
  • 8 threads: 2819.714 us/run
  • speedup: 2.93x

Break-Even Matters More Than The Headline

The thread-count evidence is part of the result, not a footnote:

  • serial remained the best choice below roughly 131072 paths on this machine;
  • count-only tended to prefer 4 threads on very large inputs;
  • reusable-output tended to peak near 8 threads on the biggest measured row;
  • 16 threads regressed at every measured size.

That is the right ending for a threading optimization. The answer is not “always parallelize.” The answer is “parallelize when the scan is big enough to pay for it.”

7. The Rollbacks Matter As Much As The Wins

This note would be much less useful if it only listed the kept changes.

Several plausible-looking ideas were measured and removed:

  • BLAS-like batch-8 matching;
  • a literal-prefix prefilter attempt that did not earn a stable win;
  • std.mem.indexOf for required-component search;
  • a specialized recursive literal/**/literal/*.suffix path;
  • a SIMD separator scan for the required-component check.

The sharpest rollback examples were:

Rejected changeWorkloadBeforeAfter
BLAS-like batch-8 matchingsingle_short_suffix_zig, 131072 paths791.748 us/run906.225 us/run
std.mem.indexOf component searchfiltered recursive, warm count-only838.916 us/run1951.303 us/run
SIMD separator scanreusable-output warm977.884 us/run1448.611 us/run

The SIMD separator row is especially useful. It reduced branch misses, but the cycle count still got worse: 21,260,797,779 -> 28,614,128,108.

That is a healthy reminder that lower branch misses are not the same thing as a faster program.

8. Takeaway

The zlob wins are easy to summarize because the benchmark discipline was strong enough to keep the tree honest.

The durable changes were:

  • widen the suffix fast path from 1-4 bytes to 1-8 bytes;
  • stop rescanning basenames when a full-path tail check is enough;
  • reject impossible recursive work with a cheap required-component prefilter;
  • let callers reuse output buffers or request counts only;
  • add threading only for sufficiently large scans.

The larger lesson is even simpler:

first make the serial path stop wasting work
then give callers cheaper contracts
then parallelize only the cases large enough to deserve it

That is why the final matcher is faster without becoming more layered.

Comments