Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Reduce minetest.after time complexity and provide ordering guarantee #13477

Merged
merged 1 commit into from Jan 16, 2024

Conversation

appgurueu
Copy link
Contributor

Adopted (essentially just trivially rebased) #12043.

The following discussion from @savilli was still unresolved. savilli pointed out that jobs are not completely removed from the data structure, but rather updated to be "dummy" jobs, thus deferring the cost of removing them. The downsides of not removing dummy jobs are the following:

  • They make the data structure (slightly) slower for new jobs. This is largely negligible since large n in O(log n) is not an issue.
  • They waste space until they expire. This might be an issue if a game heavily relies on jobs being dropped immediately as they are cancelled. Adding a billion jobs expiring in a minute and then cancelling all of them will probably OOM.
  • They waste (very little) time when they expire.

For regular use of jobs and cancellation, none of this will be an issue. On the other hand, implementing immediate removal comes with the following issues:

  • Maintaining the data structure gets slightly worse constant factors both time- and space-wise. The asymptotic time and space complexity however remain unaffected.
  • Much more importantly, the implementation remains rather simple. Immediate removal of jobs would require upgrading the heap to a priority queue and the singly linked lists to doubly linked lists.

builtin/common/after.lua Outdated Show resolved Hide resolved
builtin/common/after.lua Outdated Show resolved Hide resolved
builtin/common/after.lua Show resolved Hide resolved
doc/lua_api.md Outdated Show resolved Hide resolved
@Zughy Zughy added the Action / change needed Code still needs changes (PR) / more information requested (Issues) label Oct 2, 2023
@Zughy Zughy removed the Action / change needed Code still needs changes (PR) / more information requested (Issues) label Nov 8, 2023
@sfan5 sfan5 added this to the 5.9.0 milestone Nov 12, 2023
builtin/game/features.lua Outdated Show resolved Hide resolved
@sfan5
Copy link
Member

sfan5 commented Jan 11, 2024

Well if it works feel free to merge it.

@rubenwardy rubenwardy added the Concept approved Approved by a core dev: PRs welcomed! label Jan 14, 2024
---------

Co-authored-by: Lars Mueller <appgurulars@gmx.de>
@appgurueu
Copy link
Contributor Author

Had to manually squash and force-push to make sure TurkeyMcMac is properly preserved as the first author in the commit logs.

@appgurueu appgurueu merged commit e7dd973 into minetest:master Jan 16, 2024
2 checks passed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet

6 participants