FazBrowse GitHub Viewer | Trending |
URL:
| Home
Tools: [Download Repo ZIP]   [Original HTTPS Page]

lib: optimize FixedQueue by reusing one segment by gurgunday · Pull Request #60031 · nodejs/node · GitHub

/ node Public

lib: optimize FixedQueue by reusing one segment - #60031

Closed
gurgunday wants to merge 1 commit into
nodejs:mainfrom
gurgunday:fixed-queue
ConversationCommits (1)ChecksFiles changed
Closed

lib: optimize FixedQueue by reusing one segment#60031
gurgunday wants to merge 1 commit into
nodejs:mainfrom
gurgunday:fixed-queue

Conversation

gurgunday commented Sep 27, 2025 •
edited
Loading

Copy link
Copy Markdown
Member

Benchmarks:

main:

node % ./node benchmark/run.js --filter fixed-queue util
util/fixed-queue-oscillate.js
util/fixed-queue-oscillate.js cycles=5000: 240,760,722.06068513
util/fixed-queue.js
util/fixed-queue.js n=100000: 30,605,608.47775355

branch:

node % ./node benchmark/run.js --filter fixed-queue util
util/fixed-queue-oscillate.js
util/fixed-queue-oscillate.js cycles=5000: 283,339,287.4243814
util/fixed-queue.js
util/fixed-queue.js n=100000: 32,606,927.0808029

When the head segment fills, we reuse a “spare” FixedCircularBuffer if available; when a segment becomes empty, we reset it and stash it as the spare instead of wasting it. This cuts allocations/GC especially when the queue oscillates between N and N+1 segments, which is more than likely to be the case in real life scenarios where Events/Promises/Tasks are emitted/created and consumed in bursts.

We only call reset() when reusing a spare (not for a freshly allocated buffer).

And finally, there is no behavior change: we have the same data structure (linked fixed-size circular buffers), same invariants (one-slot-wasted), same FIFO semantics and API. Capacity per segment stays kSize - 1, so overall capacity is unchanged.

nodejs-github-bot commented Sep 27, 2025

Copy link
Copy Markdown
Collaborator

Review requested:

  • @nodejs/performance

nodejs-github-bot added the needs-ci PRs that need a full CI run. label Sep 27, 2025
Uzlopak reviewed Sep 27, 2025
View reviewed changes
Comment thread lib/internal/fixed_queue.js Outdated

codecov Bot commented Sep 27, 2025 •
edited
Loading

Copy link
Copy Markdown

Codecov Report

✅ All modified and coverable lines are covered by tests.
✅ Project coverage is 88.46%. Comparing base (eda67ac) to head (c99a6c4).
⚠️ Report is 3 commits behind head on main.

Additional details and impacted files 
@@           Coverage Diff           @@
##             main   #60031   +/-   ##
=======================================
  Coverage   88.45%   88.46%           
=======================================
  Files         703      703           
  Lines      207805   207821   +16     
  Branches    40022    40029    +7     
=======================================
+ Hits       183822   183848   +26     
+ Misses      15980    15961   -19     
- Partials     8003     8012    +9
Files with missing lines Coverage Δ
lib/internal/fixed_queue.js 100.00% <100.00%> (ø)

... and 45 files with indirect coverage changes

🚀 New features to boost your workflow:
  • ❄️ Test Analytics: Detect flaky tests, report on failures, and find test suite problems.
  • 📦 JS Bundle Analysis: Save yourself from yourself by tracking and limiting bundle sizes in JS merges.

mcollina requested changes Sep 27, 2025
View reviewed changes

mcollina left a comment

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Choose a reason Spam Abuse Off Topic Outdated Duplicate Resolved Low Quality

Great work! There are diagrams explaining this data structure at the top of the file that would need updating.

gurgunday commented Sep 27, 2025 •
edited
Loading

Copy link
Copy Markdown
Member Author

Great work! There are diagrams explaining this data structure at the top of the file that would need updating.

