bpo-37029: keep usable_arenas in sorted order without searching #13612
Conversation
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
sorted by number of free pools.
methane
reviewed
May 29, 2019
methane
approved these changes
May 31, 2019
pitrou
reviewed
May 31, 2019
|
|
||
| /* The head of the doubly-linked, NULL-terminated at each end, list of | ||
| * arena_objects associated with arenas that have pools available. | ||
| */ |
Member
There was a problem hiding this comment.
Add comment documenting that they are sorted in number of free pools?
Member
Author
There was a problem hiding this comment.
I'd rather not, unless you feel strongly about it. This has been documented all along, but up where the main explanation of arenas lives (look at the comment block about usable_arenas at line 1150).
There are a bunch of moving parts here, and the style of the file is to give long-ish English explanations in uninterrupted comment blocks, with only the briefest of memory-jogging comments on declaration lines.
|
@tim-one: Please replace |
DinoV
pushed a commit
to DinoV/cpython
that referenced
this pull request
Jan 14, 2020
…on#13612) This adds a vector of "search fingers" so that usable_arenas can be kept in sorted order (by number of free pools) via constant-time operations instead of linear search. This should reduce worst-case time for reclaiming a great many objects from O(A**2) to O(A), where A is the number of arenas. See bpo-37029.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
5 participants
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
This adds a vector of "search fingers" so that usable_arenas can be kept in sorted order (by number of free pools) via constant-time operations instead of linear search.
This should reduce worst-case time for reclaiming a great many objects from O(A**2) to O(A), where A is the number of arenas.
https://bugs.python.org/issue37029