bpo-37029: keep usable_arenas in sorted order without searching by tim-one · Pull Request #13612 · python/cpython
sorted by number of free pools.
tim-one
deleted the
remove-arena-search
branch
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.
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