Skip to content

Commit 7ebf931

Browse files
sokrasokra
authored
Merge pull request webpack#5786 from webpack/performance/chunks
improve chunk graph building performance
2 parents 48096a1 + 7870bfc commit 7ebf931

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
@@ -853,61 +853,90 @@ class Compilation extends Tapable {
853853
}
854854
}
855855

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

871+
const blockChunks = new Map();
872+
873+
// Start with the provided modules/chunks
859874
const queue = inputChunks.map(chunk => ({
860875
block: chunk.entryModule,
861-
module: chunk.entryModule,
862876
chunk: chunk
863877
}));
864878

865-
let block, module, chunk;
879+
let block, chunk;
880+
881+
// For each async Block in graph
866882
const iteratorBlock = b => {
867-
let c;
868-
if(!b.chunks) {
883+
// 1. We create a chunk for this Block
884+
// but only once (blockChunks map)
885+
let c = blockChunks.get(b);
886+
if(c === undefined) {
869887
c = this.addChunk(b.chunkName, b.module, b.loc);
870-
b.chunks = [c];
871-
c.addBlock(b);
872-
} else {
873-
c = b.chunks[0];
888+
blockChunks.set(b, c);
889+
allCreatedChunks.add(c);
890+
// We initialize the chunks property
891+
// this is later filled with the chunk when needed
892+
b.chunks = [];
874893
}
894+
895+
// 2. We store the Block+Chunk mapping as dependency for the chunk
875896
let deps = chunkDependencies.get(chunk);
876897
if(!deps) chunkDependencies.set(chunk, deps = []);
877898
deps.push({
878-
chunk: c,
879-
module
899+
block: b,
900+
chunk: c
880901
});
902+
903+
// 3. We enqueue the DependenciesBlock for traversal
881904
queue.push({
882905
block: b,
883-
module: null,
884906
chunk: c
885907
});
886908
};
887909

910+
// For each Dependency in the graph
888911
const iteratorDependency = d => {
912+
// We skip Dependencies without Module pointer
889913
if(!d.module) {
890914
return;
891915
}
916+
// We skip weak Dependencies
892917
if(d.weak) {
893918
return;
894919
}
920+
// We connect Module and Chunk when not already done
895921
if(chunk.addModule(d.module)) {
896922
d.module.addChunk(chunk);
923+
924+
// And enqueue the Module for traversal
897925
queue.push({
898926
block: d.module,
899-
module: d.module,
900927
chunk
901928
});
902929
}
903930
};
904931

932+
// Iterative traversal of the Module graph
933+
// Recursive would be simpler to write but could result in Stack Overflows
905934
while(queue.length) {
906935
const queueItem = queue.pop();
907936
block = queueItem.block;
908-
module = queueItem.module;
909937
chunk = queueItem.chunk;
910938

939+
// Traverse all variables, Dependencies and Blocks
911940
if(block.variables) {
912941
iterationBlockVariable(block.variables, iteratorDependency);
913942
}
@@ -921,45 +950,108 @@ class Compilation extends Tapable {
921950
}
922951
}
923952

953+
// PART TWO
954+
955+
let availableModules;
956+
let newAvailableModules;
924957
const queue2 = inputChunks.map(chunk => ({
925958
chunk,
926-
chunks: new Set()
959+
availableModules: new Set()
927960
}));
928961

929-
let chunks;
930-
const filterFn = dep => {
931-
if(chunks.has(dep.chunk)) return false;
932-
for(const chunk of chunks) {
933-
if(chunk.containsModule(dep.module))
962+
// Helper function to check if all modules of a chunk are available
963+
const areModulesAvailable = (chunk, availableModules) => {
964+
for(const module of chunk.modulesIterable) {
965+
if(!availableModules.has(module))
934966
return false;
935967
}
936968
return true;
937969
};
938970

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

1008+
// 2. Get the edges at this point of the graph
9441009
const deps = chunkDependencies.get(chunk);
9451010
if(!deps) continue;
1011+
if(deps.length === 0) continue;
9461012

947-
const depsFiltered = deps.filter(filterFn);
1013+
// 3. Create a new Set of available modules at this points
1014+
newAvailableModules = new Set(availableModules);
1015+
for(const m of chunk.modulesIterable)
1016+
newAvailableModules.add(m);
9481017

949-
for(let i = 0; i < depsFiltered.length; i++) {
950-
const dep = depsFiltered[i];
1018+
// 4. Filter edges with available modules
1019+
const filteredDeps = deps.filter(filterFn);
1020+
1021+
// 5. Foreach remaining edge
1022+
const nextChunks = new Set();
1023+
for(let i = 0; i < filteredDeps.length; i++) {
1024+
const dep = filteredDeps[i];
9511025
const depChunk = dep.chunk;
952-
chunk.addChunk(depChunk);
953-
depChunk.addParent(chunk);
1026+
const depBlock = dep.block;
9541027

955-
const newChunks = depsFiltered.length > 1 ? new Set(chunks) : chunks;
956-
newChunks.add(chunk);
1028+
// 6. Connnect block with chunk
1029+
if(depChunk.addBlock(depBlock)) {
1030+
depBlock.chunks.push(depChunk);
1031+
}
1032+
1033+
// 7. Connect chunk with parent
1034+
if(chunk.addChunk(depChunk)) {
1035+
depChunk.addParent(chunk);
1036+
}
1037+
1038+
nextChunks.add(depChunk);
1039+
}
1040+
1041+
// 8. Enqueue further traversal
1042+
for(const nextChunk of nextChunks) {
9571043
queue2.push({
958-
chunk: depChunk,
959-
chunks: newChunks
1044+
chunk: nextChunk,
1045+
availableModules: newAvailableModules
9601046
});
9611047
}
9621048
}
1049+
1050+
// Remove all unconnected chunks
1051+
for(const chunk of allCreatedChunks) {
1052+
if(chunk.parents.length === 0)
1053+
chunk.remove("unconnected");
1054+
}
9631055
}
9641056

9651057
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)