Skip to content

Commit 45afb50

Browse files
committed
perf(split-chunks): bound intersection expansion
1 parent af334f1 commit 45afb50

3 files changed

Lines changed: 93 additions & 20 deletions

File tree

‎lib/optimize/SplitChunksPlugin.js‎

Lines changed: 41 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -355,6 +355,7 @@ const MAX_INTERSECTION_PAIRS = 500000;
355355
const MAX_INTERSECTION_COMPARISONS = 16000000;
356356
const MAX_INTERSECTION_PROPAGATION_CHECKS = 500000;
357357
const MAX_INTERSECTION_PROPAGATION_COMPARISONS = 16000000;
358+
const MAX_INTERSECTION_PROPAGATION_EXPANSIONS = 500000;
358359

359360
/**
360361
* Returns normalized representation.
@@ -1010,20 +1011,26 @@ class SplitChunksPlugin {
10101011
const getChunkSetsInGraph = memoize(() => {
10111012
/** @type {Map<bigint, ChunkSet>} */
10121013
const chunkSetsInGraph = new Map();
1014+
/** @type {Map<bigint, number>} */
1015+
const chunkSetModuleCounts = new Map();
10131016
/** @type {ChunkSet} */
10141017
const singleChunkSets = new Set();
10151018
for (const module of compilation.modules) {
10161019
const chunks = chunkGraph.getModuleChunksIterable(module);
10171020
const chunksKey = getKey(chunks);
10181021
if (typeof chunksKey === "bigint") {
1022+
chunkSetModuleCounts.set(
1023+
chunksKey,
1024+
(chunkSetModuleCounts.get(chunksKey) || 0) + 1
1025+
);
10191026
if (!chunkSetsInGraph.has(chunksKey)) {
10201027
chunkSetsInGraph.set(chunksKey, new Set(chunks));
10211028
}
10221029
} else {
10231030
singleChunkSets.add(chunksKey);
10241031
}
10251032
}
1026-
return { chunkSetsInGraph, singleChunkSets };
1033+
return { chunkSetsInGraph, singleChunkSets, chunkSetModuleCounts };
10271034
});
10281035

10291036
/**
@@ -1055,6 +1062,8 @@ class SplitChunksPlugin {
10551062
const getExportsChunkSetsInGraph = memoize(() => {
10561063
/** @type {ChunkSetsInGraph} */
10571064
const chunkSetsInGraph = new Map();
1065+
/** @type {Map<bigint, number>} */
1066+
const chunkSetModuleCounts = new Map();
10581067
/** @type {ChunkSet} */
10591068
const singleChunkSets = new Set();
10601069
for (const module of compilation.modules) {
@@ -1065,13 +1074,17 @@ class SplitChunksPlugin {
10651074
singleChunkSets.add(chunks[0]);
10661075
} else {
10671076
const chunksKey = /** @type {bigint} */ (getKey(chunks));
1077+
chunkSetModuleCounts.set(
1078+
chunksKey,
1079+
(chunkSetModuleCounts.get(chunksKey) || 0) + 1
1080+
);
10681081
if (!chunkSetsInGraph.has(chunksKey)) {
10691082
chunkSetsInGraph.set(chunksKey, new Set(chunks));
10701083
}
10711084
}
10721085
}
10731086
}
1074-
return { chunkSetsInGraph, singleChunkSets };
1087+
return { chunkSetsInGraph, singleChunkSets, chunkSetModuleCounts };
10751088
});
10761089

