PR 521 caused catastrophic slowdown in AddPattern time for wildcards

[timbray]

Hey @sayrer - By a factor of like 10x in BenchmarkShellStyleBuildTime if increasing the number of words. Thinking about reverting this one until we figure out what's going on.

[sayrer]

oh shoot, ok, sorry for missing that.

[sayrer]

wrote a little test program and found the culprits (a few bugs), but the per-word cost is still there.

Substantial recovery. Here's the full picture (shellstyle build, ms):

  ┌──────┬──────────────────────┬───────────────┬──────────────┬───────────────┐
  │  N   │ main (struct fields) │ branch before │ branch fixed │ fixed vs main │
  ├──────┼──────────────────────┼───────────────┼──────────────┼───────────────┤
  │ 125  │                  6.0 │          39.7 │         24.7 │          4.1× │
  ├──────┼──────────────────────┼───────────────┼──────────────┼───────────────┤
  │ 250  │                 17.1 │          96.9 │         51.1 │          3.0× │
  ├──────┼──────────────────────┼───────────────┼──────────────┼───────────────┤
  │ 500  │                 57.3 │         317.3 │        139.3 │          2.4× │
  ├──────┼──────────────────────┼───────────────┼──────────────┼───────────────┤
  │ 1000 │                188.5 │        1321.2 │        489.5 │          2.6× │
  └──────┴──────────────────────┴───────────────┴──────────────┴───────────────┘

  The pathological part is gone. Per-word cost on the fixed branch now grows 197→489 µs (2.5×
  over 8× words) — essentially the same slope as main (3.9×), where before it was 4.2× and
  accelerating. That confirms the quadratic NFA-walk blowup (broken walkGen dedup) and the
  allocation storm were the real culprits, and both are fixed. Full test suite passes (17.7s).

  The honest residual

  There's still a ~2.6× constant-factor gap vs main at N=1000. That's not a bug — it's the
  irreducible cost of the branch's design goal. The build re-runs epsilonClosure over the
  whole growing NFA on every AddPattern (O(N²) visited-checks, true on main too). Main pays
  each check as a near-free struct-field compare; any off-struct design pays it as a
  pointer-hash map lookup. You can't close that gap without putting the generation state back
  on smallTable/faState — which is exactly the steady-state memory the branch set out to
  remove.

  So this is now a clean tradeoff decision rather than a regression:

  - Keep the fix → builds ~2.6× slower than main, but smallTable loses 24 bytes and faState
  loses 8 bytes each at steady state (tens of MB on large matchers).
  - Revert to struct fields → full build speed, no memory savings.

[sayrer]

Looks like if we keep going, we can take back everything, this is with the bug fixes above on:

