perf: reducing ast node memory overhead

[thebanjomatic]

This PR contains:

• bugfix
• feature
• refactor
• documentation
• other

Are tests included?

• yes (bugfixes and features will not be merged without tests)
• no

Breaking Changes?

• yes (breaking changes will not be merged unless absolutely necessary)
• no

List any relevant issue numbers:

resolves #5127

Description

This PR implements the suggestions outlined in the linked issue and reduces the memory overhead of the AST that rollup creates for each source file. Note: I have split the changes into 4 distinct commits that should be easier to review individually.

I have primarily been testing on one large project which is a storybook application building with vite and by extension, building with rollup. As mentioned in the issue, the aim of these 4 commits is to reduce the object size for each node instance since there are millions of node instances, shaving a few bytes here and there can lead to tangible memory reductions.

To validate the memory savings, I took heap snapshots using the node devtools, but I also found it useful to identify the value for --max-old-space-size at which point the build runs out of memory and node stack dumps. This is a rough measurement because I only found this value to the nearest 25MB. I also tested using 3.26.0 to capture the heap size reduction from #5075 as my current test project is a different project than the one I was testing with in that PR.

• 3.26.0: --max-old-space-size works at 2750 MB & crashes at 2725 MB
• 3.29.0: --max-old-space-size works at 2425 MB & crashes at 2400 MB
• this PR: --max-old-space-size works at 2250 MB & crashes at 2225 MB

So for this particular build, it was able to complete with around 175MB less memory which lines up with what I saw in the heap snapshots (170 MB).

As far as build times are concerned, the linked issue had some concerns about extra overhead due to needing to do bitwise operations instead of simpler boolean access patterns. I also had concerns when developing the last commit in particular (perf: make ast fields optional instead of null) about whether or not making that change would reduce build performance due to creating more hidden classes and maybe some functions would no longer be monomorphic. After identifying and fixing a bug in one of my optimizations, I don't really see any noticeable runtime performance difference with this PR.

I tested the same builds as above and found the time difference was within the noise threshold:

• 3.26.0: Average build time: 31.378 seconds (averaged over 25 builds)
• 3.29.0: Average build time: 31.267 seconds (averaged over 100 builds)
• this PR: Average build time: 31.259 seconds (averaged over 100 builds)

The last commit which switches from null to optional / undefined is perhaps the most controversial of the changes, so I wanted to also test without that change and allow the maintainers to determine whether or not to pursue that, or it can be split to its own PR if we feel like more testing / validation is needed.

Measuring with a heap snapshot taken just before await renderChunks gets called inside of generate():
Heap Size without last commit: 1564 MB
Heap Size with last commit: 1555 MB

So that commit contributes 9 MB to the 170 MB reduction and it would be at 161 MB otherwise.

[vercel]

The latest updates on your projects. Learn more about Vercel for Git ↗︎

Name	Status	Preview	Comments	Updated (UTC)
rollup	✅ Ready (Inspect)	Visit Preview	💬 Add feedback	Oct 14, 2023 4:51am

[thebanjomatic]

Looking into test failures. I don't recall seeing them locally, but I think that's because it was failing in test:only on the symlinked config tests which don't seem to ever work for me on windows.

[Update]
Looks like in one of the setters, we weren't assigning the new flag value:

Fixed and rebased.

Also, I figured out why I couldn't run the tests and created a doc PR to update the contributing guide: #5134

[codecov]

Codecov Report

Merging #5133 (5bfce4f) into master (e2f947f) will decrease coverage by 0.04%.
The diff coverage is 97.53%.

@@            Coverage Diff             @@
##           master    #5133      +/-   ##
==========================================
- Coverage   98.86%   98.82%   -0.04%     
==========================================
  Files         230      231       +1     
  Lines        8805     8849      +44     
  Branches     2314     2314              
==========================================
+ Hits         8705     8745      +40     
- Misses         39       43       +4     
  Partials       61       61              

Files	Coverage Δ
src/ast/keys.ts	100.00% <100.00%> (ø)
src/ast/nodes/ArrayExpression.ts	100.00% <100.00%> (ø)
src/ast/nodes/ArrowFunctionExpression.ts	95.45% <100.00%> (ø)
src/ast/nodes/AssignmentExpression.ts	100.00% <100.00%> (ø)
src/ast/nodes/AssignmentPattern.ts	100.00% <100.00%> (ø)
src/ast/nodes/AwaitExpression.ts	100.00% <100.00%> (ø)
src/ast/nodes/BlockStatement.ts	100.00% <100.00%> (ø)
src/ast/nodes/CallExpression.ts	100.00% <100.00%> (ø)
src/ast/nodes/CatchClause.ts	100.00% <100.00%> (ø)
src/ast/nodes/ClassBody.ts	100.00% <100.00%> (ø)
... and 47 more

