feat: optimize updateParent by batching dependency sorting (#20204)

xiaoxiaojx · web-flow · commit 4baab4e5778c · 2025-12-05T13:43:23.000+03:00
diff --git a/.changeset/fast-parents-sort.md b/.changeset/fast-parents-sort.md
@@ -0,0 +1,5 @@
+---
+"webpack": minor
+---
+
+Optimize dependency sorting in updateParent: sort each module only once by deferring to finishUpdateParent(), and reduce traversal count in sortWithSourceOrder by caching WeakMap values upfront.
diff --git a/lib/ModuleGraph.js b/lib/ModuleGraph.js
@@ -169,6 +169,12 @@ class ModuleGraph {
 		 * @private
 		 */
 		this._dependencySourceOrderMap = new WeakMap();
+
+		/**
+		 * @type {Set<Module>}
+		 * @private
+		 */
+		this._modulesNeedingSort = new Set();
 	}
 
 	/**
@@ -330,17 +336,28 @@ class ModuleGraph {
 				sub: originSourceOrder
 			});
 
+			// Save for later batch sorting
+			this._modulesNeedingSort.add(parentModule);
+		}
+	}
+
+	/**
+	 * @returns {void}
+	 */
+	finishUpdateParent() {
+		if (this._modulesNeedingSort.size === 0) {
+			return;
+		}
+		for (const mod of this._modulesNeedingSort) {
 			// If dependencies like HarmonyImportSideEffectDependency and HarmonyImportSpecifierDependency have a SourceOrder,
 			// we sort based on it; otherwise, we preserve the original order.
 			sortWithSourceOrder(
-				parentModule.dependencies,
-				this._dependencySourceOrderMap
+				mod.dependencies,
+				this._dependencySourceOrderMap,
+				(dep, index) => this.setParentDependenciesBlockIndex(dep, index)
 			);
-
-			for (const [index, dep] of parentModule.dependencies.entries()) {
-				this.setParentDependenciesBlockIndex(dep, index);
-			}
 		}
+		this._modulesNeedingSort.clear();
 	}
 
 	/**
diff --git a/lib/optimize/SideEffectsFlagPlugin.js b/lib/optimize/SideEffectsFlagPlugin.js
@@ -381,6 +381,7 @@ class SideEffectsFlagPlugin {
 						for (const module of modules) {
 							optimizeIncomingConnections(module);
 						}
+						moduleGraph.finishUpdateParent();
 						logger.timeEnd("update dependencies");
 					}
 				);
diff --git a/lib/util/comparators.js b/lib/util/comparators.js
@@ -511,85 +511,62 @@ const compareChunksNatural = (chunkGraph) => {
  * https://github.com/webpack/webpack/pull/19686
  * @param {Dependency[]} dependencies dependencies
  * @param {WeakMap<Dependency, DependencySourceOrder>} dependencySourceOrderMap dependency source order map
+ * @param {((dep: Dependency, index: number) => void)=} onDependencyReSort optional callback to set index for each dependency
  * @returns {void}
  */
-const sortWithSourceOrder = (dependencies, dependencySourceOrderMap) => {
-	/**
-	 * @param {Dependency} dep dependency
-	 * @returns {number} source order
-	 */
-	const getSourceOrder = (dep) => {
-		if (dependencySourceOrderMap.has(dep)) {
-			const { main } = /** @type {DependencySourceOrder} */ (
-				dependencySourceOrderMap.get(dep)
-			);
-			return main;
-		}
-		return /** @type {number} */ (
-			/** @type {ModuleDependency} */ (dep).sourceOrder
-		);
-	};
-
-	/**
-	 * If the sourceOrder is a number, it means the dependency needs to be sorted.
-	 * @param {number | undefined} sourceOrder sourceOrder
-	 * @returns {boolean} needReSort
-	 */
-	const needReSort = (sourceOrder) => {
-		if (typeof sourceOrder === "number") {
-			return true;
-		}
-		return false;
-	};
-
-	// Extract dependencies with sourceOrder and sort them
+const sortWithSourceOrder = (
+	dependencies,
+	dependencySourceOrderMap,
+	onDependencyReSort
+) => {
+	/** @type {{dep: Dependency, main: number, sub: number}[]} */
 	const withSourceOrder = [];
+	/** @type {number[]} */
+	const positions = [];
 
-	// First pass: collect dependencies with sourceOrder
 	for (let i = 0; i < dependencies.length; i++) {
 		const dep = dependencies[i];
-		const sourceOrder = getSourceOrder(dep);
-
-		if (needReSort(sourceOrder)) {
-			withSourceOrder.push({ dep, sourceOrder, originalIndex: i });
+		const cached = dependencySourceOrderMap.get(dep);
+
+		if (cached) {
+			positions.push(i);
+			withSourceOrder.push({
+				dep,
+				main: cached.main,
+				sub: cached.sub
+			});
+		} else {
+			const sourceOrder = /** @type {number | undefined} */ (
+				/** @type {ModuleDependency} */ (dep).sourceOrder
+			);
+			if (typeof sourceOrder === "number") {
+				positions.push(i);
+				withSourceOrder.push({
+					dep,
+					main: sourceOrder,
+					sub: 0
+				});
+			}
 		}
 	}
 
 	if (withSourceOrder.length <= 1) {
 		return;
 	}
 
-	// Sort dependencies with sourceOrder
 	withSourceOrder.sort((a, b) => {
-		// Handle both dependencies in map case
-		if (
-			dependencySourceOrderMap.has(a.dep) &&
-			dependencySourceOrderMap.has(b.dep)
-		) {
-			const { main: mainA, sub: subA } = /** @type {DependencySourceOrder} */ (
-				dependencySourceOrderMap.get(a.dep)
-			);
-			const { main: mainB, sub: subB } = /** @type {DependencySourceOrder} */ (
-				dependencySourceOrderMap.get(b.dep)
-			);
-			if (mainA === mainB) {
-				return compareNumbers(subA, subB);
-			}
-			return compareNumbers(mainA, mainB);
+		if (a.main !== b.main) {
+			return compareNumbers(a.main, b.main);
 		}
-
-		return compareNumbers(a.sourceOrder, b.sourceOrder);
+		return compareNumbers(a.sub, b.sub);
 	});
 
-	// Second pass: build result array
-	let sortedIndex = 0;
-	for (let i = 0; i < dependencies.length; i++) {
-		const dep = dependencies[i];
-		const sourceOrder = getSourceOrder(dep);
-
-		if (needReSort(sourceOrder)) {
-			dependencies[i] = withSourceOrder[sortedIndex].dep;
-			sortedIndex++;
+	// Second pass: place sorted deps back to original positions
+	for (let i = 0; i < positions.length; i++) {
+		const depIndex = positions[i];
+		dependencies[depIndex] = withSourceOrder[i].dep;
+		if (onDependencyReSort) {
+			onDependencyReSort(dependencies[depIndex], depIndex);
 		}
 	}
 };
diff --git a/types.d.ts b/types.d.ts
@@ -10704,6 +10704,7 @@ declare class ModuleGraph {
 		connection?: ModuleGraphConnection,
 		parentModule?: Module
 	): void;
+	finishUpdateParent(): void;
 	removeConnection(dependency: Dependency): void;
 	addExplanation(dependency: Dependency, explanation: string): void;
 	cloneModuleAttributes(sourceModule: Module, targetModule: Module): void;
@@ -19357,7 +19358,8 @@ declare namespace exports {
 			export let keepOriginalOrder: <T>(iterable: Iterable<T>) => Comparator<T>;
 			export let sortWithSourceOrder: (
 				dependencies: Dependency[],
-				dependencySourceOrderMap: WeakMap<Dependency, DependencySourceOrder>
+				dependencySourceOrderMap: WeakMap<Dependency, DependencySourceOrder>,
+				onDependencyReSort?: (dep: Dependency, index: number) => void
 			) => void;
 		}
 		export namespace runtime {

-Original file line number
+Diff line change
@@ @@ -0,0 +1,5 @@ @@
 +---
 +"webpack": minor
 +---
++
 +Optimize dependency sorting in updateParent: sort each module only once by deferring to finishUpdateParent(), and reduce traversal count in sortWithSourceOrder by caching WeakMap values upfront.
Original file line number	Diff line number	Diff line change
`@@ -381,6 +381,7 @@ class SideEffectsFlagPlugin {`
`381`	`381`	`for (const module of modules) {`
`382`	`382`	`optimizeIncomingConnections(module);`
`383`	`383`	`}`
	`384`	`+ moduleGraph.finishUpdateParent();`
`384`	`385`	`logger.timeEnd("update dependencies");`
`385`	`386`	`}`
`386`	`387`	`);`