]> granicus.if.org Git - python/commit
projects / python / commit
? search:
summary | shortlog | log | commit | commitdiff | tree
(parent: 549e55a) | patch
bpo-37029: keep usable_arenas in sorted order without searching (#13612)
authorTim Peters <tim.peters@gmail.com>
Sat, 1 Jun 2019 02:16:04 +0000 (21:16 -0500)
committerGitHub <noreply@github.com>
Sat, 1 Jun 2019 02:16:04 +0000 (21:16 -0500)
commit1c263e39c4ed28225a7dc8ca1f24953225ac48ca
tree5ed4207eb76f5bfcbf77a0827435aa9cc0681edatree | snapshot
parent549e55a3086d04c13da9b6f33214f6399681292acommit | diff
bpo-37029:  keep usable_arenas in sorted order without searching (#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.
Misc/NEWS.d/next/Core and Builtins/2019-05-28-17-02-46.bpo-37029.MxpgfJ.rst [new file with mode: 0644] blob
Objects/obmalloc.c diff | blob | history
Unnamed repository; edit this file 'description' to name the repository.