The new spare segment isn’t part of the list. It’s just a detached buffer we park for reuse once it's created, so it doesn’t really affect the diagrams. But nonetheless, I added a small paragraph to explain how it works.

Let me know if you'd like to see more explanation in the code!

gurgunday requested a review from mcollina September 27, 2025 20:11

This comment was marked as outdated.

Sign in to view

This comment was marked as outdated.

Sign in to view
lpinca added the request-ci Add this label to start a Jenkins CI on a PR. label Sep 28, 2025
github-actions Bot added request-ci-failed An error occurred while starting CI via request-ci label, and manual interventon is needed. and removed request-ci Add this label to start a Jenkins CI on a PR. labels Sep 28, 2025

github-actions Bot commented Sep 28, 2025

Copy link
Copy Markdown
Contributor
Failed to start CI
   ⚠  No approving reviews found
   ✘  Refusing to run CI on potentially unsafe PR
https://github.com/nodejs/node/actions/runs/18073218517

gurgunday commented Sep 29, 2025

Copy link
Copy Markdown
Member Author

@mcollina PTAL

RafaelGSS added the performance Issues and PRs related to the performance of Node.js. label Sep 29, 2025
RafaelGSS reviewed Sep 29, 2025
View reviewed changes
Comment thread benchmark/util/fixed-queue-oscillate.js Outdated
@@ -0,0 +1,28 @@
'use strict';

RafaelGSS Sep 29, 2025

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Choose a reason Spam Abuse Off Topic Outdated Duplicate Resolved Low Quality

I wouldn't include this inside benchmark/util. I believe benchmark/internal would be more appropriate. To be fair, creating a benchmark for a public API that makes use of FixedQueue behind the scenes would be better.

gurgunday Sep 29, 2025

Copy link
Copy Markdown
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Choose a reason Spam Abuse Off Topic Outdated Duplicate Resolved Low Quality

Hey @RafaelGSS, I looked at the other benchmarks and unfortunately I would need to create something super targeted for this. And even then, it might be hard to see the difference indirectly

This is a specific improvement that only gets triggered if we reach segment N + 1, and cycle between N and N + 1

For the benchmark, I was inspired by the priority queue benchmark. If you prefer, I can remove benchmark/util/fixed-queue-oscillate.js

lemire approved these changes Sep 29, 2025
View reviewed changes

lemire left a comment

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Choose a reason Spam Abuse Off Topic Outdated Duplicate Resolved Low Quality

It is a tradeoff: using more memory but also getting more performance.

gurgunday commented Sep 29, 2025

Copy link
Copy Markdown
Member Author

It is a tradeoff: using more memory but also getting more performance.

Yes, that's correct. It hinges on the idea that if we reach N+1 segments, there is a higher chance we will reach there again. But the good thing here is that we keep at max 1 extra spare segment. If 2 segments are empty (we're at N-1), segment N+1 will still be GC'd with its spare

lemire commented Sep 29, 2025

Copy link
Copy Markdown
Member

@gurgunday Yes, to be clearer, my comment was tied with my approval of the PR.

gurgunday commented Oct 3, 2025

Copy link
Copy Markdown
Member Author

I can't see an improvement in the next-tick or event.on benchmarks unfortunately

gurgunday closed this Oct 3, 2025
gurgunday deleted the fixed-queue branch October 3, 2025 22:13
gurgunday mentioned this pull request Jan 26, 2026
Merged
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
Show hidden characters
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

RafaelGSS RafaelGSS left review comments
lemire lemire approved these changes
mcollina Awaiting requested review from mcollina
+1 more reviewer
Uzlopak Uzlopak left review comments
Reviewers whose approvals may not affect merge requirements

Assignees

No one assigned

Labels

needs-ci PRs that need a full CI run. performance Issues and PRs related to the performance of Node.js. request-ci-failed An error occurred while starting CI via request-ci label, and manual interventon is needed.

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

7 participants

Back | FazBrowse Home | New Git URL