Skip to content

Commit 5a1884d

Browse files
committed
feat(split-chunks): discover shared chunk intersections
1 parent 4448f8b commit 5a1884d

17 files changed

Lines changed: 484 additions & 23 deletions

File tree

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,5 @@
1+
---
2+
"webpack": minor
3+
---
4+
5+
Discover shared chunk intersections before enforcing splitChunks size limits.

‎lib/optimize/SplitChunksPlugin.js‎

Lines changed: 118 additions & 23 deletions
Original file line numberDiff line numberDiff line change
@@ -9,7 +9,7 @@ const Chunk = require("../Chunk");
99
const { STAGE_ADVANCED } = require("../OptimizationStages");
1010
const WebpackError = require("../errors/WebpackError");
1111
const { requestToId } = require("../ids/IdHelpers");
12-
const { isSubset } = require("../util/SetHelpers");
12+
const { findIntersections, isSubset } = require("../util/SetHelpers");
1313
const SortableSet = require("../util/SortableSet");
1414
const {
1515
compareIterables,
@@ -343,6 +343,12 @@ const ALL_CHUNK_FILTER = (_chunk) => true;
343343
/** Placeholder until a chunk set group is filled and its signatures are written. */
344344
const EMPTY_SIGNATURES = new Uint32Array(0);
345345

346+
const MIN_INTERSECTION_CHUNKS = 2;
347+
const MAX_INTERSECTION_CANDIDATE_FACTOR = 2;
348+
const MAX_INTERSECTION_CANDIDATES = 4096;
349+
const MAX_INTERSECTION_PAIRS = 500000;
350+
const MAX_INTERSECTION_COMPARISONS = 16000000;
351+
346352
/**
347353
* Returns normalized representation.
348354
* @param {OptimizationSplitChunksSizes | undefined} value the sizes
@@ -951,6 +957,7 @@ class SplitChunksPlugin {
951957
const ZERO = BigInt("0");
952958
const ONE = BigInt("1");
953959
const START = ONE << BigInt("31");
960+
const CHUNK_SET_MASK = ~(START - ONE);
954961
let index = START;
955962
let denseIndex = 0;
956963
for (const chunk of chunks) {
@@ -1035,7 +1042,7 @@ class SplitChunksPlugin {
10351042
/** @type {Map<Module, Iterable<Chunk[]>>} */
10361043
const groupedByExportsMap = new Map();
10371044

1038-
/** @typedef {Map<bigint | Chunk, ChunkSet>} ChunkSetsInGraph */
1045+
/** @typedef {Map<bigint, ChunkSet>} ChunkSetsInGraph */
10391046

10401047
const getExportsChunkSetsInGraph = memoize(() => {
10411048
/** @type {ChunkSetsInGraph} */
@@ -1049,7 +1056,7 @@ class SplitChunksPlugin {
10491056
if (chunks.length === 1) {
10501057
singleChunkSets.add(chunks[0]);
10511058
} else {
1052-
const chunksKey = getKey(chunks);
1059+
const chunksKey = /** @type {bigint} */ (getKey(chunks));
10531060
if (!chunkSetsInGraph.has(chunksKey)) {
10541061
chunkSetsInGraph.set(chunksKey, new Set(chunks));
10551062
}
@@ -1095,7 +1102,7 @@ class SplitChunksPlugin {
10951102
// (only smaller sets can be subset)
10961103
/**
10971104
* Group chunk sets by count.
1098-
* @param {IterableIterator<ChunkSet>} chunkSets set of sets of chunks
1105+
* @param {Iterable<ChunkSet>} chunkSets set of sets of chunks
10991106
* @returns {ChunkSetsByCount} map of sets of chunks by count
11001107
*/
11011108
const groupChunkSetsByCount = (chunkSets) => {
@@ -1131,6 +1138,49 @@ class SplitChunksPlugin {
11311138
)
11321139
);
11331140

1141+
/**
1142+
* Discovers intersections and groups them with the original chunk sets.
1143+
* @param {ChunkSetsInGraph} chunkSets original chunk sets
1144+
* @returns {ChunkSetsByCount} original and additional sets grouped by size
1145+
*/
1146+
const groupChunkSetsWithIntersections = (chunkSets) => {
1147+
/** @type {Map<bigint, ChunkSet>} */
1148+
const chunkSetsByMembership = new Map();
1149+
for (const [key, chunks] of chunkSets) {
1150+
chunkSetsByMembership.set(key & CHUNK_SET_MASK, chunks);
1151+
}
1152+
const result = findIntersections(chunkSetsByMembership, {
1153+
minimumSize: MIN_INTERSECTION_CHUNKS,
1154+
maximumCandidates: Math.min(
1155+
MAX_INTERSECTION_CANDIDATES,
1156+
chunkSetsByMembership.size * MAX_INTERSECTION_CANDIDATE_FACTOR
1157+
),
1158+
maximumPairs: MAX_INTERSECTION_PAIRS,
1159+
maximumComparisons: MAX_INTERSECTION_COMPARISONS
1160+
});
1161+
logger.debug(
1162+
"Prepared %d additional split chunk intersections from %d pairs and %d comparisons%s",
1163+
result.sets.length,
1164+
result.pairs,
1165+
result.comparisons,
1166+
result.limited ? " (limited)" : ""
1167+
);
1168+
return groupChunkSetsByCount([
1169+
...chunkSets.values(),
1170+
...result.sets
1171+
]);
1172+
};
1173+
const getChunkSetsWithIntersectionsByCount = memoize(() =>
1174+
groupChunkSetsWithIntersections(
1175+
getChunkSetsInGraph().chunkSetsInGraph
1176+
)
1177+
);
1178+
const getExportsChunkSetsWithIntersectionsByCount = memoize(() =>
1179+
groupChunkSetsWithIntersections(
1180+
getExportsChunkSetsInGraph().chunkSetsInGraph
1181+
)
1182+
);
1183+
11341184
/** @typedef {(ChunkSet | Chunk)[]} Combinations */
11351185

11361186
// Create a list of possible combinations
@@ -1204,13 +1254,25 @@ class SplitChunksPlugin {
12041254
getChunkSetsByCount()
12051255
);
12061256
});
1257+
const getCombinationsWithIntersectionsFactory = memoize(() => {
1258+
const { chunkSetsInGraph, singleChunkSets } = getChunkSetsInGraph();
1259+
return createGetCombinations(
1260+
chunkSetsInGraph,
1261+
singleChunkSets,
1262+
getChunkSetsWithIntersectionsByCount()
1263+
);
1264+
});
12071265

12081266
/**
12091267
* Returns combinations by key.
12101268
* @param {bigint | Chunk} key key
1269+
* @param {boolean} includeIntersections whether to include additional intersections
12111270
* @returns {Combinations} combinations by key
12121271
*/
1213-
const getCombinations = (key) => getCombinationsFactory()(key);
1272+
const getCombinations = (key, includeIntersections) =>
1273+
(includeIntersections
1274+
? getCombinationsWithIntersectionsFactory()
1275+
: getCombinationsFactory())(key);
12141276

12151277
const getExportsCombinationsFactory = memoize(() => {
12161278
const { chunkSetsInGraph, singleChunkSets } =
@@ -1221,13 +1283,25 @@ class SplitChunksPlugin {
12211283
getExportsChunkSetsByCount()
12221284
);
12231285
});
1286+
const getExportsCombinationsWithIntersectionsFactory = memoize(() => {
1287+
const { chunkSetsInGraph, singleChunkSets } =
1288+
getExportsChunkSetsInGraph();
1289+
return createGetCombinations(
1290+
chunkSetsInGraph,
1291+
singleChunkSets,
1292+
getExportsChunkSetsWithIntersectionsByCount()
1293+
);
1294+
});
12241295
/**
12251296
* Gets exports combinations.
12261297
* @param {bigint | Chunk} key key
1298+
* @param {boolean} includeIntersections whether to include additional intersections
12271299
* @returns {Combinations} exports combinations by key
12281300
*/
1229-
const getExportsCombinations = (key) =>
1230-
getExportsCombinationsFactory()(key);
1301+
const getExportsCombinations = (key, includeIntersections) =>
1302+
(includeIntersections
1303+
? getExportsCombinationsWithIntersectionsFactory()
1304+
: getExportsCombinationsFactory())(key);
12311305

12321306
/**
12331307
* Defines the selected chunks result type used by this module.
@@ -1440,17 +1514,25 @@ class SplitChunksPlugin {
14401514
/**
14411515
* Returns combinations of the chunks the module is in.
14421516
* @param {Module} module the module
1517+
* @param {boolean} includeIntersections whether to include additional intersections
14431518
* @returns {Combinations} chunk combinations
14441519
*/
1445-
const computeCombinations = (module) =>
1446-
getCombinations(getKey(chunkGraph.getModuleChunksIterable(module)));
1520+
const computeCombinations = (module, includeIntersections) =>
1521+
getCombinations(
1522+
getKey(chunkGraph.getModuleChunksIterable(module)),
1523+
includeIntersections
1524+
);
14471525

14481526
/**
14491527
* Returns combinations of the module's chunks grouped by used exports.
14501528
* @param {Module} module the module
1529+
* @param {boolean} includeIntersections whether to include additional intersections
14511530
* @returns {Set<ChunkSet | Chunk>} chunk combinations
14521531
*/
1453-
const computeCombinationsByUsedExports = (module) => {
1532+
const computeCombinationsByUsedExports = (
1533+
module,
1534+
includeIntersections
1535+
) => {
14541536
// fill the groupedByExportsMap
14551537
getExportsChunkSetsInGraph();
14561538
/** @type {Set<ChunkSet | Chunk>} */
@@ -1459,7 +1541,10 @@ class SplitChunksPlugin {
14591541
/** @type {Iterable<Chunk[]>} */
14601542
(groupedByExportsMap.get(module));
14611543
for (const chunks of groupedByUsedExports) {
1462-
for (const comb of getExportsCombinations(getKey(chunks))) {
1544+
for (const comb of getExportsCombinations(
1545+
getKey(chunks),
1546+
includeIntersections
1547+
)) {
14631548
set.add(comb);
14641549
}
14651550
}
@@ -1478,28 +1563,38 @@ class SplitChunksPlugin {
14781563
continue;
14791564
}
14801565

1481-
// Computed at most once per module, on first use by a cache group
1482-
/** @type {Combinations | undefined} */
1483-
let combsCache;
1484-
/** @type {Set<ChunkSet | Chunk> | undefined} */
1485-
let combsByUsedExportsCache;
1566+
// Each mode is computed at most once per module.
1567+
/** @type {(Combinations | undefined)[]} */
1568+
const combinationsCache = [];
1569+
/** @type {(Set<ChunkSet | Chunk> | undefined)[]} */
1570+
const combinationsByUsedExportsCache = [];
14861571

14871572
let cacheGroupIndex = 0;
14881573
for (const cacheGroupSource of cacheGroups) {
14891574
const cacheGroup = this._getCacheGroup(cacheGroupSource);
1575+
const includeIntersections =
1576+
cacheGroup.getName === defaultGetName &&
1577+
(cacheGroup._validateSize ||
1578+
hasNonZeroSizes(cacheGroup.minSizeReduction));
1579+
const combinationsCacheIndex = includeIntersections ? 1 : 0;
14901580

14911581
let combs;
14921582
if (cacheGroup.usedExports) {
1493-
if (combsByUsedExportsCache === undefined) {
1494-
combsByUsedExportsCache =
1495-
computeCombinationsByUsedExports(module);
1583+
combs = combinationsByUsedExportsCache[combinationsCacheIndex];
1584+
if (combs === undefined) {
1585+
combs = computeCombinationsByUsedExports(
1586+
module,
1587+
includeIntersections
1588+
);
1589+
combinationsByUsedExportsCache[combinationsCacheIndex] =
1590+
combs;
14961591
}
1497-
combs = combsByUsedExportsCache;
14981592
} else {
1499-
if (combsCache === undefined) {
1500-
combsCache = computeCombinations(module);
1593+
combs = combinationsCache[combinationsCacheIndex];
1594+
if (combs === undefined) {
1595+
combs = computeCombinations(module, includeIntersections);
1596+
combinationsCache[combinationsCacheIndex] = combs;
15011597
}
1502-
combs = combsCache;
15031598
}
15041599
// For all combination of chunk selection
15051600
for (const chunkCombination of combs) {

‎lib/util/SetHelpers.js‎

Lines changed: 96 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -5,6 +5,9 @@
55

66
"use strict";
77

8+
const BIGINT_ZERO = BigInt("0");
9+
const BIGINT_ONE = BigInt("1");
10+
811
/**
912
* intersect creates Set containing the intersection of elements between all sets
1013
* @template T
@@ -36,6 +39,98 @@ const intersect = (sets) => {
3639
return current;
3740
};
3841

42+
/**
43+
* Defines the result of bounded set intersection discovery.
44+
* @template T
45+
* @typedef {object} FindIntersectionsResult
46+
* @property {Set<T>[]} sets the additional sets
47+
* @property {number} pairs the number of intersected pairs
48+
* @property {number} comparisons the number of membership checks
49+
* @property {boolean} limited whether discovery reached a limit
50+
*/
51+
52+
/**
53+
* Discovers proper intersections that are not already present in the input.
54+
* Work and additional memory are bounded while every original set is retained.
55+
* @template T
56+
* @param {Map<bigint, Set<T>>} setsByKey original sets keyed by membership bit masks
57+
* @param {object} options discovery options
58+
* @param {number} options.minimumSize minimum size of an intersection
59+
* @param {number} options.maximumCandidates maximum number of additional sets
60+
* @param {number} options.maximumPairs maximum number of intersected pairs
61+
* @param {number} options.maximumComparisons maximum number of membership checks
62+
* @returns {FindIntersectionsResult<T>} discovered set intersections
63+
*/
64+
const findIntersections = (setsByKey, options) => {
65+
const { minimumSize, maximumCandidates, maximumPairs, maximumComparisons } =
66+
options;
67+
/** @type {{ key: bigint, set: Set<T> }[]} */
68+
const candidates = [];
69+
/** @type {Set<bigint>} */
70+
const knownKeys = new Set();
71+
for (const [key, set] of setsByKey) {
72+
knownKeys.add(key);
73+
if (set.size > minimumSize) candidates.push({ key, set });
74+
}
75+
candidates.sort((a, b) => {
76+
const sizeDifference = b.set.size - a.set.size;
77+
return sizeDifference || (a.key < b.key ? -1 : a.key > b.key ? 1 : 0);
78+
});
79+
80+
const originalCount = candidates.length;
81+
/** @type {Set<T>[]} */
82+
const intersections = [];
83+
let pairs = 0;
84+
let comparisons = 0;
85+
let limited = false;
86+
let currentIndex = 0;
87+
88+
search: while (currentIndex < candidates.length) {
89+
const current = candidates[currentIndex];
90+
if (current.set.size <= minimumSize) {
91+
currentIndex++;
92+
continue;
93+
}
94+
const end = Math.min(currentIndex, originalCount);
95+
for (let otherIndex = 0; otherIndex < end; otherIndex++) {
96+
if (intersections.length >= maximumCandidates || pairs >= maximumPairs) {
97+
limited = true;
98+
break search;
99+
}
100+
const other = candidates[otherIndex];
101+
const smaller =
102+
current.set.size < other.set.size ? current.set : other.set;
103+
if (comparisons + smaller.size > maximumComparisons) {
104+
limited = true;
105+
break search;
106+
}
107+
pairs++;
108+
comparisons += smaller.size;
109+
const key = current.key & other.key;
110+
if (knownKeys.has(key)) continue;
111+
let remaining = key;
112+
let size = 0;
113+
while (remaining !== BIGINT_ZERO && size < minimumSize) {
114+
remaining &= remaining - BIGINT_ONE;
115+
size++;
116+
}
117+
if (size < minimumSize) continue;
118+
const larger = smaller === current.set ? other.set : current.set;
119+
/** @type {Set<T>} */
120+
const intersection = new Set();
121+
for (const item of smaller) {
122+
if (larger.has(item)) intersection.add(item);
123+
}
124+
knownKeys.add(key);
125+
intersections.push(intersection);
126+
candidates.push({ key, set: intersection });
127+
}
128+
currentIndex++;
129+
}
130+
131+
return { sets: intersections, pairs, comparisons, limited };
132+
};
133+
39134
/**
40135
* Checks if a set is the subset of another set
41136
* @template T
@@ -92,6 +187,7 @@ const combine = (a, b) => {
92187

93188
module.exports.combine = combine;
94189
module.exports.find = find;
190+
module.exports.findIntersections = findIntersections;
95191
module.exports.first = first;
96192
module.exports.intersect = intersect;
97193
module.exports.isSubset = isSubset;

0 commit comments

Comments
 (0)