{"action":"created","issue":{"url":"https://api.github.com/repos/chapel-lang/chapel/issues/8182","repository_url":"https://api.github.com/repos/chapel-lang/chapel","labels_url":"https://api.github.com/repos/chapel-lang/chapel/issues/8182/labels{/name}","comments_url":"https://api.github.com/repos/chapel-lang/chapel/issues/8182/comments","events_url":"https://api.github.com/repos/chapel-lang/chapel/issues/8182/events","html_url":"https://github.com/chapel-lang/chapel/pull/8182","id":287957194,"number":8182,"title":"Introducing Quiescent State-Based Reclamation to Chapel","user":{"login":"LouisJenkinsCS","id":4269990,"avatar_url":"https://avatars2.githubusercontent.com/u/4269990?v=4","gravatar_id":"","url":"https://api.github.com/users/LouisJenkinsCS","html_url":"https://github.com/LouisJenkinsCS","followers_url":"https://api.github.com/users/LouisJenkinsCS/followers","following_url":"https://api.github.com/users/LouisJenkinsCS/following{/other_user}","gists_url":"https://api.github.com/users/LouisJenkinsCS/gists{/gist_id}","starred_url":"https://api.github.com/users/LouisJenkinsCS/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/LouisJenkinsCS/subscriptions","organizations_url":"https://api.github.com/users/LouisJenkinsCS/orgs","repos_url":"https://api.github.com/users/LouisJenkinsCS/repos","events_url":"https://api.github.com/users/LouisJenkinsCS/events{/privacy}","received_events_url":"https://api.github.com/users/LouisJenkinsCS/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":{"login":"mppf","id":3653132,"avatar_url":"https://avatars3.githubusercontent.com/u/3653132?v=4","gravatar_id":"","url":"https://api.github.com/users/mppf","html_url":"https://github.com/mppf","followers_url":"https://api.github.com/users/mppf/followers","following_url":"https://api.github.com/users/mppf/following{/other_user}","gists_url":"https://api.github.com/users/mppf/gists{/gist_id}","starred_url":"https://api.github.com/users/mppf/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mppf/subscriptions","organizations_url":"https://api.github.com/users/mppf/orgs","repos_url":"https://api.github.com/users/mppf/repos","events_url":"https://api.github.com/users/mppf/events{/privacy}","received_events_url":"https://api.github.com/users/mppf/received_events","type":"User","site_admin":false},"assignees":[{"login":"mppf","id":3653132,"avatar_url":"https://avatars3.githubusercontent.com/u/3653132?v=4","gravatar_id":"","url":"https://api.github.com/users/mppf","html_url":"https://github.com/mppf","followers_url":"https://api.github.com/users/mppf/followers","following_url":"https://api.github.com/users/mppf/following{/other_user}","gists_url":"https://api.github.com/users/mppf/gists{/gist_id}","starred_url":"https://api.github.com/users/mppf/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mppf/subscriptions","organizations_url":"https://api.github.com/users/mppf/orgs","repos_url":"https://api.github.com/users/mppf/repos","events_url":"https://api.github.com/users/mppf/events{/privacy}","received_events_url":"https://api.github.com/users/mppf/received_events","type":"User","site_admin":false}],"milestone":null,"comments":251,"created_at":"2018-01-11T23:14:44Z","updated_at":"2018-03-02T01:26:03Z","closed_at":null,"author_association":"MEMBER","pull_request":{"url":"https://api.github.com/repos/chapel-lang/chapel/pulls/8182","html_url":"https://github.com/chapel-lang/chapel/pull/8182","diff_url":"https://github.com/chapel-lang/chapel/pull/8182.diff","patch_url":"https://github.com/chapel-lang/chapel/pull/8182.patch"},"body":"I introduce Quiescent State-Based Reclamation, a memory reclamation algorithm that can be from the confines of the runtime and potentially from Chapel user code (with some GOTCHAS). The memory reclamation algorithm comes with very little performance regression and can ensure the eventual cleanup of memory so long as checkpoints are periodically called from all threads (although their placement is up to debate). \r\n\r\nQSBR can come in handy for any performance-critical data structure, and currently is used in Chapel's privatization table. Future uses can be for the thread-safety of Chapel's callback system and perhaps in more dynamic task local storage. In the future, a specific QSBR table is planned for users that will not be able to interfere with the runtime.\r\n\r\n**Potential Uses of QSBR:**\r\n1. Non-Blocking Data Structures: It is safe to defer the deletion of anything logically removed from the data structure in question. For example, a lock-free queue that removes a node from the head can safely defer deletion as it will be the only thread to do so (since the CAS operation will return true for only one successful operation)\r\n2. Multiword Compare-And-Swap: This also applies to anything using descriptors for helping mechanisms, but a K-Word Compare-And-Swap where we make use of an object that holds enough state to represent some in-progress operation to claim ownership of the location. The descriptor can be accessed by concurrent threads and so it is safe to defer for deletion after the owning thread/task completes its operation.\r\n3. Software Transactional Memory: While things like reading and writing are trivial to implement, a huge problem that arises is the deletion of data during a transaction and even after committing it. Deleting the object immediately can result in a segmentation fault for tasks that have not yet aborted their transaction, so deferring deletion would be a solution so long as no checkpoint is invoked within a transaction.\r\n\r\nThere are many other potential uses, the sky is the limit.\r\n\r\n@mppf's list of TODOs before merging:\r\n\r\nFor my part - I think the criterion for me are:\r\n - [ ] I need to have another look at the patch in detail\r\n - [x] (I can) run full local testing\r\n - [x] achieve some understanding of development path if we make RCU available to other runtime code / Chapel code\r\n - [ ] (Elliot can) full multi-locale performance testing\r\n - [x] (anybody can) a stupid amount of trials on the privatizations tests. passed 10000 trials of test/distributions/privatization/runtime/ in the standard configuration, and 1000 with quickstart.\r\n"},"comment":{"url":"https://api.github.com/repos/chapel-lang/chapel/issues/comments/369789287","html_url":"https://github.com/chapel-lang/chapel/pull/8182#issuecomment-369789287","issue_url":"https://api.github.com/repos/chapel-lang/chapel/issues/8182","id":369789287,"user":{"login":"LouisJenkinsCS","id":4269990,"avatar_url":"https://avatars2.githubusercontent.com/u/4269990?v=4","gravatar_id":"","url":"https://api.github.com/users/LouisJenkinsCS","html_url":"https://github.com/LouisJenkinsCS","followers_url":"https://api.github.com/users/LouisJenkinsCS/followers","following_url":"https://api.github.com/users/LouisJenkinsCS/following{/other_user}","gists_url":"https://api.github.com/users/LouisJenkinsCS/gists{/gist_id}","starred_url":"https://api.github.com/users/LouisJenkinsCS/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/LouisJenkinsCS/subscriptions","organizations_url":"https://api.github.com/users/LouisJenkinsCS/orgs","repos_url":"https://api.github.com/users/LouisJenkinsCS/repos","events_url":"https://api.github.com/users/LouisJenkinsCS/events{/privacy}","received_events_url":"https://api.github.com/users/LouisJenkinsCS/received_events","type":"User","site_admin":false},"created_at":"2018-03-02T01:26:03Z","updated_at":"2018-03-02T01:26:03Z","author_association":"MEMBER","body":"@ronawho \r\n\r\nYou are a genius!!! It works! Down from 800M to 25M and only like a second or two of regression!"}}
{"actor":{"display_login":"LouisJenkinsCS"}}