Skip to content

Commit 512a357

Browse files
perf(javascript): reuse a released SyntaxTree's columns, as CSS and HTML do
A released tree hands columns of up to 65536 nodes to the next tree and frees larger ones, and the next tree grows straight to the size the last one needed. A minifier run on the same input no longer allocates its columns again, which CodSpeed's memory mode counts. Claude-Session: https://claude.ai/code/session_01Tgxgyb4N35ndP6cC4KcrXC
1 parent fd0b90e commit 512a357

3 files changed

Lines changed: 150 additions & 65 deletions

File tree

‎lib/javascript/syntax-parser.js‎

Lines changed: 113 additions & 55 deletions
Original file line numberDiff line numberDiff line change
@@ -19947,39 +19947,69 @@ class EstreeObject extends LazyLocNode {
1994719947
* @template {Int32Array | Uint16Array | Uint8Array} T
1994819948
* @param {T} array the column to grow
1994919949
* @param {number} capacity the length it needs at least
19950+
* @param {number} hint the length the last released tree needed
1995019951
* @returns {T} the column, or a copy holding at least `capacity` entries
1995119952
*/
19952-
const growColumn = (array, capacity) => {
19953+
const growColumn = (array, capacity, hint) => {
1995319954
if (capacity <= array.length) return array;
1995419955
const copy = /** @type {T} */ (
1995519956
new /** @type {new (length: number) => T} */ (array.constructor)(
19956-
Math.max(array.length * 2, capacity, 1024)
19957+
Math.max(array.length * 2, capacity, hint, 1024)
1995719958
)
1995819959
);
1995919960
copy.set(array);
1996019961
return copy;
1996119962
};
1996219963

19964+
// Released columns all share these: growth replaces a column before any write.
19965+
const EMPTY_U8 = new Uint8Array(0);
19966+
const EMPTY_U16 = new Uint16Array(0);
19967+
const EMPTY_I32 = new Int32Array(0);
19968+
// WHY: as the CSS and HTML columns are, a released tree's columns are reused
19969+
// by the next tree up to this many nodes, and let go past it. Either way the
19970+
// next tree grows straight to what the last one needed rather than doubling.
19971+
const SHRINK_CAPACITY = 65536;
19972+
/** @type {SyntaxTree | null} */
19973+
let spareTree = null;
19974+
let nodeHint = 0;
19975+
let slotHint = 0;
19976+
let listHint = 0;
19977+
let listItemHint = 0;
19978+
1996319979
/**
1996419980
* A JavaScript syntax tree held as a struct of arrays: a node is an integer
1996519981
* id from 1, `0` is no node, and it reads as the CSS and HTML paths do.
1996619982
*/
1996719983
class SyntaxTree {
1996819984
constructor() {
1996919985
this._count = 0;
19970-
this._types = new Uint8Array(0);
19971-
this._starts = new Int32Array(0);
19972-
this._ends = new Int32Array(0);
19973-
this._flags = new Uint16Array(0);
19974-
this._bases = new Int32Array(0);
19975-
this._complete = new Uint8Array(0);
19976-
this._slots = new Int32Array(0);
19986+
this._types = EMPTY_U8;
19987+
this._starts = EMPTY_I32;
19988+
this._ends = EMPTY_I32;
19989+
this._flags = EMPTY_U16;
19990+
this._bases = EMPTY_I32;
19991+
this._complete = EMPTY_U8;
19992+
this._slots = EMPTY_I32;
1997719993
this._slotTop = 0;
19978-
this._listStarts = new Int32Array(0);
19979-
this._listLengths = new Int32Array(0);
19994+
this._listStarts = EMPTY_I32;
19995+
this._listLengths = EMPTY_I32;
1998019996
this._listCount = 0;
19981-
this._listItems = new Int32Array(0);
19997+
this._listItems = EMPTY_I32;
1998219998
this._listItemTop = 0;
19999+
const spare = spareTree;
20000+
if (spare !== null) {
20001+
spareTree = null;
20002+
this._types = spare._types;
20003+
this._starts = spare._starts;
20004+
this._ends = spare._ends;
20005+
this._flags = spare._flags;
20006+
this._bases = spare._bases;
20007+
this._complete = spare._complete;
20008+
this._slots = spare._slots;
20009+
this._listStarts = spare._listStarts;
20010+
this._listLengths = spare._listLengths;
20011+
this._listItems = spare._listItems;
20012+
}
1998320013
/** @type {(TreeValue | undefined)[]} */
1998420014
this._values = [];
1998520015
/** @type {(EstreeObject | undefined)[]} */
@@ -20000,46 +20030,66 @@ class SyntaxTree {
2000020030
}
2000120031

2000220032
/**
20003-
* Lets go of every column now, rather than when a collection reaches the
20004-
* tree: an ArrayBuffer that can be transferred frees its memory at once,
20005-
* where it would otherwise outlast the parse into the work after it.
20033+
* Hands the columns back once nothing reads the tree: the next tree reuses
20034+
* small ones, and a large one's ArrayBuffers are freed at once, where they
20035+
* would otherwise outlast the parse into the work after it.
2000620036
* @returns {void}
2000720037
*/
2000820038
release() {
20009-
const columns = [
20010-
this._types,
20011-
this._starts,
20012-
this._ends,
20013-
this._flags,
20014-
this._bases,
20015-
this._complete,
20016-
this._slots,
20017-
this._listStarts,
20018-
this._listLengths,
20019-
this._listItems
20020-
];
20021-
for (const column of columns) {
20022-
const buffer =
20023-
/** @type {ArrayBuffer & { transfer?: (length: number) => ArrayBuffer }} */ (
20024-
column.buffer
20025-
);
20026-
if (typeof buffer.transfer === "function" && buffer.byteLength > 0) {
20027-
buffer.transfer(0);
20039+
nodeHint = this._count + 1;
20040+
slotHint = this._slotTop;
20041+
listHint = this._listCount + 1;
20042+
listItemHint = this._listItemTop;
20043+
if (this._types.length > SHRINK_CAPACITY) {
20044+
const columns = [
20045+
this._types,
20046+
this._starts,
20047+
this._ends,
20048+
this._flags,
20049+
this._bases,
20050+
this._complete,
20051+
this._slots,
20052+
this._listStarts,
20053+
this._listLengths,
20054+
this._listItems
20055+
];
20056+
for (const column of columns) {
20057+
const buffer =
20058+
/** @type {ArrayBuffer & { transfer?: (length: number) => ArrayBuffer }} */ (
20059+
column.buffer
20060+
);
20061+
if (typeof buffer.transfer === "function" && buffer.byteLength > 0) {
20062+
buffer.transfer(0);
20063+
}
2002820064
}
20065+
} else if (spareTree === null && this._types.length > 0) {
20066+
this._complete.fill(0, 0, this._count + 1);
20067+
const spare = new SyntaxTree();
20068+
spare._types = this._types;
20069+
spare._starts = this._starts;
20070+
spare._ends = this._ends;
20071+
spare._flags = this._flags;
20072+
spare._bases = this._bases;
20073+
spare._complete = this._complete;
20074+
spare._slots = this._slots;
20075+
spare._listStarts = this._listStarts;
20076+
spare._listLengths = this._listLengths;
20077+
spare._listItems = this._listItems;
20078+
spareTree = spare;
2002920079
}
2003020080
this._count = 0;
20031-
this._types = new Uint8Array(0);
20032-
this._starts = new Int32Array(0);
20033-
this._ends = new Int32Array(0);
20034-
this._flags = new Uint16Array(0);
20035-
this._bases = new Int32Array(0);
20036-
this._complete = new Uint8Array(0);
20037-
this._slots = new Int32Array(0);
20081+
this._types = EMPTY_U8;
20082+
this._starts = EMPTY_I32;
20083+
this._ends = EMPTY_I32;
20084+
this._flags = EMPTY_U16;
20085+
this._bases = EMPTY_I32;
20086+
this._complete = EMPTY_U8;
20087+
this._slots = EMPTY_I32;
2003820088
this._slotTop = 0;
20039-
this._listStarts = new Int32Array(0);
20040-
this._listLengths = new Int32Array(0);
20089+
this._listStarts = EMPTY_I32;
20090+
this._listLengths = EMPTY_I32;
2004120091
this._listCount = 0;
20042-
this._listItems = new Int32Array(0);
20092+
this._listItems = EMPTY_I32;
2004320093
this._listItemTop = 0;
2004420094
this._values = [];
2004520095
this._objects = [];
@@ -20091,7 +20141,9 @@ class SyntaxTree {
2009120141
const base = this._slotTop;
2009220142
const top = base + slotCount;
2009320143
this._slotTop = top;
20094-
if (top > this._slots.length) this._slots = growColumn(this._slots, top);
20144+
if (top > this._slots.length) {
20145+
this._slots = growColumn(this._slots, top, slotHint);
20146+
}
2009520147
this._types[node] = type;
2009620148
this._starts[node] = start;
2009720149
this._ends[node] = end;
@@ -20105,12 +20157,12 @@ class SyntaxTree {
2010520157
* @returns {void}
2010620158
*/
2010720159
_growNodes(capacity) {
20108-
this._types = growColumn(this._types, capacity);
20109-
this._starts = growColumn(this._starts, capacity);
20110-
this._ends = growColumn(this._ends, capacity);
20111-
this._flags = growColumn(this._flags, capacity);
20112-
this._bases = growColumn(this._bases, capacity);
20113-
this._complete = growColumn(this._complete, capacity);
20160+
this._types = growColumn(this._types, capacity, nodeHint);
20161+
this._starts = growColumn(this._starts, capacity, nodeHint);
20162+
this._ends = growColumn(this._ends, capacity, nodeHint);
20163+
this._flags = growColumn(this._flags, capacity, nodeHint);
20164+
this._bases = growColumn(this._bases, capacity, nodeHint);
20165+
this._complete = growColumn(this._complete, capacity, nodeHint);
2011420166
}
2011520167

2011620168
/**
@@ -20174,7 +20226,9 @@ class SyntaxTree {
2017420226
const base = this._slotTop;
2017520227
const top = base + count;
2017620228
this._slotTop = top;
20177-
if (top > this._slots.length) this._slots = growColumn(this._slots, top);
20229+
if (top > this._slots.length) {
20230+
this._slots = growColumn(this._slots, top, slotHint);
20231+
}
2017820232
this._types[node] = type;
2017920233
this._starts[node] = start;
2018020234
this._ends[node] = end;
@@ -20348,11 +20402,15 @@ class SyntaxTree {
2034820402
*/
2034920403
_reserveList(length) {
2035020404
const list = ++this._listCount;
20351-
this._listStarts = growColumn(this._listStarts, list + 1);
20352-
this._listLengths = growColumn(this._listLengths, list + 1);
20405+
this._listStarts = growColumn(this._listStarts, list + 1, listHint);
20406+
this._listLengths = growColumn(this._listLengths, list + 1, listHint);
2035320407
const start = this._listItemTop;
2035420408
this._listItemTop += length;
20355-
this._listItems = growColumn(this._listItems, this._listItemTop);
20409+
this._listItems = growColumn(
20410+
this._listItems,
20411+
this._listItemTop,
20412+
listItemHint
20413+
);
2035620414
this._listItems.fill(0, start, this._listItemTop);
2035720415
this._listStarts[list] = start;
2035820416
this._listLengths[list] = length;

‎test/unitCases/JavascriptSyntaxTree.unittest.js‎

Lines changed: 34 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -328,31 +328,58 @@ describe("SyntaxTree", () => {
328328
expect(tree.name(tree.field(0, Field.argument, spread))).toBe("c");
329329
});
330330

331-
it("lets go of its columns once released", () => {
332-
const tree = new SyntaxTree();
333-
const program = /** @type {number} */ (
331+
/**
332+
* @param {SyntaxTree} tree the tree to write
333+
* @param {string} source the source
334+
* @returns {number} its program
335+
*/
336+
const parseInto = (tree, source) =>
337+
/** @type {number} */ (
334338
/** @type {unknown} */ (
335339
new WebpackParser(
336340
{ ecmaVersion: "latest", lazyNodes: true, syntaxTree: tree },
337-
"a(b, [c]);"
341+
source
338342
).parse()
339343
)
340344
);
341-
expect(tree.type(program)).toBe(NodeType.Program);
345+
346+
it("hands a small tree's columns to the next tree, cleared", () => {
347+
const tree = new SyntaxTree();
348+
parseInto(tree, "x = { a: [b, c], [d]: `e${f}` };");
342349
const types = tree._types;
343-
const items = tree._listItems;
344350
tree.release();
345351
expect([tree._types.length, tree._values.length, tree._listCount]).toEqual([
346352
0, 0, 0
347353
]);
354+
const next = new SyntaxTree();
355+
expect(next._types).toBe(types);
356+
const source = "a(b, [c]);";
357+
const program = parseInto(next, source);
358+
const fresh = new SyntaxTree();
359+
expect(toEstreeObject(next, program)).toEqual(
360+
toEstreeObject(fresh, parseInto(fresh, source))
361+
);
362+
next.release();
363+
});
364+
365+
it("lets go of a large tree's columns, and the next grows to its size", () => {
366+
const tree = new SyntaxTree();
367+
parseInto(tree, "a;".repeat(40000));
368+
const types = tree._types;
369+
const nodes = tree._count;
370+
tree.release();
348371
// A runtime that transfers an ArrayBuffer frees the old one at once.
349372
const detached =
350373
typeof (
351374
/** @type {ArrayBuffer & { transfer?: unknown }} */ (
352375
new ArrayBuffer(0)
353376
).transfer
354377
) === "function";
355-
expect(types.byteLength === 0 && items.byteLength === 0).toBe(detached);
378+
expect(types.byteLength === 0).toBe(detached);
379+
const next = new SyntaxTree();
380+
expect(next._types).not.toBe(types);
381+
next.add(NodeType.Identifier, 0, 1);
382+
expect(next._types.length).toBe(nodes + 1);
356383
});
357384

358385
it("refuses an unknown type or field", () => {

‎types.d.ts‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -34804,9 +34804,9 @@ declare class SyntaxTree {
3480434804
constructor();
3480534805

3480634806
/**
34807-
* Lets go of every column now, rather than when a collection reaches the
34808-
* tree: an ArrayBuffer that can be transferred frees its memory at once,
34809-
* where it would otherwise outlast the parse into the work after it.
34807+
* Hands the columns back once nothing reads the tree: the next tree reuses
34808+
* small ones, and a large one's ArrayBuffers are freed at once, where they
34809+
* would otherwise outlast the parse into the work after it.
3481034810
*/
3481134811
release(): void;
3481234812

0 commit comments

Comments
 (0)