[TrickyPi]

Nice work!

The last commit which switches from null to optional / undefined is perhaps the most controversial of the changes, so I wanted to also test without that change and allow the maintainers to determine whether or not to pursue that, or it can be split to its own PR if we feel like more testing / validation is needed.

If this commit does not significantly reduce memory size (I personally think the 9MB memory increase is acceptable), I prefer null to optional/undefined, Because currently the actual value of the changed properties is null.

I have some quesions, Are the memory sizes of null and undefined the same? If same, Why is the heap snapshot different?

[thebanjomatic]

@TrickyPi the size of null or undefined would be the same. The key difference here is that we don't ever set these values to undefined, but they are instead unset if there is no value. When you read these properties it comes back as undefined, but the properties aren't allocated on the object.

[TrickyPi]

@TrickyPi the size of null or undefined would be the same. The key difference here is that we don't ever set these values to undefined, but they are instead unset if there is no value. When you read these properties it comes back as undefined, but the properties aren't allocated on the object.

Oh, I see! I've only seen some declaration properties before. For some properties that are initialized in Rollup, such as includedLabelsAfterBlock in src/ast/nodes/TryStatement.ts, I think switching null to optional undefined is really nice. But for some properties initialized in the ast parser (acorn or swc), such as init in src/ast/nodes/VariableDeclarator.ts. In other words, the types of these properties are defined in the ESTree standard. We should preserve these types unless we modify these values when generating Rollup ast nodes.

[thebanjomatic]

For some properties that are initialized in Rollup, such as includedLabelsAfterBlock in src/ast/nodes/TryStatement.ts, I think switching null to optional undefined is really nice. But for some properties initialized in the ast parser (acorn or swc), such as init in src/ast/nodes/VariableDeclarator.ts. In other words, the types of these properties are defined in the ESTree standard. We should preserve these types unless we modify these values when generating Rollup ast nodes.

What I don't like about that approach is there is less uniformity in the values and you'd have to know why some properties check !== null and other check !== undefined or alternatively we could change all the checks to != null or == null to include both null and undefined instead of using strict equality. But I agree if its a goal of the rollup ast nodes to conform to the api specification for the estree nodes, then its probably better not to make that change.

[lukastaegert]

Nice work!

[lukastaegert]

As for the general null vs undefined discussion, I am not sure. I think the gains are not much, but it creates some weird artifacts in places. And before, this code base was consistently using explicit nulls to denote things that are absent, which is now no longer the case. I wonder why there was not much performance impact due to polymorphic functions, though. My guess is that all relevant functions were already polymorphic to start with. But this may not be the case for all future.

[TrickyPi]

What I don't like about that approach is there is less uniformity in the values and you'd have to know why some properties check !== null and other check !== undefined or alternatively we could change all the checks to != null or == null to include both null and undefined instead of using strict equality

I think TS types prompt can help us know if the value is null or undefined when checking.

But I agree if its a goal of the rollup ast nodes to conform to the api specification for the estree nodes, then its probably better not to make that change

