Skip to content

perf: singly-linked StackEntry for resolver stack with Set-like API#526

Merged
alexander-akait merged 1 commit intomainfrom
perf/stack-entry-linked-list
Apr 17, 2026
Merged

perf: singly-linked StackEntry for resolver stack with Set-like API#526
alexander-akait merged 1 commit intomainfrom
perf/stack-entry-linked-list

Conversation

@xiaoxiaojx
Copy link
Copy Markdown
Member

@xiaoxiaojx xiaoxiaojx commented Apr 16, 2026

Summary
Replace Set<string>-based stack with a singly-linked StackEntry class that exposes a Set-compatible API (has, iteration, size, toString). Each doResolve call prepends a node instead of cloning a Set.

Comparison

original PR #443 PR #523 (claude/pr-443-...) this PR (#526)
Stack representation POJO { name, path, request, ..., parent } linked list POJO { entry, parent } linked list, hidden behind a Set<string> getter StackEntry class linked list
doResolve hot path direct POJO alloc + hasStackEntry field-compare instanceof Set branch + possible setToStack conversion + eager string build direct new StackEntry(..., parent) + field-compare has
Per-call string formatting lazy (only on recursion log) every call lazy (only on recursion log)
stack.has(entry) (public API) breaks — stack is a POJO, no .has works (but materializes a Set each read) works (O(n) list walk, no alloc)
stack instanceof Set breaks true breaks — rare in practice
stack.add(x) breaks works (on the Set view) breaks — external code doesn't mutate
Webpack ResolverCachePlugin requires update (author's own note) works (via Set conversion path) works (no change needed)

CodSpeed CI benchmarks (vs main BASE)

Benchmark PR #523 this PR (#526)
pathological-deep-stack: alias chain of 50 (warm) +50.91% +48.65%
realistic-midsize: mixed batch (warm cache) +10.29% +12.55%
resolve-to-context: directory resolve (warm) +11.82% +18.65%
symlinks: symlinks=false (warm) +10.77% +12.38%
description-files-multi (warm) +11.07% +13.13%
exports-patterns-many: 6 prefixes × 4 leaves (warm) +10.16% +11.2%
main-field: browser/module/main combos (warm) +13.68% (similar)
cache-predicate: mixed cached/uncached (warm) −45.02% ❌ +10.5% ✅

PR #523 regresses cache-predicate by 45% because its doResolve hot path adds an instanceof Set branch + _stack \|\| stack fallback + lazy Set getter materialization. For paths that hit UnsafeCachePlugin and skip the rest of the plugin chain (already microsecond-scale), that per-call overhead dominates.

This PR avoids the regression by keeping a single representation (the linked list) with no branching or materialization on the hot path — every benchmark improves, none regress.

What kind of change does this PR introduce?
perf

Did you add tests for your changes?

Does this PR introduce a breaking change?

If relevant, what needs to be documented once your changes are merged or what have you already documented?

Use of AI

@changeset-bot
Copy link
Copy Markdown

changeset-bot Bot commented Apr 16, 2026

🦋 Changeset detected

Latest commit: 27f13f1

The changes in this PR will be included in the next version bump.

This PR includes changesets to release 1 package
Name Type
enhanced-resolve Patch

Not sure what this means? Click here to learn what changesets are.

Click here if you're a maintainer who wants to add another changeset to this PR

@codspeed-hq
Copy link
Copy Markdown

codspeed-hq Bot commented Apr 16, 2026

Merging this PR will improve performance by 48.65%

⚠️ Different runtime environments detected

Some benchmarks with significant performance changes were compared across different runtime environments,
which may affect the accuracy of the results.

Open the report in CodSpeed to investigate

⚡ 24 improved benchmarks
✅ 19 untouched benchmarks

Performance Changes

Benchmark BASE HEAD Efficiency
array-alias: @ -> [preferred, fallback] (warm) 793.6 µs 717 µs +10.68%
concurrent-batch: Promise.all of 15 resolves (warm) 3.3 ms 3 ms +11.16%
prefer-absolute: absolute paths (warm) 971.1 µs 878.8 µs +10.5%
realistic-midsize: mixed batch (warm cache) 3.6 ms 3.2 ms +12.55%
deep-package-subpath: pkg/a/b/c requests (warm) 2.9 ms 2.6 ms +10.46%
deep-hierarchy: bare specifier from 10-deep dir (warm) 2.6 ms 2.3 ms +10.55%
exports-field: conditions=require,node (warm) 2.5 ms 2.3 ms +10.57%
description-files-multi: package.json + bower + component (warm) 1.3 ms 1.2 ms +13.13%
resolve-to-context: directory resolve (warm) 395.7 µs 333.5 µs +18.65%
cache-predicate: mixed cached/uncached requests (warm) 2.3 ms 2.1 ms +10.5%
pathological-deep-stack: alias chain of 50 (warm) 40.6 ms 27.3 ms +48.65%
query-fragment: ?query + #fragment mix (warm) 1.7 ms 1.6 ms +11.92%
unsafe-cache: OFF, 3x repeat 5.4 ms 4.9 ms +10.9%
self-reference: import own package name (warm) 1.3 ms 1.2 ms +11.7%
symlinks: symlinks=false (warm) 773.8 µs 688.5 µs +12.38%
exports-patterns-many: 6 prefixes x 4 leaves (warm) 5.8 ms 5.2 ms +11.2%
sync-resolver: resolveSync mixed batch (warm) 1,033.2 µs 905.2 µs +14.14%
many-extensions-miss: 5 misses + 1 hit per resolve (warm) 1.5 ms 1.3 ms +13.42%
main-field: browser/module/main combos (warm) 1.4 ms 1.3 ms +15.68%
failed-resolution: missing files + packages 2.2 ms 2 ms +11.16%
... ... ... ... ...

ℹ️ Only the first 20 benchmarks are displayed. Go to the app to view all benchmarks.


Comparing perf/stack-entry-linked-list (27f13f1) with main (b5259a0)

Open in CodSpeed

@codecov
Copy link
Copy Markdown

codecov Bot commented Apr 16, 2026

Codecov Report

❌ Patch coverage is 86.27451% with 7 lines in your changes missing coverage. Please review.
✅ Project coverage is 96.52%. Comparing base (b5259a0) to head (27f13f1).
⚠️ Report is 2 commits behind head on main.

Files with missing lines Patch % Lines
lib/Resolver.js 86.27% 7 Missing ⚠️
Additional details and impacted files
@@            Coverage Diff             @@
##             main     #526      +/-   ##
==========================================
- Coverage   96.75%   96.52%   -0.23%     
==========================================
  Files          50       50              
  Lines        2589     2622      +33     
  Branches      788      794       +6     
==========================================
+ Hits         2505     2531      +26     
- Misses         69       76       +7     
  Partials       15       15              
Flag Coverage Δ
integration 96.52% <86.27%> (-0.23%) ⬇️

Flags with carried forward coverage won't be shown. Click here to find out more.

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report? Share it here.

🚀 New features to boost your workflow:
  • ❄️ Test Analytics: Detect flaky tests, report on failures, and find test suite problems.
  • 📦 JS Bundle Analysis: Save yourself from yourself by tracking and limiting bundle sizes in JS merges.

Copy link
Copy Markdown
Member

@alexander-akait alexander-akait left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Let's merge, I don't think anyone uses add method for stack, perf improvements are looking very good,

@alexander-akait alexander-akait merged commit 5505bb2 into main Apr 17, 2026
32 of 34 checks passed
@alexander-akait alexander-akait deleted the perf/stack-entry-linked-list branch April 17, 2026 11:45
alexander-akait pushed a commit that referenced this pull request Apr 17, 2026
The StackEntry refactor (#526) replaced the internal Set-based stack
with a singly-linked list. However, the public API still allows
callers to pass a Set<string> as resolveContext.stack. When doResolve
receives a Set as parent, Set.has(stackEntry) compares by reference
and never matches the new StackEntry object, so recursion detection
silently fails.

Fix: check `parent instanceof StackEntry` and fall back to
`parent.has(stackEntry.toString())` for Set compatibility.

https://claude.ai/code/session_01TBuEDZmTzjKYzebY26ZkL1
alexander-akait pushed a commit that referenced this pull request Apr 17, 2026
… set

`doResolve` runs once per plugin step (~10-15 per resolve). When
`resolveContext.log` is unset — the production hot path — the inner
context is structurally identical to the parent save for `stack`, so we
can mutate `stack` in place before the hook call and restore it after,
avoiding one options-literal + one `createInnerContext` return object
per step.

`forEachBail` and tapable's `AsyncSeriesBailHook` drive sibling calls
strictly sequentially, so no two call sites read `resolveContext.stack`
concurrently. The logging branch remains unchanged, since it still needs
the deferred header wrapper from `createInnerContext`.

Benchmark on top of main (which already has the singly-linked stack
from #526), median of 5 runs under the repo's `--no-opt --predictable`
flags:

  concurrent-batch (15 parallel resolves):  1.075 -> 1.045 ms  (+2.8%)

All 970 tests pass, including the recursion detection suite.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants