Visitar URL original
perf: hybrid recursive walker w/ iterative fallback for side-effects … · webpack/webpack@aa20f65 · GitHub
Skip to content

Commit aa20f65

Browse files
perf: hybrid recursive walker w/ iterative fallback for side-effects state
The previous iterative-only walker fixed the regression but still ran ~2x slower than the pre-#20993 recursive code on short-to-medium chains because every descent went through explicit array-stack operations instead of native call frames. Restructure the walk as: walkSideEffectsRecursive(mod, depth) if depth >= SIDE_EFFECTS_RECURSION_LIMIT (2000): -> walkSideEffectsIterative(mod) # stack-safe tail else: direct recursion, 1 native frame per module The recursive form also folds the descent through HarmonyImportSideEffectDependency.getModuleEvaluationSideEffectsState directly into the loop, so each module costs one V8 stack frame instead of two. That is why the limit can be set as high as 2000 without risking the #20986 overflow (which triggered at ~1300 modules under the old two-frame pattern). Microbench (best of 7 runs, side-effect-free linear chain): chain BEFORE AFTER NOW 10 34.0 ms 190.8 ms 40.1 ms 100 48.5 ms 191.3 ms 59.0 ms 1000 60.3 ms 231.8 ms 69.8 ms 20000 CRASH 111.5 ms 66.3 ms Within 16-22% of the pre-regression recursive code on short / medium chains, ~3x faster than the merged generator trampoline, and still stack-safe at 20000 modules. A new unit test exercises the recursive-to-iterative crossover with a bailout planted deep in the iterative tail.
1 parent b3893ec commit aa20f65

3 files changed

Lines changed: 215 additions & 25 deletions

File tree

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,5 @@
1+
---
2+
"webpack": patch
3+
---
4+
5+
Rewrite `NormalModule#getSideEffectsConnectionState` walk as an allocation-light iterative loop instead of a generator trampoline, restoring rebuild performance lost in #20993 while keeping deep import chains stack-safe.

‎lib/NormalModule.js‎

Lines changed: 164 additions & 25 deletions
Original file line numberDiff line numberDiff line change
@@ -86,7 +86,6 @@ const parseJson = require("./util/parseJson");
8686
/** @typedef {import("./Module").UnsafeCacheData} UnsafeCacheData */
8787
/** @typedef {import("./ModuleGraph")} ModuleGraph */
8888
/** @typedef {import("./ModuleGraphConnection").ConnectionState} ConnectionState */
89-
/** @typedef {Iterator<SideEffectsWalk, ConnectionState, ConnectionState>} SideEffectsWalk */
9089
/** @typedef {import("./NormalModuleFactory")} NormalModuleFactory */
9190
/** @typedef {import("./NormalModuleFactory").NormalModuleTypes} NormalModuleTypes */
9291
/** @typedef {import("./NormalModuleFactory").ParserByType} ParserByType */
@@ -157,14 +156,13 @@ const recordSideEffectsBailout = (mod, moduleGraph, dep) => {
157156
};
158157

