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

lib: fix - invalid timer priority queue order by mareksrom · Pull Request #24318 · nodejs/node · GitHub

/ node Public

lib: fix - invalid timer priority queue order - #24318

Closed
mareksrom wants to merge 2 commits into
nodejs:masterfrom
mareksrom:master
ConversationCommits (2)ChecksFiles changed
Closed

lib: fix - invalid timer priority queue order#24318
mareksrom wants to merge 2 commits into
nodejs:masterfrom
mareksrom:master

Conversation

mareksrom commented Nov 12, 2018

Copy link
Copy Markdown

  • in lib/timers.js PriorityQueue.percolateDown cannot be used for rescheduling list,
    because it does not work in all cases

    • updated item does not have to be root of the heap when new timers are created
      in runNextTicks and then percolateDown does not solve all binary heap
      inconsistencies
    • old behavior could cause infinite loop timers in some cases

  • added PriorityQueue.updateAt and PriorityQueue.update methods

    • simple implementation by remove & insert, could be improved...
    • rescheduling list uses updateAt method
Checklist
  • make -j4 test (UNIX), or vcbuild test (Windows) passes
  • tests and/or benchmarks are included
  • documentation is changed or added
  • commit message follows commit guidelines

lib: fix - invalid timer priority queue order
fa558e6 
- in lib/timers.js PriorityQueue.percolateDown cannot be used for rescheduling list,
  because it does not work in all cases
  - updated item does not have to be root of the heap when new timers are created
    in runNextTicks and then percolateDown does not solve all binary heap
    inconsistencies
  - old behavior could cause infinite loop timers in some cases

- added PriorityQueue.updateAt and PriorityQueue.update methods
  - simple implementation by remove & insert, could be improved...
  - rescheduling list uses updateAt method
nodejs-github-bot added the timers Issues and PRs related to the timers subsystem / setImmediate, setInterval, setTimeout. label Nov 12, 2018
mareksrom mentioned this pull request Nov 12, 2018
Closed
cjihrig mentioned this pull request Nov 12, 2018
Closed

mareksrom commented Nov 12, 2018

Copy link
Copy Markdown
Author

Thanks for info, I’ll check the priority queue for your test case...

mareksrom commented Nov 12, 2018

Copy link
Copy Markdown
Author

The fix is still not complete, PriorityQueue.percolateDown is not suitable method for restoring binary heap after removal of item. I have to implement updateAt method without removing and inserting the item, that wil be able to fix binary heap up and also down... It will be used in updateAt and also removeAt methods...

apapirovski commented Nov 12, 2018 •
edited
Loading

Copy link
Copy Markdown
Contributor

@mareksrom sorry, I didn't see your PR earlier but I opened the correct version at #24322 which rebalances both up & down the heap. Would appreciate your review if you've got a moment.

Fishrock123 commented Nov 15, 2018

Copy link
Copy Markdown
Contributor

Superseded by the now merged #24322

@mareksrom Thanks for making this anyway!

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

apapirovski Awaiting requested review from apapirovski
Fishrock123 Awaiting requested review from Fishrock123

Assignees

No one assigned

Labels

timers Issues and PRs related to the timers subsystem / setImmediate, setInterval, setTimeout.

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

5 participants

Back | FazBrowse Home | New Git URL