GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — prevent groups with size < minSize · webpack/webpack@cbeaf70

File tree

Expand file treeCollapse file tree
Open diff view settings
Filter options
  • lib/util
    • deterministicGrouping.js
  • test/__snapshots__
    • StatsTestCases.test.js.snap
Expand file treeCollapse file tree
Open diff view settings
Collapse file

‎lib/util/deterministicGrouping.js‎

Copy file name to clipboardExpand all lines: lib/util/deterministicGrouping.js
+92-70Lines changed: 92 additions & 70 deletions
Original file line numberDiff line numberDiff line change
@@ -124,6 +124,13 @@ module.exports = ({ maxSize, minSize, items, getSize, getKey }) => {
124124
/** @type {Node<T>[]} */
125125
const initialNodes = [];
126126

127+
// lexically ordering of keys
128+
nodes.sort((a, b) => {
129+
if (a.key < b.key) return -1;
130+
if (a.key > b.key) return 1;
131+
return 0;
132+
});
133+
127134
// return nodes bigger than maxSize directly as group
128135
for (const node of nodes) {
129136
if (node.size >= maxSize) {
@@ -134,13 +141,6 @@ module.exports = ({ maxSize, minSize, items, getSize, getKey }) => {
134141
}
135142

136143
if (initialNodes.length > 0) {
137-
// lexically ordering of keys
138-
initialNodes.sort((a, b) => {
139-
if (a.key < b.key) return -1;
140-
if (a.key > b.key) return 1;
141-
return 0;
142-
});
143-
144144
// calculate similarities between lexically adjacent nodes
145145
/** @type {number[]} */
146146
const similarities = [];
@@ -150,77 +150,99 @@ module.exports = ({ maxSize, minSize, items, getSize, getKey }) => {
150150
similarities.push(similarity(a.key, b.key));
151151
}
152152

153-
const queue = [new Group(initialNodes, similarities)];
153+
const initialGroup = new Group(initialNodes, similarities);
154154

155-
while (queue.length) {
156-
const group = queue.pop();
157-
// only groups bigger than maxSize need to be splitted
158-
if (group.size < maxSize) {
159-
result.push(group);
160-
continue;
155+
if (initialGroup.size < minSize) {
156+
// We hit an edgecase where the working set is already smaller than minSize
157+
// We merge it with the smallest result node to keep minSize intact
158+
if (result.length > 0) {
159+
const smallestGroup = result.reduce(
160+
(min, group) => (min.size > group.size ? group : min)
161+
);
162+
for (const node of initialGroup.nodes) smallestGroup.nodes.push(node);
163+
smallestGroup.nodes.sort((a, b) => {
164+
if (a.key < b.key) return -1;
165+
if (a.key > b.key) return 1;
166+
return 0;
167+
});
168+
} else {
169+
// There are no other nodes
170+
// We use all nodes and have to accept that it's smaller than minSize
171+
result.push(initialGroup);
161172
}
173+
} else {
174+
const queue = [initialGroup];
162175

163-
// find unsplittable area from left and right
164-
// going minSize from left and right
165-
// at least one node need to be included otherwise we get stuck
166-
let left = 0;
167-
let leftSize = 0;
168-
while (leftSize <= minSize) {
169-
leftSize += group.nodes[left].size;
170-
left++;
171-
}
172-
let right = group.nodes.length - 1;
173-
let rightSize = 0;
174-
while (rightSize <= minSize) {
175-
rightSize += group.nodes[right].size;
176-
right--;
177-
}
176+
while (queue.length) {
177+
const group = queue.pop();
178+
// only groups bigger than maxSize need to be splitted
179+
if (group.size < maxSize) {
180+
result.push(group);
181+
continue;
182+
}
178183

179-
if (left - 1 > right) {
180-
// can't split group while holding minSize
181-
// because minSize is preferred of maxSize we return
182-
// the group here even while it's too big
183-
// To avoid this make sure maxSize > minSize * 3
184-
result.push(group);
185-
continue;
186-
}
187-
if (left <= right) {
188-
// when there is a area between left and right
189-
// we look for best split point
190-
// we split at the minimum similarity
191-
// here key space is separated the most
192-
let best = left - 1;
193-
let bestSimilarity = group.similarities[best];
194-
for (let i = left; i <= right; i++) {
195-
const similarity = group.similarities[i];
196-
if (similarity < bestSimilarity) {
197-
best = i;
198-
bestSimilarity = similarity;
184+
// find unsplittable area from left and right
185+
// going minSize from left and right
186+
// at least one node need to be included otherwise we get stuck
187+
let left = 0;
188+
let leftSize = 0;
189+
while (leftSize <= minSize) {
190+
leftSize += group.nodes[left].size;
191+
left++;
192+
}
193+
let right = group.nodes.length - 1;
194+
let rightSize = 0;
195+
while (rightSize <= minSize) {
196+
rightSize += group.nodes[right].size;
197+
right--;
198+
}
199+
200+
if (left - 1 > right) {
201+
// can't split group while holding minSize
202+
// because minSize is preferred of maxSize we return
203+
// the group here even while it's too big
204+
// To avoid this make sure maxSize > minSize * 3
205+
result.push(group);
206+
continue;
207+
}
208+
if (left <= right) {
209+
// when there is a area between left and right
210+
// we look for best split point
211+
// we split at the minimum similarity
212+
// here key space is separated the most
213+
let best = left - 1;
214+
let bestSimilarity = group.similarities[best];
215+
for (let i = left; i <= right; i++) {
216+
const similarity = group.similarities[i];
217+
if (similarity < bestSimilarity) {
218+
best = i;
219+
bestSimilarity = similarity;
220+
}
199221
}
222+
left = best + 1;
223+
right = best;
200224
}
201-
left = best + 1;
202-
right = best;
203-
}
204225

205-
// create two new groups for left and right area
206-
// and queue them up
207-
const rightNodes = [group.nodes[right + 1]];
208-
/** @type {number[]} */
209-
const rightSimilaries = [];
210-
for (let i = right + 2; i < group.nodes.length; i++) {
211-
rightSimilaries.push(group.similarities[i - 1]);
212-
rightNodes.push(group.nodes[i]);
213-
}
214-
queue.push(new Group(rightNodes, rightSimilaries));
215-
216-
const leftNodes = [group.nodes[0]];
217-
/** @type {number[]} */
218-
const leftSimilaries = [];
219-
for (let i = 1; i < left; i++) {
220-
leftSimilaries.push(group.similarities[i - 1]);
221-
leftNodes.push(group.nodes[i]);
226+
// create two new groups for left and right area
227+
// and queue them up
228+
const rightNodes = [group.nodes[right + 1]];
229+
/** @type {number[]} */
230+
const rightSimilaries = [];
231+
for (let i = right + 2; i < group.nodes.length; i++) {
232+
rightSimilaries.push(group.similarities[i - 1]);
233+
rightNodes.push(group.nodes[i]);
234+
}
235+
queue.push(new Group(rightNodes, rightSimilaries));
236+
237+
const leftNodes = [group.nodes[0]];
238+
/** @type {number[]} */
239+
const leftSimilaries = [];
240+
for (let i = 1; i < left; i++) {
241+
leftSimilaries.push(group.similarities[i - 1]);
242+
leftNodes.push(group.nodes[i]);
243+
}
244+
queue.push(new Group(leftNodes, leftSimilaries));
222245
}
223-
queue.push(new Group(leftNodes, leftSimilaries));
224246
}
225247
}
226248

Collapse file

‎test/__snapshots__/StatsTestCases.test.js.snap‎

Copy file name to clipboardExpand all lines: test/__snapshots__/StatsTestCases.test.js.snap
+13-15Lines changed: 13 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -2978,14 +2978,14 @@ Child development:
29782978
> ./ main
29792979
[./node_modules/very-big.js?1] 1.57 KiB {vendors~main~._node_modules_very-big.js~6bdbed7b} [built]
29802980
Child switched:
2981-
Entrypoint main = switched-vendors~main~7274e1de.js switched-vendors~main~0feae4ad.js switched-main~2bc5b870.js switched-main~748942c6.js switched-main~17acad98.js switched-main~b2c7414a.js switched-main~d9f1562b.js switched-main~c6931360.js switched-main~cd7c5bfc.js switched-main~02369f19.js
2982-
chunk {0} switched-main~02369f19.js (main~02369f19) 1.57 KiB ={1}= ={2}= ={3}= ={4}= ={5}= ={6}= ={7}= ={8}= ={9}= [entry] [rendered]
2981+
Entrypoint main = switched-vendors~main~7274e1de.js switched-main~2bc5b870.js switched-main~748942c6.js switched-main~17acad98.js switched-main~b2c7414a.js switched-main~d9f1562b.js switched-main~c6931360.js switched-main~cd7c5bfc.js switched-main~02369f19.js
2982+
chunk {0} switched-main~02369f19.js (main~02369f19) 1.57 KiB ={1}= ={2}= ={3}= ={4}= ={5}= ={6}= ={7}= ={8}= [entry] [rendered]
29832983
> ./ main
29842984
[11] ./very-big.js?1 1.57 KiB {0} [built]
2985-
chunk {1} switched-main~17acad98.js (main~17acad98) 1.57 KiB ={0}= ={2}= ={3}= ={4}= ={5}= ={6}= ={7}= ={8}= ={9}= [initial] [rendered]
2985+
chunk {1} switched-main~17acad98.js (main~17acad98) 1.57 KiB ={0}= ={2}= ={3}= ={4}= ={5}= ={6}= ={7}= ={8}= [initial] [rendered]
29862986
> ./ main
29872987
[39] ./in-some-directory/very-big.js?1 1.57 KiB {1} [built]
2988-
chunk {2} switched-main~2bc5b870.js (main~2bc5b870) 1.05 KiB ={0}= ={1}= ={3}= ={4}= ={5}= ={6}= ={7}= ={8}= ={9}= [initial] [rendered]
2988+
chunk {2} switched-main~2bc5b870.js (main~2bc5b870) 1.05 KiB ={0}= ={1}= ={3}= ={4}= ={5}= ={6}= ={7}= ={8}= [initial] [rendered]
29892989
> ./ main
29902990
[0] ./big.js?1 268 bytes {2} [built]
29912991
[1] ./big.js?2 268 bytes {2} [built]
@@ -2994,7 +2994,7 @@ Child switched:
29942994
[36] ./in-some-directory/small.js?2 67 bytes {2} [built]
29952995
[37] ./in-some-directory/small.js?3 67 bytes {2} [built]
29962996
[38] ./in-some-directory/small.js?4 67 bytes {2} [built]
2997-
chunk {3} switched-main~748942c6.js (main~748942c6) 1.18 KiB ={0}= ={1}= ={2}= ={4}= ={5}= ={6}= ={7}= ={8}= ={9}= [initial] [rendered]
2997+
chunk {3} switched-main~748942c6.js (main~748942c6) 1.18 KiB ={0}= ={1}= ={2}= ={4}= ={5}= ={6}= ={7}= ={8}= [initial] [rendered]
29982998
> ./ main
29992999
[2] ./small.js?1 67 bytes {3} [built]
30003000
[3] ./small.js?2 67 bytes {3} [built]
@@ -3012,16 +3012,16 @@ Child switched:
30123012
[29] ./inner-module/small.js?5 67 bytes {3} [built]
30133013
[30] ./inner-module/small.js?6 67 bytes {3} [built]
30143014
+ 3 hidden modules
3015-
chunk {4} switched-main~b2c7414a.js (main~b2c7414a) 1.19 KiB ={0}= ={1}= ={2}= ={3}= ={5}= ={6}= ={7}= ={8}= ={9}= [initial] [rendered]
3015+
chunk {4} switched-main~b2c7414a.js (main~b2c7414a) 1.19 KiB ={0}= ={1}= ={2}= ={3}= ={5}= ={6}= ={7}= ={8}= [initial] [rendered]
30163016
> ./ main
30173017
[44] ./index.js 1.19 KiB {4} [built]
3018-
chunk {5} switched-main~c6931360.js (main~c6931360) 1.57 KiB ={0}= ={1}= ={2}= ={3}= ={4}= ={6}= ={7}= ={8}= ={9}= [initial] [rendered]
3018+
chunk {5} switched-main~c6931360.js (main~c6931360) 1.57 KiB ={0}= ={1}= ={2}= ={3}= ={4}= ={6}= ={7}= ={8}= [initial] [rendered]
30193019
> ./ main
30203020
[12] ./very-big.js?2 1.57 KiB {5} [built]
3021-
chunk {6} switched-main~cd7c5bfc.js (main~cd7c5bfc) 1.57 KiB ={0}= ={1}= ={2}= ={3}= ={4}= ={5}= ={7}= ={8}= ={9}= [initial] [rendered]
3021+
chunk {6} switched-main~cd7c5bfc.js (main~cd7c5bfc) 1.57 KiB ={0}= ={1}= ={2}= ={3}= ={4}= ={5}= ={7}= ={8}= [initial] [rendered]
30223022
> ./ main
30233023
[13] ./very-big.js?3 1.57 KiB {6} [built]
3024-
chunk {7} switched-main~d9f1562b.js (main~d9f1562b) 1.11 KiB ={0}= ={1}= ={2}= ={3}= ={4}= ={5}= ={6}= ={8}= ={9}= [initial] [rendered]
3024+
chunk {7} switched-main~d9f1562b.js (main~d9f1562b) 1.11 KiB ={0}= ={1}= ={2}= ={3}= ={4}= ={5}= ={6}= ={8}= [initial] [rendered]
30253025
> ./ main
30263026
[14] ./subfolder/big.js?1 268 bytes {7} [built]
30273027
[15] ./subfolder/big.js?2 268 bytes {7} [built]
@@ -3034,14 +3034,12 @@ Child switched:
30343034
[22] ./subfolder/small.js?7 67 bytes {7} [built]
30353035
[23] ./subfolder/small.js?8 67 bytes {7} [built]
30363036
[24] ./subfolder/small.js?9 67 bytes {7} [built]
3037-
chunk {8} switched-vendors~main~0feae4ad.js (vendors~main~0feae4ad) 1.57 KiB ={0}= ={1}= ={2}= ={3}= ={4}= ={5}= ={6}= ={7}= ={9}= [initial] [rendered] split chunk (cache group: vendors) (name: vendors~main)
3037+
chunk {8} switched-vendors~main~7274e1de.js (vendors~main~7274e1de) 1.96 KiB ={0}= ={1}= ={2}= ={3}= ={4}= ={5}= ={6}= ={7}= [initial] [rendered] split chunk (cache group: vendors) (name: vendors~main)
30383038
> ./ main
3039+
[40] ./node_modules/big.js?1 268 bytes {8} [built]
3040+
[41] ./node_modules/small.js?1 67 bytes {8} [built]
3041+
[42] ./node_modules/small.js?2 67 bytes {8} [built]
30393042
[43] ./node_modules/very-big.js?1 1.57 KiB {8} [built]
3040-
chunk {9} switched-vendors~main~7274e1de.js (vendors~main~7274e1de) 402 bytes ={0}= ={1}= ={2}= ={3}= ={4}= ={5}= ={6}= ={7}= ={8}= [initial] [rendered] split chunk (cache group: vendors) (name: vendors~main)
3041-
> ./ main
3042-
[40] ./node_modules/big.js?1 268 bytes {9} [built]
3043-
[41] ./node_modules/small.js?1 67 bytes {9} [built]
3044-
[42] ./node_modules/small.js?2 67 bytes {9} [built]
30453043
Child zero-min:
30463044
Entrypoint main = zero-min-vendors~main~7274e1de.js zero-min-vendors~main~0feae4ad.js zero-min-main~6e7ead72.js zero-min-main~6a2ae26b.js zero-min-main~17acad98.js zero-min-main~b2c7414a.js zero-min-main~75f09de8.js zero-min-main~052b3814.js zero-min-main~3ff27526.js zero-min-main~11485824.js zero-min-main~c6931360.js zero-min-main~cd7c5bfc.js zero-min-main~02369f19.js
30473045
chunk {0} zero-min-main~02369f19.js (main~02369f19) 1.57 KiB ={1}= ={2}= ={3}= ={4}= ={5}= ={6}= ={7}= ={8}= ={9}= ={10}= ={11}= ={12}= [entry] [rendered]

0 commit comments

Comments
0 (0)
You are visitor 01402605 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.