159158
/**
160-
* Generator form of `getSideEffectsConnectionState` — descends through
161-
* `HarmonyImportSideEffectDependency` via `yield` so the trampoline in
162-
* `getSideEffectsConnectionState` can drive the walk iteratively (#20986).
163-
* @param {NormalModule} mod the module being evaluated
164-
* @param {ModuleGraph} moduleGraph the module graph
165-
* @returns {SideEffectsWalk} the generator
159+
* Resolves a module's side-effects state without descending into its
160+
* dependencies. Returns the state when known, or `undefined` when the caller
161+
* must walk the module's dependencies to compute it.
162+
* @param {NormalModule} mod the module
163+
* @returns {ConnectionState | undefined} the state, or `undefined` to descend
166164
*/
167-
function* walkSideEffects(mod, moduleGraph) {
165+
const sideEffectsFastPath = (mod) => {
168166
if (mod.factoryMeta !== undefined) {
169167
if (mod.factoryMeta.sideEffectFree) return false;
170168
if (mod.factoryMeta.sideEffectFree === false) return true;
@@ -175,6 +173,161 @@ function* walkSideEffects(mod, moduleGraph) {
175173
if (mod._isEvaluatingSideEffects) {
176174
return ModuleGraphConnection.CIRCULAR_CONNECTION;
177175
}
176+
return undefined;
177+
};
178+
179+
// Maximum recursive descent depth before switching to the iterative walker.
180+
// #20986 reported overflow around 1300 modules in webpack 5.107.0 where each
181+
// step consumed two stack frames (`NormalModule.getSideEffectsConnectionState`
182+
// plus `HarmonyImportSideEffectDependency.getModuleEvaluationSideEffectsState`).
183+
// `walkSideEffectsRecursive` folds the second call into the first and uses
184+
// one frame per module, so this limit caps the native stack at half the depth
185+
// where the original code overflowed — well within the safe range across
186+
// platforms while keeping the common (shallow) case purely recursive.
187+
const SIDE_EFFECTS_RECURSION_LIMIT = 2000;
188+
189+
/**
190+
* Iterative form of the side-effects walker. Used as a fallback once the
191+
* recursive form reaches `SIDE_EFFECTS_RECURSION_LIMIT` so deep chains
192+
* (#20986) don't overflow V8's stack. Safe to enter while ancestors set
193+
* `_isEvaluatingSideEffects` on their own modules — those are treated as
194+
* `CIRCULAR_CONNECTION` if revisited, matching the original recursive
195+
* behavior.
196+
* @param {NormalModule} rootMod the module to walk
197+
* @param {ModuleGraph} moduleGraph the module graph
198+
* @returns {ConnectionState} the side-effects connection state
199+
*/
200+
const walkSideEffectsIterative = (rootMod, moduleGraph) => {
201+
const SideEffectDep = getHarmonyImportSideEffectDependency();
202+
203+
/** @type {NormalModule[]} */
204+
const modStack = [rootMod];
205+
/** @type {Dependency[][]} */
206+
const depsStack = [rootMod.dependencies];
207+
const indexStack = [0];
208+
/** @type {ConnectionState[]} */
209+
const currentStack = [false];
210+
rootMod._isEvaluatingSideEffects = true;
211+
212+
/**
213+
* Result from a just-popped child frame, to be applied to the new
214+
* top's current dep. `undefined` means "no pending; advance".
215+
* @type {ConnectionState | undefined}
216+
*/
217+
let pending;
218+
219+
while (modStack.length > 0) {
220+
const top = modStack.length - 1;
221+
const deps = depsStack[top];
222+
223+
if (pending !== undefined) {
224+
const state = pending;
225+
pending = undefined;
226+
const dep = deps[indexStack[top]];
227+
228+
if (state === true) {
229+
recordSideEffectsBailout(modStack[top], moduleGraph, dep);
230+
modStack[top]._isEvaluatingSideEffects = false;
231+
modStack.pop();
232+
depsStack.pop();
233+
indexStack.pop();
234+
currentStack.pop();
235+
pending = true;
236+
continue;
237+
}
238+
if (state !== ModuleGraphConnection.CIRCULAR_CONNECTION) {
239+
currentStack[top] = ModuleGraphConnection.addConnectionStates(
240+
currentStack[top],
241+
state
242+
);
243+
}
244+
indexStack[top]++;
245+
}
246+
247+
let descended = false;
248+
while (indexStack[top] < deps.length) {
249+
const dep = deps[indexStack[top]];
250+
/** @type {ConnectionState} */
251+
let state;
252+
253+
if (dep instanceof SideEffectDep) {
254+
const refModule = moduleGraph.getModule(dep);
255+
if (!refModule) {
256+
state = true;
257+
} else if (refModule instanceof NormalModule) {
258+
const refFast = sideEffectsFastPath(refModule);
259+
if (refFast !== undefined) {
260+
state = refFast;
261+
} else {
262+
refModule._isEvaluatingSideEffects = true;
263+
modStack.push(refModule);
264+
depsStack.push(refModule.dependencies);
265+
indexStack.push(0);
266+
currentStack.push(false);
267+
descended = true;
268+
break;
269+
}
270+
} else {
271+
state = refModule.getSideEffectsConnectionState(moduleGraph);
272+
}
273+
} else {
274+
state = dep.getModuleEvaluationSideEffectsState(moduleGraph);
275+
}
276+
277+
if (state === true) {
278+
recordSideEffectsBailout(modStack[top], moduleGraph, dep);
279+
modStack[top]._isEvaluatingSideEffects = false;
280+
modStack.pop();
281+
depsStack.pop();
282+
indexStack.pop();
283+
currentStack.pop();
284+
pending = true;
285+
descended = true;
286+
break;
287+
}
288+
if (state !== ModuleGraphConnection.CIRCULAR_CONNECTION) {
289+
currentStack[top] = ModuleGraphConnection.addConnectionStates(
290+
currentStack[top],
291+
state
292+
);
293+
}
294+
indexStack[top]++;
295+
}
296+
297+
if (descended) continue;
298+
299+
modStack[top]._isEvaluatingSideEffects = false;
300+
pending = currentStack[top];
301+
modStack.pop();
302+
depsStack.pop();
303+
indexStack.pop();
304+
currentStack.pop();
305+
}
306+
307+
// When caching is implemented here, make sure to not cache when
308+
// at least one circular connection was folded into the result.
309+
return /** @type {ConnectionState} */ (pending);
310+
};
311+
312+
/**
313+
* Recursive form of the side-effects walker. Folds the descent through
314+
* `HarmonyImportSideEffectDependency.getModuleEvaluationSideEffectsState`
315+
* directly into the loop so each module costs only one V8 stack frame
316+
* (vs. two in the original recursive code). Falls back to
317+
* `walkSideEffectsIterative` once depth reaches
318+
* `SIDE_EFFECTS_RECURSION_LIMIT` to keep deep chains stack-safe (#20986).
319+
* @param {NormalModule} mod the module being walked
320+
* @param {ModuleGraph} moduleGraph the module graph
321+
* @param {number} depth current recursion depth
322+
* @returns {ConnectionState} the side-effects connection state
323+
*/
324+
const walkSideEffectsRecursive = (mod, moduleGraph, depth) => {
325+
const fast = sideEffectsFastPath(mod);
326+
if (fast !== undefined) return fast;
327+
328+
if (depth >= SIDE_EFFECTS_RECURSION_LIMIT) {
329+
return walkSideEffectsIterative(mod, moduleGraph);
330+
}
178331

179332
const SideEffectDep = getHarmonyImportSideEffectDependency();
180333
mod._isEvaluatingSideEffects = true;
@@ -189,7 +342,7 @@ function* walkSideEffects(mod, moduleGraph) {
189342
if (!refModule) {
190343
state = true;
191344
} else if (refModule instanceof NormalModule) {
192-
state = yield walkSideEffects(refModule, moduleGraph);
345+
state = walkSideEffectsRecursive(refModule, moduleGraph, depth + 1);
193346
} else {
194347
state = refModule.getSideEffectsConnectionState(moduleGraph);
195348
}
@@ -211,7 +364,7 @@ function* walkSideEffects(mod, moduleGraph) {
211364
// When caching is implemented here, make sure to not cache when
212365
// at least one circular connection was folded into `current`.
213366
return current;
214-
}
367+
};
215368

216369
const ABSOLUTE_PATH_REGEX = /^(?:[a-z]:\\|\\\\|\/)/i;
217370

@@ -1539,21 +1692,7 @@ class NormalModule extends Module {
15391692
* @returns {ConnectionState} how this module should be connected to referencing modules when consumed for side-effects only
15401693
*/
15411694
getSideEffectsConnectionState(moduleGraph) {
1542-
// Trampoline `walkSideEffects` so the descent doesn't consume the
1543-
// call stack (#20986).
1544-
const stack = [walkSideEffects(this, moduleGraph)];
1545-
/** @type {ConnectionState} */
1546-
let r = false;
1547-
while (stack.length > 0) {
1548-
const step = stack[stack.length - 1].next(r);
1549-
if (step.done) {
1550-
stack.pop();
1551-
r = step.value;
1552-
} else {
1553-
stack.push(step.value);
1554-
}
1555-
}
1556-
return r;
1695+
return walkSideEffectsRecursive(this, moduleGraph, 0);
15571696
}
15581697

15591698
/**

‎test/NormalModule.unittest.js‎

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -429,6 +429,18 @@ describe("NormalModule", () => {
429429
expect(modules[0].getSideEffectsConnectionState(moduleGraph)).toBe(false);
430430
});
431431

432+
it("propagates bailout across the recursive→iterative crossover", () => {
433+
// Chain length is chosen to exceed `SIDE_EFFECTS_RECURSION_LIMIT`,
434+
// so the walker recurses for the head of the chain and switches
435+
// to iteration deeper in. A bailout deep in the iterative tail
436+
// must still propagate all the way back to module 0.
437+
const { modules, moduleGraph } = buildChain(5000);
438+
modules[4500].buildMeta = { sideEffectFree: false };
439+
expect(modules[0].getSideEffectsConnectionState(moduleGraph)).toBe(true);
440+
expect(modules[0]._isEvaluatingSideEffects).toBe(false);
441+
expect(modules[4499]._isEvaluatingSideEffects).toBe(false);
442+
});
443+
432444
it("detects cycles in the side-effect graph", () => {
433445
const { modules, moduleGraph } = buildChain(50);
434446
// close the loop: last module's dep points to modules[0]
@@ -468,5 +480,39 @@ describe("NormalModule", () => {
468480
);
469481
}
470482
});
483+
484+
it("aggregates state across branching deps", () => {
485+
// Diamond: root depends on two side-effect-free leaves.
486+
const make = (id) => {
487+
const mod = new NormalModule({
488+
type: "javascript/auto",
489+
request: `/${id}`,
490+
userRequest: `/${id}`,
491+
rawRequest: id,
492+
loaders: [],
493+
resource: `/${id}`,
494+
parser: { parse() {} },
495+
generator: null,
496+
resolveOptions: {}
497+
});
498+
mod.buildMeta = { sideEffectFree: true };
499+
mod.dependencies = [];
500+
return mod;
501+
};
502+
const root = make("root");
503+
const a = make("a");
504+
const b = make("b");
505+
const depA = new HarmonyImportSideEffectDependency("a", 0, "evaluation");
506+
const depB = new HarmonyImportSideEffectDependency("b", 1, "evaluation");
507+
root.dependencies = [depA, depB];
508+
const moduleGraph = {
509+
getModule: (dep) => (dep === depA ? a : dep === depB ? b : undefined),
510+
getOptimizationBailout: () => []
511+
};
512+
expect(root.getSideEffectsConnectionState(moduleGraph)).toBe(false);
513+
expect(root._isEvaluatingSideEffects).toBe(false);
514+
expect(a._isEvaluatingSideEffects).toBe(false);
515+
expect(b._isEvaluatingSideEffects).toBe(false);
516+
});
471517
});
472518
});

0 commit comments

Comments
 (0)