{"action":"created","issue":{"url":"https://api.github.com/repos/bitcoin/bitcoin/issues/8895","repository_url":"https://api.github.com/repos/bitcoin/bitcoin","labels_url":"https://api.github.com/repos/bitcoin/bitcoin/issues/8895/labels{/name}","comments_url":"https://api.github.com/repos/bitcoin/bitcoin/issues/8895/comments","events_url":"https://api.github.com/repos/bitcoin/bitcoin/issues/8895/events","html_url":"https://github.com/bitcoin/bitcoin/pull/8895","id":181275275,"number":8895,"title":"Better SigCache Implementation","user":{"login":"JeremyRubin","id":886523,"avatar_url":"https://avatars.githubusercontent.com/u/886523?v=3","gravatar_id":"","url":"https://api.github.com/users/JeremyRubin","html_url":"https://github.com/JeremyRubin","followers_url":"https://api.github.com/users/JeremyRubin/followers","following_url":"https://api.github.com/users/JeremyRubin/following{/other_user}","gists_url":"https://api.github.com/users/JeremyRubin/gists{/gist_id}","starred_url":"https://api.github.com/users/JeremyRubin/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/JeremyRubin/subscriptions","organizations_url":"https://api.github.com/users/JeremyRubin/orgs","repos_url":"https://api.github.com/users/JeremyRubin/repos","events_url":"https://api.github.com/users/JeremyRubin/events{/privacy}","received_events_url":"https://api.github.com/users/JeremyRubin/received_events","type":"User","site_admin":false},"labels":[{"id":326918230,"url":"https://api.github.com/repos/bitcoin/bitcoin/labels/Resource%20usage","name":"Resource usage","color":"981023","default":false},{"id":118379652,"url":"https://api.github.com/repos/bitcoin/bitcoin/labels/Validation","name":"Validation","color":"6060aa","default":false}],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":{"url":"https://api.github.com/repos/bitcoin/bitcoin/milestones/21","html_url":"https://github.com/bitcoin/bitcoin/milestones/0.14.0","labels_url":"https://api.github.com/repos/bitcoin/bitcoin/milestones/21/labels","id":1823680,"number":21,"title":"0.14.0","description":"","creator":{"login":"MarcoFalke","id":6399679,"avatar_url":"https://avatars.githubusercontent.com/u/6399679?v=3","gravatar_id":"","url":"https://api.github.com/users/MarcoFalke","html_url":"https://github.com/MarcoFalke","followers_url":"https://api.github.com/users/MarcoFalke/followers","following_url":"https://api.github.com/users/MarcoFalke/following{/other_user}","gists_url":"https://api.github.com/users/MarcoFalke/gists{/gist_id}","starred_url":"https://api.github.com/users/MarcoFalke/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/MarcoFalke/subscriptions","organizations_url":"https://api.github.com/users/MarcoFalke/orgs","repos_url":"https://api.github.com/users/MarcoFalke/repos","events_url":"https://api.github.com/users/MarcoFalke/events{/privacy}","received_events_url":"https://api.github.com/users/MarcoFalke/received_events","type":"User","site_admin":false},"open_issues":18,"closed_issues":24,"state":"open","created_at":"2016-06-13T14:18:51Z","updated_at":"2016-11-25T07:39:26Z","due_on":null,"closed_at":null},"comments":16,"created_at":"2016-10-05T21:51:18Z","updated_at":"2016-11-30T23:41:55Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/bitcoin/bitcoin/pulls/8895","html_url":"https://github.com/bitcoin/bitcoin/pull/8895","diff_url":"https://github.com/bitcoin/bitcoin/pull/8895.diff","patch_url":"https://github.com/bitcoin/bitcoin/pull/8895.patch"},"body":"edited: This PR has been squashed with a few revisions from the initial PR. The unsquashed version is still available here https://github.com/bitcoin/bitcoin/compare/master...JeremyRubin:cuckoocache-pull-request-not-squashed. The PR message has also been updated to reflect the current squashed version more closely.\n# Summary\n\nThis PR replaces the boost::unordered_set in sigcache with CuckooCache::cache.\n# Benefits\n- Better memory utilization (no pointers/linked lists/stored hashes)\n- Lock Free concurrent reads and erases\n- Lazy Deletion of entries (potentially beneficial in case of re-orgs)\n- Low cache thrashing -- a standard lookup and erase should only require ~9 cache lines (Hash 0..Hash 7, and erase flag)\n- Allocation free design\n- Insert guaranteed to terminate\n- Generations smartly delete older entries before newer ones\n# Design\n\nThe CuckooCache uses a design similar to a [Cuckoo Hash Table](https://en.wikipedia.org/wiki/Cuckoo_hashing). Each key inserted has a hash function 0 through hash function 7 (h0..h7).\n- Lookup(k) is a matter of examining location h0(k)..h7(k).\n- Insert(k) first sees if h0(k)..h7(k) is empty, and insets to one if so. If not, insert swaps k with the key at one more than the last hash location (so it goes in a cycle through h0..h7) and attempts to insert the swapped out key at it's other location, repeating (up to a limit) if necessary. At that limit, the last entry is dropped. Insert also checks a heuristic (described below) to age a generation before trying to insert.\n- Delete(k) first does a Lookup(k), then marks the corresponding bit in an std::atomic<uint8_t> as set as a relaxed atomic operation.\n\nMore information about the synchronization specification is in the code documentation.\n## Generation Heuristic\n\nA bit vector is used to track if the element belongs to the current or prior generation. Once the number of the current generation's non-deleted elements exceeds ~45%, the generation is retired. The previously retired generation is marked deleted. Because the cache deletes lazily, these entries are still present but are more likely to be overwritten than elements in the currently retired generation. Generations are scanned to see if they should be retired using a heuristic of how many inserts would need to occur since the last scan to exceed the generation size.\n\nThere is a slight (1-bit per entry) memory overhead to this approach. This does not negatively impact this cache because the trade off is worth it for intelligently deleting older entries. Only one bit is used for simplicity, as we get three represented states (deleted, old, current). Using more generations (lets say, 1 more bit) would allow for more granular freeing of only the oldest quarter and not half per scan. This has advantages, but also an additional memory cost and two generations was sufficient for this use case.\n# Simulation\n\nThese simulation results are slightly outdated, @morcos will chime in below with some updated figures. It should be better/the same as below.\n~~This can overall be seen as a 40% improvement on validation times over master on a 16 core machine simulated over a month. The simulation methodology sends relayed transactions and blocks to the node in the order they were received historically. On 4 and 1 core simulations, the improvement is not significant (but no worse). Our tests didn't really hit hard saturation on the cache, which suggests that the megabytes allocated to the cache could be reduced.~~\n# Testing\n\nThe PR includes a test suite which checks a few key properties:\n1. Check that values not inserted are never readable\n2. Check that a reasonable hit rate is achieved\n3. Check that erased elements are inserted on reasonably well rather than replacing fresh contents\n4. Test that (3) holds when erases are in parallel.\n# Future Work\n\nThere are future optimizations which may be able to bring some of the advantages seen with 16 cores to 4 and 1 cores, but this PR is focused on a minimal complexity patch with a demonstrable improvement over main as a base for future work in this direction.\n\nThere are also a few cleanup related items (such as cache initialization) which are not done in this patch to make it a minimal code change. These can be fixed in a later PR if this is accepted.\n# Acknowledgements\n\nThanks to @morcos, @sdaftuar, and @TheBlueMatt for their assistance and review on this patch.\n"},"comment":{"url":"https://api.github.com/repos/bitcoin/bitcoin/issues/comments/264032672","html_url":"https://github.com/bitcoin/bitcoin/pull/8895#issuecomment-264032672","issue_url":"https://api.github.com/repos/bitcoin/bitcoin/issues/8895","id":264032672,"user":{"login":"JeremyRubin","id":886523,"avatar_url":"https://avatars.githubusercontent.com/u/886523?v=3","gravatar_id":"","url":"https://api.github.com/users/JeremyRubin","html_url":"https://github.com/JeremyRubin","followers_url":"https://api.github.com/users/JeremyRubin/followers","following_url":"https://api.github.com/users/JeremyRubin/following{/other_user}","gists_url":"https://api.github.com/users/JeremyRubin/gists{/gist_id}","starred_url":"https://api.github.com/users/JeremyRubin/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/JeremyRubin/subscriptions","organizations_url":"https://api.github.com/users/JeremyRubin/orgs","repos_url":"https://api.github.com/users/JeremyRubin/repos","events_url":"https://api.github.com/users/JeremyRubin/events{/privacy}","received_events_url":"https://api.github.com/users/JeremyRubin/received_events","type":"User","site_admin":false},"created_at":"2016-11-30T23:41:55Z","updated_at":"2016-11-30T23:41:55Z","body":"Should be all addressed."}}
{"actor":{"display_login":"JeremyRubin"}}