perf: use pre-allocated arrays for known result sizes #5703
Conversation
|
The latest updates on your projects. Learn more about Vercel for Git ↗︎
|
Codecov ReportAll modified and coverable lines are covered by tests ✅
Additional details and impacted files@@ Coverage Diff @@
## master #5703 +/- ##
==========================================
- Coverage 99.03% 99.01% -0.02%
==========================================
Files 257 257
Lines 8044 8055 +11
Branches 1357 1358 +1
==========================================
+ Hits 7966 7976 +10
Misses 52 52
- Partials 26 27 +1 ☔ View full report in Codecov by Sentry. |
|
I haven't yet added all of the files I wanted, but the failure appears to prioritize the push method, which is basically directly against what this PR aims to do |
|
Tip: If you want to change anything in bufferParsers or bufferToAst, heed the tip at the top of the file that these files are entirely generated code. They will be overwritten by a full build and are mostly checked in so that you can compare and inspect the code and that TypeScript does not complain. Otherwise, I am definitely curious to see if this provides any tangible performance benefits, especially in the generated code it would be a quick win. |
|
Ah, I didn't know they were generated. I was so used to the scripts directory being for miscellaneous actions like bumping releases, that I didn't even decide to take a look there, that was my bad. I'll update them soon. As for the performance, constant time always wins against amortized constant time (constant being pre allocated array, and amortized being push). That's because every once in a while push will not be O(1) but rather O(n) because the engine will need to copy it to a new, bigger array, in order to adjust for the growth. With pre-allocated array, the engine can immediately allocate the necessary space which will prevent dynamic resizing. In terms of memory, the difference is even more significant than that of the performance, because the entire operation will be much more memory efficient, due to the elimination of the dynamic resizing. This removes the pressure on the GC that exists when dynamically pushing to an unknown final size. We can make a quick calculation to see how much more efficient it is: If we take a look at a 100 element array, it would go as follows: Total amount of memory used would be 12 + 24 + 48 + 96 + 192 = 372 bytes With the pre allocated array method, we directly reserve spots for 100 bytes. That means the push method will use almost x4 more memory for just 100 elements |
|
I understand the theory. However, if the impact turns out to be close to not-measurable, I would suggest to limit these kind of changes only to hot code paths as of course they are not entirely free, they make the code slightly less straightforward to read and maintain. |
I can't help but to think about resource-constrained environments in this case. I agree, on unbound computers this may not be of any significance, but on computers with limited resources this could be a significant change, especially considering memory itself is more of a bottleneck than performance in most cases. I also believe that objectively speaking, even if the readability is a bit impacted by it, it's very minimal. Most of the syntax it's the same, and I believe people are familiar with array access, even if they are unaware of low-level optimizations like pre-allocated arrays. But of course, the final decision will be up to you. It goes without saying that the difference becomes more noticeable the more elements are in the array, so if there are some arrays in this PR that are not influenced by user-code and are purely internally managed, then if you'd like we could revert them. But for anything that can directly be affected by the code it is bundling, then it would likely be better, for performance, to keep them with the current approach, just for the slight chance it would be exceptionally big. |
Thank you for your contribution! ❤️You can try out this pull request locally by installing Rollup via npm install GalacticHypernova/rollup#patch-1Notice: Ensure you have installed the latest stable Rust toolchain. If you haven't installed it yet, please see https://www.rust-lang.org/tools/install to learn how to download Rustup and install Rust. or load it into the REPL: |
Performance report
|
|
I am just saying that I wanted to wait for the measurements. And the measurements do support your approach. While apparently performance changes were negligible, the changes seem to save 3-5% memory in the test, which is good enough for me to keep the changes. In order to merge this, could you please run |
|
Sure thing, thanks! I apologize if I seemed overly pushy about this. I'm just trying to contribute as much as I can and I know memory efficiency is a hugely overlooked, yet equally important, aspect in performance, given that most people only pay attention strictly to runtime performance (speed of execution), without worrying about the memory due to the GC being a thing. I also didn't know that rollup has its own memory benchmark, so I wanted to explain essentially what the benchmark showed but in my own words Edit: I might need a little more to fix the AST generators |
|
And this is really appreciated, I hope I did not sound too negative. Honestly I never thought too much about this aspect before and am positively surprised that it really does make a measurable impact in our benchmark. |
Yea, the issue isn't the lint. For some reason it says the husky pre-commit script failed so I have to manually update from GitHub itself, one by one. I believe I fixed it all, but I could be wrong. Would appreciate if you could review to see if I missed anything related to the PR |
|
Looks good. Not sure what is up with husky but in the worst case, you can add |
|
This PR has been released as part of rollup@4.24.3. You can test it via |
This PR contains:
Are tests included?
Breaking Changes?
List any relevant issue numbers:
Description
When the final size of an array is known, it would be more performant to use a pre-allocated array. This will prevent the internal resizing that happens when
Array.prototype.pushexceeds the array's memory allocation, which the JS engine will then internally re-allocate and apply unnecessary pressure on the GC to clean up the "dead" memory.Note: This PR is a draft because I will add all relevant files in this single PR, which might take some time