Title: Add delayed reclamation mechanism for free-threaded build (QSBR) · Issue #115103 · python/cpython · GitHub
Open Graph Title: Add delayed reclamation mechanism for free-threaded build (QSBR) · Issue #115103 · python/cpython
X Title: Add delayed reclamation mechanism for free-threaded build (QSBR) · Issue #115103 · python/cpython
Description: Feature or enhancement Many operations in the free-threaded build are protected by locks. However, in some cases, we want to allow reads to happen concurrently with updates 1. For example, we want to avoid locking during most list read a...
Open Graph Description: Feature or enhancement Many operations in the free-threaded build are protected by locks. However, in some cases, we want to allow reads to happen concurrently with updates 1. For example, we want ...
X Description: Feature or enhancement Many operations in the free-threaded build are protected by locks. However, in some cases, we want to allow reads to happen concurrently with updates 1. For example, we want ...
Opengraph URL: https://github.com/python/cpython/issues/115103
X: @github
Domain: github.com
{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"Add delayed reclamation mechanism for free-threaded build (QSBR)","articleBody":"# Feature or enhancement\n\nMany operations in the free-threaded build are protected by locks. However, in some cases, we want to allow reads to happen concurrently with updates [^1]. For example, we want to avoid locking during most list read accesses. If there is a concurrent list resize operation, when is it safe to free the list's previous array?\n\n\"Safe memory reclamation\" (SMR) schemes address this usually by delaying the \"free\" operation until all concurrent read accesses are guaranteed to have completed. Quiescent state-based reclamation (QSBR) is a safe memory reclamation scheme that will be useful in the free-threaded build. QSBR relies on marked \"quiescent states\", when a thread reports that it is definitely **not** in the middle of a non-locking read operation. The eval breaker checks serve as a good place to report a quiescent state.\n\n### Background\n\nSMR schemes are most common in systems that don't use garbage collection or reference counting. CPython uses reference counting and has a tracing garbage collector, so it may seem like an odd fit. However, some data structures are not reference counted. For example, a list object's [array](https://github.com/python/cpython/blob/b6228b521b4692b2de1c1c12f4aa5623f8319084/Include/cpython/listobject.h#L8) is not separately reference counted, but may have a shorter lifetime than the containing `PyListObject`. We could delay reclamation until the GC runs, but we want reclamation to happen quickly, and we generally want to run the GC less frequently in the free-threaded build, because it requires pausing all threads and, at least for now, scanning the entire heap.\n\n### Use cases\n\n* Dict keys (`PyDictKeysObject`) and list arrays (`ob_item`): If we resize a dict or list that may be [shared](https://github.com/python/cpython/blob/b6228b521b4692b2de1c1c12f4aa5623f8319084/Include/internal/pycore_gc.h#L74-L77) between threads, we use QSBR to delay freeing the old keys/array until it's safe to do so. Note that most dicts and lists are not accessed by multiple threads; their keys/arrays can be immediately freed on resize.\n* Mimalloc `mi_page_t`: The non-locking [dict and list accesses](https://peps.python.org/pep-0703/#mimalloc-changes-for-optimistic-list-and-dict-access) require cooperation from mimalloc. We want to ensure that even if an item is freed during access and the memory reused for a new object, the new object’s reference count field is placed at the same location in memory. In practice, this means that when an `mi_page_t` is empty, we don't immediately allow it to be re-used for allocations of a different size class. We use QSBR to determine when it's safe to use the `mi_page_t` for a different size class (or return the memory to the OS).\n\n### Implementation Overview\n\nThe implementation will be partially based on FreeBSD's [\"Global Unbounded Sequences\"](https://github.com/freebsd/freebsd-src/blob/main/sys/kern/subr_smr.c). The FreeBSD implementation provides a good starting point because it's relatively simple, self contained, and the license (2-Clause BSD) is compatible with CPython. The implementation relies on a few sequence counters:\n\n* Global (per-interpreter) write sequence: When we want to safely free a data structure, we increment the global write sequence counter and tag the data to be freed with the new value.\n* Per-thread state read sequence: When a thread reaches a quiescent state (such as when it checks the eval breaker), it copies the global write sequence to its local read counter.\n\nIt's safe to free data once all thread states' read sequences are greater than or equal to the write sequence used to tag the data.\n\nTo check that, we scan over all the thread states read sequences to compute the minimum value (excluding detached threads). For efficiency, we also cache that computed value globally (per-interpreter).\n\n### Limitations\n\nDetermining the current minimum read sequence requires scanning over all thread states. This will likely become a bottleneck if we have a large number of threads (>1,000?). We will likely eventually want to address this, possibly with some combination of a tree-based mechanism [^2] and incremental scanning.\n\nFor now, I think keeping the implementation simple important until we are able to run and benchmark multithreaded programs with the GIL disabled.\n\n[^1]: See [\"Optimistically Avoiding Locking\"](https://peps.python.org/pep-0703/#optimistically-avoiding-locking) in PEP 703. \n[^2]: https://people.kernel.org/joelfernandes/gus-vs-rcu\n\n\u003c!-- gh-linked-prs -->\n### Linked PRs\n* gh-115180\n* gh-115367\n* gh-115435\n* gh-116238\n* gh-116251\n* gh-116343\n* gh-116480\n\u003c!-- /gh-linked-prs -->\n","author":{"url":"https://github.com/colesbury","@type":"Person","name":"colesbury"},"datePublished":"2024-02-06T21:08:38Z","url":"https://github.com/python/cpython/issues/115103"}
| react-profiling | 0 |
| react-import-map | react,react-dom,react-dom/client,react-dom/profiling,react-is,react/compiler-runtime,react/jsx-dev-runtime,react/jsx-runtime,scheduler@b8488ee2c322 |
| route-pattern | /_view_fragments/issues/show/:user_id/:repository/:id/issue_layout(.:format) |
| route-controller | voltron_issues_fragments |
| route-action | issue_layout |
| fetch-nonce | v2:6dd9a325-c2ff-12b4-ba4d-3bef32cf280d |
| current-catalog-service-hash | 81bb79d38c15960b92d99bca9288a9108c7a47b18f2423d0f6438c5b7bcd2114 |
| request-id | 8F6E:21BD98:3089C76:3D92AAF:6B01FDFD |
| html-safe-nonce | d65faae7a18b723e8eb013ccdb05336a28635db1410b1e64e96f33342b918b0c |
| visitor-payload | eyJyZWZlcnJlciI6IiIsInJlcXVlc3RfaWQiOiI4RjZFOjIxQkQ5ODozMDg5Qzc2OjNEOTJBQUY6NkIwMUZERkQiLCJ2aXNpdG9yX2lkIjoiNjczMDAwMjgyODc4MzM4NjEwOSIsInJlZ2lvbl9lZGdlIjoiaWFkIiwicmVnaW9uX3JlbmRlciI6ImlhZCJ9 |
| visitor-hmac | 508abe0823f8666b57ab5ef7a41c56442f82f32c5aecd5d9daebfa288a6e6f82 |
| hovercard-subject-tag | issue:2121668643 |
| github-keyboard-shortcuts | repository,issues,copilot |
| google-site-verification | Apib7-x98H0j5cPqHWwSMm6dNU4GmODRoqxLiDzdx9I |
| octolytics-url | https://collector.github.com/github/collect |
| analytics-location | / |
| fb:app_id | 1401488693436528 |
| apple-itunes-app | app-id=1477376905, app-argument=https://github.com/_view_fragments/issues/show/python/cpython/115103/issue_layout |
| twitter:image | https://opengraph.githubassets.com/9c0493e861c6dcbe86859cb751a4166f9c0e5822e4acf0dceaec8463ff3c639e/python/cpython/issues/115103 |
| twitter:card | summary_large_image |
| og:image | https://opengraph.githubassets.com/9c0493e861c6dcbe86859cb751a4166f9c0e5822e4acf0dceaec8463ff3c639e/python/cpython/issues/115103 |
| og:image:alt | Feature or enhancement Many operations in the free-threaded build are protected by locks. However, in some cases, we want to allow reads to happen concurrently with updates 1. For example, we want ... |
| og:image:width | 1200 |
| og:image:height | 600 |
| og:site_name | GitHub |
| og:type | object |
| og:author:username | colesbury |
| hostname | github.com |
| expected-hostname | github.com |
| None | 87e774ee7c6b3bee0490394e4d3e57ec9dbc956f74b87ea685dc8996c1676456 |
| turbo-cache-control | no-preview |
| go-import | github.com/python/cpython git https://github.com/python/cpython.git |
| octolytics-dimension-user_id | 1525981 |
| octolytics-dimension-user_login | python |
| octolytics-dimension-repository_id | 81598961 |
| octolytics-dimension-repository_nwo | python/cpython |
| octolytics-dimension-repository_public | true |
| octolytics-dimension-repository_is_fork | false |
| octolytics-dimension-repository_network_root_id | 81598961 |
| octolytics-dimension-repository_network_root_nwo | python/cpython |
| turbo-body-classes | logged-out env-production page-responsive |
| disable-turbo | false |
| browser-stats-url | https://api.github.com/_private/browser/stats |
| browser-errors-url | https://api.github.com/_private/browser/errors |
| release | 423dbb54c5e7bfecc838eb387c1435eb3d0e760d |
| ui-target | full |
| theme-color | #1e2327 |
| color-scheme | light dark |
| react-app-name | issues |
Links:
Viewport: width=device-width