10771090
/**
@@ -1149,9 +1162,13 @@ class SplitChunksPlugin {
11491162
/**
11501163
* Discovers intersections and associates them with containing original sets.
11511164
* @param {ChunkSetsInGraph} chunkSets original chunk sets
1165+
* @param {Map<bigint, number>} chunkSetModuleCounts module count by original set key
11521166
* @returns {Map<bigint, ChunkSet[]>} intersections grouped by original set key
11531167
*/
1154-
const getIntersectionsByChunkSet = (chunkSets) => {
1168+
const getIntersectionsByChunkSet = (
1169+
chunkSets,
1170+
chunkSetModuleCounts
1171+
) => {
11551172
/** @type {Map<bigint, ChunkSet>} */
11561173
const chunkSetsByMembership = new Map();
11571174
for (const [key, chunks] of chunkSets) {
@@ -1169,31 +1186,42 @@ class SplitChunksPlugin {
11691186
const propagation = associateIntersections(
11701187
chunkSets,
11711188
result.entries,
1189+
chunkSetModuleCounts,
11721190
{
11731191
maximumChecks: MAX_INTERSECTION_PROPAGATION_CHECKS,
1174-
maximumComparisons: MAX_INTERSECTION_PROPAGATION_COMPARISONS
1192+
maximumComparisons: MAX_INTERSECTION_PROPAGATION_COMPARISONS,
1193+
maximumExpansions: MAX_INTERSECTION_PROPAGATION_EXPANSIONS
11751194
}
11761195
);
11771196
logger.debug(
1178-
"Prepared %d additional split chunk intersections from %d pairs and %d comparisons%s; propagated with %d checks and %d comparisons%s",
1197+
"Prepared %d additional split chunk intersections from %d pairs and %d comparisons%s; propagated with %d checks, %d comparisons, and %d downstream visits%s",
11791198
result.sets.length,
11801199
result.pairs,
11811200
result.comparisons,
11821201
result.limited ? " (limited)" : "",
11831202
propagation.checks,
11841203
propagation.comparisons,
1204+
propagation.expansions,
11851205
propagation.limited ? " (limited)" : ""
11861206
);
11871207
return propagation.intersectionsByOriginalKey;
11881208
};
1189-
const getIntersectionsByChunkSetKey = memoize(() =>
1190-
getIntersectionsByChunkSet(getChunkSetsInGraph().chunkSetsInGraph)
1191-
);
1192-
const getExportsIntersectionsByChunkSetKey = memoize(() =>
1193-
getIntersectionsByChunkSet(
1194-
getExportsChunkSetsInGraph().chunkSetsInGraph
1195-
)
1196-
);
1209+
const getIntersectionsByChunkSetKey = memoize(() => {
1210+
const { chunkSetsInGraph, chunkSetModuleCounts } =
1211+
getChunkSetsInGraph();
1212+
return getIntersectionsByChunkSet(
1213+
chunkSetsInGraph,
1214+
chunkSetModuleCounts
1215+
);
1216+
});
1217+
const getExportsIntersectionsByChunkSetKey = memoize(() => {
1218+
const { chunkSetsInGraph, chunkSetModuleCounts } =
1219+
getExportsChunkSetsInGraph();
1220+
return getIntersectionsByChunkSet(
1221+
chunkSetsInGraph,
1222+
chunkSetModuleCounts
1223+
);
1224+
});
11971225

11981226
/** @typedef {(ChunkSet | Chunk)[]} Combinations */
11991227

‎lib/util/SetHelpers.js‎

Lines changed: 31 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -145,6 +145,7 @@ const findIntersections = (setsByKey, options) => {
145145
* @property {Map<bigint, Set<T>[]>} intersectionsByOriginalKey additional subsets by original set key
146146
* @property {number} checks the number of possible containing sets checked
147147
* @property {number} comparisons the maximum number of membership checks performed
148+
* @property {number} expansions the weighted number of downstream visits
148149
* @property {boolean} limited whether propagation reached a limit
149150
*/
150151

@@ -155,13 +156,20 @@ const findIntersections = (setsByKey, options) => {
155156
* @template T
156157
* @param {Map<bigint, Set<T>>} originalsByKey original sets
157158
* @param {{ key: bigint, set: Set<T> }[]} intersections discovered intersections
159+
* @param {Map<bigint, number>} originalWeightsByKey downstream visit weight by original set key
158160
* @param {object} options propagation options
159161
* @param {number} options.maximumChecks maximum number of possible containing sets checked
160162
* @param {number} options.maximumComparisons maximum number of membership checks
163+
* @param {number} options.maximumExpansions maximum weighted number of downstream visits
161164
* @returns {AssociateIntersectionsResult<T>} intersections grouped by original set key
162165
*/
163-
const associateIntersections = (originalsByKey, intersections, options) => {
164-
const { maximumChecks, maximumComparisons } = options;
166+
const associateIntersections = (
167+
originalsByKey,
168+
intersections,
169+
originalWeightsByKey,
170+
options
171+
) => {
172+
const { maximumChecks, maximumComparisons, maximumExpansions } = options;
165173
/** @type {Map<T, bigint[]>} */
166174
const originalKeysByItem = new Map();
167175
for (const [key, original] of originalsByKey) {
@@ -183,6 +191,7 @@ const associateIntersections = (originalsByKey, intersections, options) => {
183191
const intersectionsByOriginalKey = new Map();
184192
let checks = 0;
185193
let comparisons = 0;
194+
let expansions = 0;
186195
let limited = false;
187196

188197
search: for (const { set: intersection } of orderedIntersections) {
@@ -207,6 +216,7 @@ const associateIntersections = (originalsByKey, intersections, options) => {
207216
// limit cannot leave an intersection attached to only some originals.
208217
/** @type {bigint[]} */
209218
const matches = [];
219+
let candidateExpansions = 0;
210220
for (const key of possibleOriginalKeys) {
211221
const original = /** @type {Set<T>} */ (originalsByKey.get(key));
212222
if (original.size <= intersection.size) continue;
@@ -219,8 +229,19 @@ const associateIntersections = (originalsByKey, intersections, options) => {
219229
}
220230
checks++;
221231
comparisons += intersection.size;
222-
if (isSubset(original, intersection)) matches.push(key);
232+
if (isSubset(original, intersection)) {
233+
const weightedExpansions =
234+
candidateExpansions +
235+
/** @type {number} */ (originalWeightsByKey.get(key));
236+
if (expansions + weightedExpansions > maximumExpansions) {
237+
limited = true;
238+
break search;
239+
}
240+
candidateExpansions = weightedExpansions;
241+
matches.push(key);
242+
}
223243
}
244+
expansions += candidateExpansions;
224245
for (const key of matches) {
225246
const intersectionsForOriginal = intersectionsByOriginalKey.get(key);
226247
if (intersectionsForOriginal === undefined) {
@@ -231,7 +252,13 @@ const associateIntersections = (originalsByKey, intersections, options) => {
231252
}
232253
}
233254

234-
return { intersectionsByOriginalKey, checks, comparisons, limited };
255+
return {
256+
intersectionsByOriginalKey,
257+
checks,
258+
comparisons,
259+
expansions,
260+
limited
261+
};
235262
};
236263

237264
/**

‎test/SetHelpers.unittest.js‎

Lines changed: 21 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -145,16 +145,25 @@ describe("SetHelpers", () => {
145145
new Set([1, i + 10])
146146
]);
147147
const matchingKey = BigInt("1000");
148+
/** @type {[bigint, number][]} */
149+
const weights = unrelated.map(([key]) => [key, 1]);
150+
weights.push([matchingKey, 7]);
148151
const result = associateIntersections(
149152
new Map([...unrelated, [matchingKey, new Set([1, 2, 3])]]),
150153
[{ key: BigInt("3"), set: new Set([1, 2]) }],
151-
{ maximumChecks: 10, maximumComparisons: 10 }
154+
new Map(weights),
155+
{
156+
maximumChecks: 10,
157+
maximumComparisons: 10,
158+
maximumExpansions: 10
159+
}
152160
);
153161
expect(result.intersectionsByOriginalKey.get(matchingKey)).toEqual([
154162
new Set([1, 2])
155163
]);
156164
expect(result.checks).toBe(1);
157165
expect(result.comparisons).toBe(2);
166+
expect(result.expansions).toBe(7);
158167
expect(result.limited).toBe(false);
159168
});
160169

@@ -165,10 +174,19 @@ describe("SetHelpers", () => {
165174
[BigInt("2"), new Set([1, 2, 4])]
166175
]),
167176
[{ key: BigInt("3"), set: new Set([1, 2]) }],
168-
{ maximumChecks: 1, maximumComparisons: 10 }
177+
new Map([
178+
[BigInt("1"), 1],
179+
[BigInt("2"), 1]
180+
]),
181+
{
182+
maximumChecks: 10,
183+
maximumComparisons: 10,
184+
maximumExpansions: 1
185+
}
169186
);
170187
expect(result.intersectionsByOriginalKey.size).toBe(0);
171-
expect(result.checks).toBe(1);
188+
expect(result.checks).toBe(2);
189+
expect(result.expansions).toBe(0);
172190
expect(result.limited).toBe(true);
173191
});
174192
});

0 commit comments

Comments
 (0)