I'm not sure about it. There is another reason is that we should keep the type of property to correspond with its value, we shouldn't declare the type of property is undenfined if its value is null, which may cause some bugs in the future. Also, I think swtiching its (such as init 3d23432#diff-8837bc36168c9214688ff3bf73dbf0e898160e59da39b5d47f5cdc138d9c54abL20) type from null to optional undefined does not reduce the memory overhead becasue of it may have been initialized to null in the ast parser.

Oh, sorry! I just ran the thebanjomatic:perf/memory-packing branch, the properties with a value of null were deleted.

[thebanjomatic]

I'm collecting the feedback from above and testing a few different approaches with some more extensive profiling runs with around 100 build iterations each.

I'm pretty sure when I switched to using member functions there was a regression and performance and I'm trying to track that down while keeping the code as clean as possible.

The main things I'm testing:

• 3.29.1 baseline
• member function this.setFlag(Flag.included)
• member function with const enum inlined: this.setFlag(1 /* Flag.included */)
• free function + const enum: this.flags = this.setFlag(this.flags, 1 /* Flag.included */) (I suspect this will effectively inline the actual bitwise math functions as they are pure functions)
• explicitly inlined getter/setter math: get included() { return (this.flags | 1 /* Flag.included */) !== 0; }

[thebanjomatic]

I did a smaller sample size on my local machine with 50 builds in each case. I'm still running a larger sample on an linux server, but the time variations were a bit wider than I was expecting and have some trends in the data, so I'm thinking of throwing that data out and just sticking with my local builds where the times are more consistent.

3.29.1 results:
Average Build Time: 33.097188782001716 seconds
Median Build Time: 32.997493799984454 seconds
Standard Deviation: 0.5184838707641164 seconds


const-enum free results:
Average Build Time: 32.71339418800355 seconds
Median Build Time: 32.69009659999609 seconds
Standard Deviation: 0.3665153691957943 seconds


const-enum member results:
Average Build Time: 33.33051260400176 seconds
Median Build Time: 33.28499439996481 seconds
Standard Deviation: 0.39615841275453434 seconds


enum member results:
Average Build Time: 33.497370042004576 seconds
Median Build Time: 33.50463529998064 seconds
Standard Deviation: 0.2266072128625438 seconds


const-enum inlined results:
Average Build Time: 32.91166543799757 seconds
Median Build Time: 32.90600040000677 seconds
Standard Deviation: 0.36886093374144213 seconds

---

With those results in mind, I can now do a larger sample size focusing on just:

• 3.29.1
• const-enum + free functions
• enum + free functions

To see if there is any benefit to changing the isolatedModules tsconfig option, and if the new code actually is faster than the old code which appears to be the case.

[lukastaegert]

I would also expect member functions to be slower because even it they are inlined in some cases, the inlining would need to be deoptimized again once anything changes about the hidden class, and then you have the property access again.

[jerome-benoit]

I did a smaller sample size on my local machine with 50 builds in each case. I'm still running a larger sample on an linux server, but the time variations were a bit wider than I was expecting and have some trends in the data, so I'm thinking of throwing that data out and just sticking with my local builds where the times are more consistent.

The enum member implementation seems to give stable result over time, allowing more predictable build time.
Ideally, the benchmark should be run on various OS and arch.
How are you doing the benchmark (tools)? Can it be implemented as a GH workflow? Or as a script?

[thebanjomatic]

Its really hard to draw performance conclusions out of the tests I've been doing because the build I'm using is rather large and takes 30+ seconds to complete, plus its also using vite and storybook on top of rollup, touches lots of files, etc. So we are bringing in lots of other factors at the same time. Its an internal project at the company I work for, so I can't share that particular test more broadly. I did test an an m7i-2xlarge instance running linux on aws as well, but as mentioned previously there was a lot of variation over time which made the results unusable.

I actually ran into similar problems when running the tests on my local machine with a larger iteration count (200 vs 50 from above).

Basically 3/4 of the way through the run the numbers flipped, so If I stopped at 100 iterations I would have gotten a different result. Its visible when looking at all the build times graphed, but becomes a lot more obvious when looking at the cumulative average or the 50 build moving average in the graphs below.

It's hard to eliminate the potential for things like virus scans or software compliance scans from running arbitrarily in the middle of the night which might only run during one particular test run when each test run takes over 2 hours to run (200 * 32 second average build time + 8 seconds of cooldown between builds to allow enough time for the cpu fans to stop).

I'm tempted to say its all just within the limits of noise, but there is a 2% difference between the final averages in the latest run.

[thebanjomatic]

My next thing to try is basically:

1. Interleave the builds so that we test A, B C, A, B, C, A, B, C instead of A, A, A, B, B, B, C, C, C that way any trends over time would be more likely to apply to all of the different test cases equally. That way the averages would be more directly comparable.

2. I need to test with a smaller build that runs quicker so that I can do more iterations in a shorter period of time. It would also be good to look at something that is only using rollup. My current plan is to just create a simple project that just uses rollup by itself and bundles and re-exports a few libraries (d3, lodash-es, and three.js). That currently takes about 3.5 seconds so I should be able to do almost 10x as many iterations in the same amount of time.

[jerome-benoit]

Its really hard to draw performance conclusions out of the tests I've been doing.

If you share the code to perform the benchmark, maybe people following the PR will also run it to confirm or infirm the results and their trends.

[thebanjomatic]

@jerome-benoit I moved the benchmark scaffolding into its own repo you can clone and run yourself:

https://github.com/thebanjomatic/test-rollup-perf/

I can't share my larger test case, but you can modify test.js to call into a separate build and modify where the node-entry.js file is copied in profile.js etc.

The code that is in there is just bundling three.js, lodash-es, and d3 into a single bundled js file with sourcemaps and takes about 4.5 seconds for me to run vs 32 seconds for my other build.

It also uses the interleaved approach described above so it should hopefully produce more consistent results. Test run is still in progress....

[jerome-benoit]

@jerome-benoit I moved the benchmark scaffolding into its own repo you can clone and run yourself:

https://github.com/thebanjomatic/test-rollup-perf/

I think tomorrow I will be able to give it a try.

Thanks.

[thebanjomatic]

Using the smaller test case, and the csv generated by that benchmark app, the data looks a lot more reasonable.

Moving average of 50 build | Absolute build times (the time trends are now in sync):

Moving average of 50 builds | % change vs 3.29.1 baseline:

1% slower for the version that doesn't modify the null/optional behavoir
2% slower for the version that does.

But in terms of absolute change (+/- 1 standard deviation):

3.29.1 results
Average Build Time: 3.975441594825 seconds +/- 0.07333327499484146 seconds

const-enum-free results:
Average Build Time: 4.0623456295599745 seconds +/- 0.07575500229998594 seconds

without-optional results:
Average Build Time: 4.019510607534976 seconds +/- 0.07868290850560891 seconds

[thebanjomatic]

Did some instrumentation to figure out how many times each flag is getting read/written to, so we might be able to get some of that performance back by doing things as discussed like removing the extra indirection for the getter/setter for things for the more heavily used properties:

flag: optional | get: 0, set: 50257
flag: method | get: 0, set: 3679
flag: prefix | get: 0, set: 2739
flag: tail | get: 0, set: 395
flag: await | get: 0, set: 72
flag: directlyIncluded | get: 0, set: 88350
flag: deoptimizedReturn | get: 2, set: 1
flag: hasUnknownDeoptimizedInteger | get: 1029, set: 133
flag: async | get: 8568, set: 5433
flag: shorthand | get: 14716, set: 3679
flag: hasUnknownDeoptimizedProperty | get: 15075, set: 64
flag: bound | get: 36320, set: 36218
flag: isBranchResolutionAnalysed | get: 52799, set: 4157
flag: hasLostTrack | get: 70365, set: 11543
flag: assignmentDeoptimized | get: 81332, set: 7118
flag: computed | get: 103108, set: 41514
flag: tdzAccess | get: 142334, set: 93601
flag: deoptimizeBody | get: 188423, set: 9651
flag: isUndefined | get: 216776, set: 0
flag: tdzAccessDefined | get: 235935, set: 93601
flag: deoptimized | get: 2800106, set: 250125
flag: included | get: 3388188, set: 1523596

[thebanjomatic]

There doesn't appear to be any benefit to removing the isFlagSet / setFlag helper functions and directly inlining the math into the getters/setters directly:

I can still try avoiding the included getter/setter and and just do the math directly and see how that effects performance, but it might just be the cost of doing 7 million bit-math operations compared to 7 million property acesses.

I'll also run a test with "asm.js" style code for the math to try to force it to treat the numbers as int32 values. I'm not sure if those optimizations are still relevant these days with modern v8, but seems worth a shot. At first glance, it doesn't appear to make a difference though.

function isFlagSet(flags, flag) {
    return ((flags|0) & (flag|0)) !== 0;
}
function setFlag(flags, flag, value) {
    var flag32 = flag|0;
    return ((flags|0) & ~flag32) | (((-value)|0) & flag32);
}

[jerome-benoit]

@jerome-benoit I moved the benchmark scaffolding into its own repo you can clone and run yourself:
https://github.com/thebanjomatic/test-rollup-perf/

I think the project would benefit from running a lightweight benchmark on each PRs with report as a github CI workflow to trap obvious performance regression before they go in.

[lukastaegert]

Sorry this got a little stale. The main reason were efforts to finalize and release Rollup 4. If this PR can be updated accordingly, I would still be interested in merging this soon.

[thebanjomatic]

@lukastaegert No problem, I figured the other 4.0 stuff was more important at the time. I'm still a little torn on this optimization as it does consistently build a little slower after this change, but uses less memory in the process. Perhaps the SWC performance improvements will even things out a little. I wasn't able to try it sooner than that because I was getting a ton of errors trying to build with the swc PR a few weeks back, but I will at least rebase this PR now that that is merged and then we can see where things are at.

[jerome-benoit]

I'm still a little torn on this optimization as it does consistently build a little slower after this change, but uses less memory in the process.

What is the root cause of the slowdown?

[thebanjomatic]

@jerome-benoit Between the deoptimized and included flags, they are checked 6.1 million times and set 1.7 million times which was previously just a property access on the object, but now is a property access and some math. I think because of how frequently we access these properties the overhead show, and we don't necessarily save enough memory to result in less garbage collection, etc., to make up for the difference.

However, if we just use regular booleans for those two flags, we also lose a lot of the memory savings from this change.

Its not really drastically slower either, it was 1% slower overall. I think we just need to make a decision about whether or not the juice is worth the squeeze.

[jerome-benoit]

Its not really drastically slower either, it was 1% slower overall. I think we just need to make a decision about whether or not the juice is worth the squeeze.

The tradeoff between the overall memory usage reduction and the very small building time slowdown "regression" seems reasonable.

[lukastaegert]

There are still some open conversations, do we want to address them before merging?

[thebanjomatic]

@lukastaegert I have resolved all the open conversations. I decided it was probably best to defer one task to a separate/future PR: #5133 (comment) let me know if you would prefer I do that refactor before merging, or if it is ok to merge as is.

[lukastaegert]

Looks good to me!

[github-actions]

This PR has been released as part of rollup@4.1.0. You can test it via npm install rollup.