https://github.com/sayrer/quamina/tree/embed-smalltable

  Headline

  Net slightly faster than main overall: geomean sec/op −1.25%, B/op −0.48%,
  allocs −0.47%. The wins are concentrated where it matters
  (build + large-pattern matching); two regressions stand out, one of which
  is dead code.

  Wins

  ┌────────────────────────────────────────────────────────────────────────────┬────────────────────┐
  │                                 Benchmark                                  │       Δ time       │
  ├────────────────────────────────────────────────────────────────────────────┼────────────────────┤
  │ ShellStyleBuildTime                                                        │ −27.5% (B/op −30%) │
  ├────────────────────────────────────────────────────────────────────────────┼────────────────────┤
  │ ShellstyleWidePatternsScaling /256, /512                                   │ −24%, −23.5%       │
  ├────────────────────────────────────────────────────────────────────────────┼────────────────────┤
  │ ShellstyleNarrowInput …/patterns=128 (most)                                │ −10% … −16%        │
  ├────────────────────────────────────────────────────────────────────────────┼────────────────────┤
  │ Workload_CacheThrashing                                                    │ −9.4%              │
  ├────────────────────────────────────────────────────────────────────────────┼────────────────────┤
  │ Workload_ManyOverlappingWildcards/N=128                                    │ −12.3%             │
  ├────────────────────────────────────────────────────────────────────────────┼────────────────────┤
  │ Workload regex micro (Alternation/Literal/Quantified/Anchored/DeepEpsilon) │ −6% … −7%          │
  ├────────────────────────────────────────────────────────────────────────────┼────────────────────┤
  │ ShellstyleSimpleWildcardScaling                                            │ −5% … −7%          │
  └────────────────────────────────────────────────────────────────────────────┴────────────────────┘

  The build-time win is the headline: the fix didn't just recover the
  regression — embed now beats main at building shellstyle matchers, and
  large-pattern match throughput improves substantially (the embedded
  smallTable removes a pointer indirection on the hot traversal).

  Regressions (2)

  ┌─────────────────────────────────┬────────┬─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
  │            Benchmark            │ Δ time │                                                        Note                                                         │
  ├─────────────────────────────────┼────────┼─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
  │ Nfa2Dfa/*                       │ +63% … │ Dead code — nfa2Dfa is "not used as of 2026/01". tableShareKey dedup + larger struct copies cost more than pointer  │
  │                                 │  +72%  │ identity. Allocs actually −7…−9%. Irrelevant to production, but flag if it's ever revived.                          │
  ├─────────────────────────────────┼────────┼─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
  │ JsonFlattener/Evaluate          │ +9% …  │ Unexpected — flattening doesn't touch smallTable. But BenchmarkCityLots (realistic, flattening-heavy) is flat (~0%, │
  │ MiddleNested/LastField          │ +15%   │  p=0.39), so this is almost certainly code-layout/inlining shift from the package-wide struct change, not a real    │
  │                                 │        │ hot-path regression.                                                                                                │
  └─────────────────────────────────┴────────┴─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
  
  Memory

  Per-op allocs/B are identical across nearly all match benchmarks (the change
  doesn't affect match-time allocation). Build allocations dropped
  (ShellStyleBuildTime B/op −30%); Nfa2Dfa allocs −7…−9%.

  Important: these are per-op metrics — they do not measure the resident size
  of a built matcher, which is the actual goal of embed-smalltable. To see
  whether embedding smallTable shrinks steady-state memory, I'd run
  GetMatcherStats/memory_cost on a large built matcher. Want me to? ```

[sayrer]

Got that Nfa2Dfa regression too.

smallTable embedding — it was the same generation-counter → map anti-pattern
as the epsilon-closure bug, this time in intern()'s dedup (clear
(sl.seen) + per-state map[*faState]struct{} assigns ≈ 600 ms vs main's
closureSetGen field compare ≈ 50 ms).

  Since nfa2Dfa is going live, I applied the structural fix you asked about:
  intern already sorts the state set by pointer to build its canonical key,
  so I dropped the seen map and dedup with slices.Compact over the sorted
  buffer instead. No per-faState field, so the memory goal is fully intact —
  and the code got simpler (−9 lines).

  Result (Nfa2Dfa geomean vs main, n=6):
  - time: +63.8% → +2.65%
  - B/op: −1.05% → −1.65%
  - allocs/op: −7.8% → −9.6%

[sayrer]

Yeah, it's all looking pretty good now.

The branch delivers on its goal. Actual retained heap (HeapAlloc after 2× GC,
matcher held live), shellstyle patterns:

  ┌──────┬────────────────┬───────────────┬───────────┬───────────┐
  │  N   │ embed resident │ main resident │   saved   │ reduction │
  ├──────┼────────────────┼───────────────┼───────────┼───────────┤
  │ 250  │      792.5 KiB │     877.8 KiB │  85.3 KiB │     −9.7% │ 
  ├──────┼────────────────┼───────────────┼───────────┼───────────┤
  │ 500  │     1486.0 KiB │    1665.1 KiB │ 179.1 KiB │    −10.8% │
  ├──────┼────────────────┼───────────────┼───────────┼───────────┤
  │ 1000 │     2971.2 KiB │    3297.9 KiB │ 326.7 KiB │     −9.9% │
  └──────┴────────────────┴───────────────┴───────────┴───────────┘
  
  Reading it

  - ~10% less resident memory, confirmed by real heap — not just the cost
    model.
  - states count is identical on both (2040 / 3821 / 7409) — the automaton
    structure is unchanged, so this is a pure per-node layout win,
    apples-to-apples.
  - ~45 bytes saved per state (resident/state: 411 B embed vs 456 B main at
    N=1000). The library's own model agrees independently (−40 B/state: 386
    vs 426), which cross-validates the measurement.

  Where the ~45 B/state comes from

  vs main (which predates the whole refactor), embed removes per-state:
  - the build-time generation fields off smallTable/faState
    (lastVisitedGen, closureGen, closureRep, closureSetGen ≈ 32 B) — the
    shared 32dc2a9 work, and
  - the *smallTable pointer + its separate heap-object header/size-class
    rounding, by embedding smallTable into faState by value (the branch's
    namesake change).

  Bottom line

  embed-smalltable now wins on all three axes vs main: ~10% smaller resident
  matchers, −27% build time + faster large-pattern matching
  (earlier benchstat), and the Nfa2Dfa path it's about to enable is back
  within ~3% of main. The memory goal is real and measured.

  Want me to push anything, port the intern fix to build-context-extract, or
  tear down the quamina-main worktree now?

[timbray]

I just posted a PR which includes the tool I've. been using to generate CSV files of the output from GetMatcherStats on a test based on TestShellStyleBuildTime.

[timbray]

Want me to push anything, port the intern fix to build-context-extract, or
tear down the quamina-main worktree now?

Maybe pull my add-research branch and see what the output looks like with your latest branch, and/or make a PR so I can do that.

[timbray]

Oh, and here's the researc/main output from before the big PR, for comparison:

2026-05-30.csv

[sayrer]

fixed by #535