Skip to content

Commit 7870bfc

Browse files
sokrasokra
committed
improve chunk graph building performance
document algorithm
1 parent 4795ffd commit 7870bfc

9 files changed

Lines changed: 146 additions & 30 deletions

File tree

‎lib/Compilation.js‎

Lines changed: 121 additions & 29 deletions
Original file line numberDiff line numberDiff line change
@@ -846,61 +846,90 @@ class Compilation extends Tapable {
846846
}
847847
}
848848

849+
// This method creates the Chunk graph from the Module graph
849850
processDependenciesBlocksForChunks(inputChunks) {
851+
// Process is splitting into two parts:
852+
// Part one traverse the module graph and builds a very basic chunks graph
853+
// in chunkDependencies.
854+
// Part two traverse every possible way through the basic chunk graph and
855+
// tracks the available modules. While traversing it connects chunks with
856+
// eachother and Blocks with Chunks. It stops traversing when all modules
857+
// for a chunk are already available. So it doesn't connect unneeded chunks.
858+
850859
const chunkDependencies = new Map(); // Map<Chunk, Array<{Module, Chunk}>>
860+
const allCreatedChunks = new Set();
861+
862+
// PART ONE
851863

864+
const blockChunks = new Map();
865+
866+
// Start with the provided modules/chunks
852867
const queue = inputChunks.map(chunk => ({
853868
block: chunk.entryModule,
854-
module: chunk.entryModule,
855869
chunk: chunk
856870
}));
857871

858-
let block, module, chunk;
872+
let block, chunk;
873+
874+
// For each async Block in graph
859875
const iteratorBlock = b => {
860-
let c;
861-
if(!b.chunks) {
876+
// 1. We create a chunk for this Block
877+
// but only once (blockChunks map)
878+
let c = blockChunks.get(b);
879+
if(c === undefined) {
862880
c = this.addChunk(b.chunkName, b.module, b.loc);
863-
b.chunks = [c];
864-
c.addBlock(b);
865-
} else {
866-
c = b.chunks[0];
881+
blockChunks.set(b, c);
882+
allCreatedChunks.add(c);
883+
// We initialize the chunks property
884+
// this is later filled with the chunk when needed
885+
b.chunks = [];
867886
}
887+
888+
// 2. We store the Block+Chunk mapping as dependency for the chunk
868889
let deps = chunkDependencies.get(chunk);
869890
if(!deps) chunkDependencies.set(chunk, deps = []);
870891
deps.push({
871-
chunk: c,
872-
module
892+
block: b,
893+
chunk: c
873894
});
895+
896+
// 3. We enqueue the DependenciesBlock for traversal
874897
queue.push({
875898
block: b,
876-
module: null,
877899
chunk: c
878900
});
879901
};
880902

903+
// For each Dependency in the graph
881904
const iteratorDependency = d => {
905+
// We skip Dependencies without Module pointer
882906
if(!d.module) {
883907
return;
884908
}
909+
// We skip weak Dependencies
885910
if(d.weak) {
886911
return;
887912
}
913+
// We connect Module and Chunk when not already done
888914
if(chunk.addModule(d.module)) {
889915
d.module.addChunk(chunk);
916+
917+
// And enqueue the Module for traversal
890918
queue.push({
891919
block: d.module,
892-
module: d.module,
893920
chunk
894921
});
895922
}
896923
};
897924

925+
// Iterative traversal of the Module graph
926+
// Recursive would be simpler to write but could result in Stack Overflows
898927
while(queue.length) {
899928
const queueItem = queue.pop();
900929
block = queueItem.block;
901-
module = queueItem.module;
902930
chunk = queueItem.chunk;
903931

932+
// Traverse all variables, Dependencies and Blocks
904933
if(block.variables) {
905934
iterationBlockVariable(block.variables, iteratorDependency);
906935
}
@@ -914,45 +943,108 @@ class Compilation extends Tapable {
914943
}
915944
}
916945

946+
// PART TWO
947+
948+
let availableModules;
949+
let newAvailableModules;
917950
const queue2 = inputChunks.map(chunk => ({
918951
chunk,
919-
chunks: new Set()
952+
availableModules: new Set()
920953
}));
921954

922-
let chunks;
923-
const filterFn = dep => {
924-
if(chunks.has(dep.chunk)) return false;
925-
for(const chunk of chunks) {
926-
if(chunk.containsModule(dep.module))
955+
// Helper function to check if all modules of a chunk are available
956+
const areModulesAvailable = (chunk, availableModules) => {
957+
for(const module of chunk.modulesIterable) {
958+
if(!availableModules.has(module))
927959
return false;
928960
}
929961
return true;
930962
};
931963

964+
// For each edge in the basic chunk graph
965+
const filterFn = dep => {
966+
// Filter egdes that are not needed because all modules are already available
967+
// This also filters circular dependencies in the chunks graph
968+
const depChunk = dep.chunk;
969+
if(areModulesAvailable(depChunk, newAvailableModules))
970+
return false; // break all modules are already available
971+
return true;
972+
};
973+
974+
const minAvailableModulesMap = new Map();
975+
976+
// Iterative traversing of the basic chunk graph
932977
while(queue2.length) {
933978
const queueItem = queue2.pop();
934979
chunk = queueItem.chunk;
935-
chunks = queueItem.chunks;
980+
availableModules = queueItem.availableModules;
981+
982+
// 1. Get minimal available modules
983+
// It doesn't make sense to traverse a chunk again with more available modules.
984+
// This step calculates the minimal available modules and skips traversal when
985+
// the list didn't shrink.
986+
let minAvailableModules = minAvailableModulesMap.get(chunk);
987+
if(minAvailableModules === undefined) {
988+
minAvailableModulesMap.set(chunk, new Set(availableModules));
989+
} else {
990+
let deletedModules = false;
991+
for(const m of minAvailableModules) {
992+
if(!availableModules.has(m)) {
993+
minAvailableModules.delete(m);
994+
deletedModules = true;
995+
}
996+
}
997+
if(!deletedModules)
998+
continue;
999+
}
9361000

1001+
// 2. Get the edges at this point of the graph
9371002
const deps = chunkDependencies.get(chunk);
9381003
if(!deps) continue;
1004+
if(deps.length === 0) continue;
9391005

940-
const depsFiltered = deps.filter(filterFn);
1006+
// 3. Create a new Set of available modules at this points
1007+
newAvailableModules = new Set(availableModules);
1008+
for(const m of chunk.modulesIterable)
1009+
newAvailableModules.add(m);
9411010

942-
for(let i = 0; i < depsFiltered.length; i++) {
943-
const dep = depsFiltered[i];
1011+
// 4. Filter edges with available modules
1012+
const filteredDeps = deps.filter(filterFn);
1013+
1014+
// 5. Foreach remaining edge
1015+
const nextChunks = new Set();
1016+
for(let i = 0; i < filteredDeps.length; i++) {
1017+
const dep = filteredDeps[i];
9441018
const depChunk = dep.chunk;
945-
chunk.addChunk(depChunk);
946-
depChunk.addParent(chunk);
1019+
const depBlock = dep.block;
9471020

948-
const newChunks = depsFiltered.length > 1 ? new Set(chunks) : chunks;
949-
newChunks.add(chunk);
1021+
// 6. Connnect block with chunk
1022+
if(depChunk.addBlock(depBlock)) {
1023+
depBlock.chunks.push(depChunk);
1024+
}
1025+
1026+
// 7. Connect chunk with parent
1027+
if(chunk.addChunk(depChunk)) {
1028+
depChunk.addParent(chunk);
1029+
}
1030+
1031+
nextChunks.add(depChunk);
1032+
}
1033+
1034+
// 8. Enqueue further traversal
1035+
for(const nextChunk of nextChunks) {
9501036
queue2.push({
951-
chunk: depChunk,
952-
chunks: newChunks
1037+
chunk: nextChunk,
1038+
availableModules: newAvailableModules
9531039
});
9541040
}
9551041
}
1042+
1043+
// Remove all unconnected chunks
1044+
for(const chunk of allCreatedChunks) {
1045+
if(chunk.parents.length === 0)
1046+
chunk.remove("unconnected");
1047+
}
9561048
}
9571049

9581050
removeChunkFromDependencies(block, chunk) {

‎test/configCases/performance/many-async-imports/index.js‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,5 @@
1+
import promise from "./start";
2+
3+
it("should compile a module with many async imports in acceptable time", function(done) {
4+
promise.then(() => done(), e => done(e));
5+
});

‎test/configCases/performance/many-async-imports/leaf.js‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+
import("./start");

‎test/configCases/performance/many-async-imports/reexport.loader.js‎

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
module.exports = function() {
2+
var str = "export default Promise.all([\n";
3+
for(var i = 0; i < 6; i++) {
4+
for(var j = 0; j < 2; j++) {
5+
str += `import("./reexport.loader.js!?${i}"),\n`;
6+
}
7+
}
8+
str += "]);";
9+
return str;
10+
};

‎test/configCases/performance/many-async-imports/start.js‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+
export { default } from "./reexport.loader.js!";

‎test/configCases/performance/many-async-imports/test.config.js‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,3 @@
1+
module.exports = {
2+
timeout: 10000
3+
};

‎test/configCases/performance/many-async-imports/test.filter.js‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,3 @@
1+
module.exports = function(config) {
2+
return !/^v4/.test(process.version);
3+
};

‎test/configCases/performance/many-async-imports/webpack.config.js‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+
module.exports = {};

‎test/statsCases/optimize-chunks/expected.txt‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -9,7 +9,7 @@ Time: Xms
99
5.js 306 bytes 5, 3 [emitted] cir2 from cir1
1010
6.js 80 bytes 6 [emitted] ac in ab
1111
main.js 6.78 kB 7 [emitted] main
12-
chunk {0} 0.js (cir1) 81 bytes {3} {5} {7} [rendered]
12+
chunk {0} 0.js (cir1) 81 bytes {3} {7} [rendered]
1313
> duplicate cir1 from cir2 [6] (webpack)/test/statsCases/optimize-chunks/circular2.js 1:0-79
1414
> duplicate cir1 [7] (webpack)/test/statsCases/optimize-chunks/index.js 13:0-54
1515
[5] (webpack)/test/statsCases/optimize-chunks/circular1.js 81 bytes {0} [built]

0 commit comments

Comments
 (0)