{"action":"opened","number":12,"pull_request":{"url":"https://api.github.com/repos/gramoli/synchrobench/pulls/12","id":90336391,"html_url":"https://github.com/gramoli/synchrobench/pull/12","diff_url":"https://github.com/gramoli/synchrobench/pull/12.diff","patch_url":"https://github.com/gramoli/synchrobench/pull/12.patch","issue_url":"https://api.github.com/repos/gramoli/synchrobench/issues/12","number":12,"state":"open","locked":false,"title":"Thread-safety of random number generators.","user":{"login":"harrisonrodgers","id":479570,"avatar_url":"https://avatars.githubusercontent.com/u/479570?v=3","gravatar_id":"","url":"https://api.github.com/users/harrisonrodgers","html_url":"https://github.com/harrisonrodgers","followers_url":"https://api.github.com/users/harrisonrodgers/followers","following_url":"https://api.github.com/users/harrisonrodgers/following{/other_user}","gists_url":"https://api.github.com/users/harrisonrodgers/gists{/gist_id}","starred_url":"https://api.github.com/users/harrisonrodgers/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/harrisonrodgers/subscriptions","organizations_url":"https://api.github.com/users/harrisonrodgers/orgs","repos_url":"https://api.github.com/users/harrisonrodgers/repos","events_url":"https://api.github.com/users/harrisonrodgers/events{/privacy}","received_events_url":"https://api.github.com/users/harrisonrodgers/received_events","type":"User","site_admin":false},"body":"**Issue:**\r\nA non-thread-safe and non-reentrant random number generator was being utilized by some skip lists to select the height of new nodes being inserted. When concurrent threads are using rand() [futex](https://en.wikipedia.org/wiki/Futex) locks are introduced which _significantly_ lowers performance.\r\n\r\n**Excerpt from `man 3 rand`**\r\n\r\n> The function rand() is not reentrant or thread-safe, since it uses hidden state that is modified on each call.  This might just be the  seed value  to  be  used by the next call, or it might be something more elaborate.  In order to get reproducible behavior in a threaded application, this state must be made explicit; this can be done using the reentrant function rand_r().\r\n\r\n**Solution:**\r\nConcurrent threads should use a thread-safe and reentrant random number generator.\r\n\r\nThis pull request implements xorshift32 random number generator in the sequential and skiplist-lock (Herlihy's optimistic) skip lists. Additionally adds thread-safety information in all the comments for rand_range() and rand_range_re().\r\n\r\nXorshift generators are extremely fast non-cryptographically-secure random number generators on modern architectures (except microprocessors).\r\n\r\n**Performance Increase:**\r\nUtilizing xorshift ([graphs](http://i.imgur.com/gMAU0F7.png) which include rand_r benchmarks) shows:\r\n\r\n- AMD & Intel\r\n  - Sequential skip list: 0% change in every workload\r\n- AMD\r\n  - Herlihy's skip list: 0% change under read-only workload\r\n  - Herlihy's skip list: up to **166% throughput increase** under _10% update_ workload\r\n  - Herlihy's skip list: up to **458% throughput increase** under _100% update_ workload\r\n- Intel\r\n  - Herlihy's skip list: 0% change under read-only workload\r\n  - Herlihy's skip list: up to **43% throughput increase** under _10% update_ workload\r\n  - Herlihy's skip list: up to **341% throughput increase** under _100% update_ workload\r\n\r\n**Xorshift Paper:**\r\nMarsaglia, George, (July 2003), \"Xorshift RNGs\", Journal of Statistical Software 8 (14)\r\n\r\n**Raw RNG Performance on Intel:**\r\nTime for _16_ threads to each produce 2^26 random numbers:\r\n\r\n  - rand() = real\t:12m33.438s user:10m22.336s _sys:184m43.816s_\r\n  - rand_r() = real:2m12.845s user:33m39.724s sys:0m0.000s\r\n  - xorshift32() = real:1m12.383s user:18m35.564s sys:0m0.004s\r\n\r\nTime for a _single_ thread to produce 2^32 random numbers:\r\n\r\n  - rand() = real:3m42.892s user:3m42.892s sys:0m0.000s\r\n  - rand_r() = real:3m25.972s user:3m25.972s sys:0m0.000s\r\n  - xorshift32() = real:1m40.228s user:1m40.228s sys:0m0.000s\r\n\r\n**Systems:**\r\n- 4x AMD Opteron(tm) Processor 6378 @ 2.40GHz with 256GB RAM gcc 5.3.0 \r\n- 2x Intel(R) Xeon(R) CPU E5-2450 @ 2.10GHz with 128GB RAM gcc 4.8.1 \r\n\r\n**Example `strace -f` output of concurrent threads using rand():**\r\n```\r\n[pid 40570] futex(0x7fc4d88da750, FUTEX_WAIT_PRIVATE, 2, NULL <unfinished ...>\r\n[pid 40569] futex(0x7fc4d88da750, FUTEX_WAKE_PRIVATE, 1 <unfinished ...>\r\n[pid 40570] <... futex resumed> )       = -1 EAGAIN (Resource temporarily unavailable)\r\n[pid 40569] <... futex resumed> )       = 0\r\n[pid 40570] futex(0x7fc4d88da750, FUTEX_WAKE_PRIVATE, 1 <unfinished ...>\r\n[pid 40568] <... futex resumed> )       = -1 EAGAIN (Resource temporarily unavailable)\r\n[pid 40570] <... futex resumed> )       = 0\r\n[pid 40569] futex(0x7fc4d88da750, FUTEX_WAIT_PRIVATE, 2, NULL <unfinished ...>\r\n[pid 40568] futex(0x7fc4d88da750, FUTEX_WAKE_PRIVATE, 1 <unfinished ...>\r\n[pid 40569] <... futex resumed> )       = -1 EAGAIN (Resource temporarily unavailable)\r\n[pid 40568] <... futex resumed> )       = 0\r\n[pid 40570] futex(0x7fc4d88da750, FUTEX_WAIT_PRIVATE, 2, NULL <unfinished ...>\r\n[pid 40569] futex(0x7fc4d88da750, FUTEX_WAKE_PRIVATE, 1 <unfinished ...>\r\n[pid 40570] <... futex resumed> )       = -1 EAGAIN (Resource temporarily unavailable)\r\n[pid 40569] <... futex resumed> )       = 0\r\n[pid 40570] futex(0x7fc4d88da750, FUTEX_WAIT_PRIVATE, 2, NULL <unfinished ...>\r\n[pid 40568] futex(0x7fc4d88da750, FUTEX_WAKE_PRIVATE, 1 <unfinished ...>\r\n[pid 40570] <... futex resumed> )       = -1 EAGAIN (Resource temporarily unavailable)\r\n[pid 40568] <... futex resumed> )       = 0\r\n[pid 40570] futex(0x7fc4d88da750, FUTEX_WAKE_PRIVATE, 1 <unfinished ...>\r\n[pid 40569] futex(0x7fc4d88da750, FUTEX_WAIT_PRIVATE, 2, NULL <unfinished ...>\r\n[pid 40570] <... futex resumed> )       = 0\r\n[pid 40569] <... futex resumed> )       = -1 EAGAIN (Resource temporarily unavailable)\r\n[pid 40570] futex(0x7fc4d88da750, FUTEX_WAIT_PRIVATE, 2, NULL <unfinished ...>\r\n[pid 40569] futex(0x7fc4d88da750, FUTEX_WAKE_PRIVATE, 1 <unfinished ...>\r\n[pid 40570] <... futex resumed> )       = -1 EAGAIN (Resource temporarily unavailable)\r\n[pid 40569] <... futex resumed> )       = 0\r\n```","created_at":"2016-10-21T07:42:45Z","updated_at":"2016-10-21T07:42:45Z","closed_at":null,"merged_at":null,"merge_commit_sha":null,"assignee":null,"assignees":[],"milestone":null,"commits_url":"https://api.github.com/repos/gramoli/synchrobench/pulls/12/commits","review_comments_url":"https://api.github.com/repos/gramoli/synchrobench/pulls/12/comments","review_comment_url":"https://api.github.com/repos/gramoli/synchrobench/pulls/comments{/number}","comments_url":"https://api.github.com/repos/gramoli/synchrobench/issues/12/comments","statuses_url":"https://api.github.com/repos/gramoli/synchrobench/statuses/486897a9bf68fa7330aee4ff7930c7c29fbf1e85","head":{"label":"harrisonrodgers:random","ref":"random","sha":"486897a9bf68fa7330aee4ff7930c7c29fbf1e85","user":{"login":"harrisonrodgers","id":479570,"avatar_url":"https://avatars.githubusercontent.com/u/479570?v=3","gravatar_id":"","url":"https://api.github.com/users/harrisonrodgers","html_url":"https://github.com/harrisonrodgers","followers_url":"https://api.github.com/users/harrisonrodgers/followers","following_url":"https://api.github.com/users/harrisonrodgers/following{/other_user}","gists_url":"https://api.github.com/users/harrisonrodgers/gists{/gist_id}","starred_url":"https://api.github.com/users/harrisonrodgers/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/harrisonrodgers/subscriptions","organizations_url":"https://api.github.com/users/harrisonrodgers/orgs","repos_url":"https://api.github.com/users/harrisonrodgers/repos","events_url":"https://api.github.com/users/harrisonrodgers/events{/privacy}","received_events_url":"https://api.github.com/users/harrisonrodgers/received_events","type":"User","site_admin":false},"repo":{"id":54942762,"name":"synchrobench","full_name":"harrisonrodgers/synchrobench","owner":{"login":"harrisonrodgers","id":479570,"avatar_url":"https://avatars.githubusercontent.com/u/479570?v=3","gravatar_id":"","url":"https://api.github.com/users/harrisonrodgers","html_url":"https://github.com/harrisonrodgers","followers_url":"https://api.github.com/users/harrisonrodgers/followers","following_url":"https://api.github.com/users/harrisonrodgers/following{/other_user}","gists_url":"https://api.github.com/users/harrisonrodgers/gists{/gist_id}","starred_url":"https://api.github.com/users/harrisonrodgers/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/harrisonrodgers/subscriptions","organizations_url":"https://api.github.com/users/harrisonrodgers/orgs","repos_url":"https://api.github.com/users/harrisonrodgers/repos","events_url":"https://api.github.com/users/harrisonrodgers/events{/privacy}","received_events_url":"https://api.github.com/users/harrisonrodgers/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/harrisonrodgers/synchrobench","description":"A benchmark to compare synchronization techniques for multicore programming ","fork":true,"url":"https://api.github.com/repos/harrisonrodgers/synchrobench","forks_url":"https://api.github.com/repos/harrisonrodgers/synchrobench/forks","keys_url":"https://api.github.com/repos/harrisonrodgers/synchrobench/keys{/key_id}","collaborators_url":"https://api.github.com/repos/harrisonrodgers/synchrobench/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/harrisonrodgers/synchrobench/teams","hooks_url":"https://api.github.com/repos/harrisonrodgers/synchrobench/hooks","issue_events_url":"https://api.github.com/repos/harrisonrodgers/synchrobench/issues/events{/number}","events_url":"https://api.github.com/repos/harrisonrodgers/synchrobench/events","assignees_url":"https://api.github.com/repos/harrisonrodgers/synchrobench/assignees{/user}","branches_url":"https://api.github.com/repos/harrisonrodgers/synchrobench/branches{/branch}","tags_url":"https://api.github.com/repos/harrisonrodgers/synchrobench/tags","blobs_url":"https://api.github.com/repos/harrisonrodgers/synchrobench/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/harrisonrodgers/synchrobench/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/harrisonrodgers/synchrobench/git/refs{/sha}","trees_url":"https://api.github.com/repos/harrisonrodgers/synchrobench/git/trees{/sha}","statuses_url":"https://api.github.com/repos/harrisonrodgers/synchrobench/statuses/{sha}","languages_url":"https://api.github.com/repos/harrisonrodgers/synchrobench/languages","stargazers_url":"https://api.github.com/repos/harrisonrodgers/synchrobench/stargazers","contributors_url":"https://api.github.com/repos/harrisonrodgers/synchrobench/contributors","subscribers_url":"https://api.github.com/repos/harrisonrodgers/synchrobench/subscribers","subscription_url":"https://api.github.com/repos/harrisonrodgers/synchrobench/subscription","commits_url":"https://api.github.com/repos/harrisonrodgers/synchrobench/commits{/sha}","git_commits_url":"https://api.github.com/repos/harrisonrodgers/synchrobench/git/commits{/sha}","comments_url":"https://api.github.com/repos/harrisonrodgers/synchrobench/comments{/number}","issue_comment_url":"https://api.github.com/repos/harrisonrodgers/synchrobench/issues/comments{/number}","contents_url":"https://api.github.com/repos/harrisonrodgers/synchrobench/contents/{+path}","compare_url":"https://api.github.com/repos/harrisonrodgers/synchrobench/compare/{base}...{head}","merges_url":"https://api.github.com/repos/harrisonrodgers/synchrobench/merges","archive_url":"https://api.github.com/repos/harrisonrodgers/synchrobench/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/harrisonrodgers/synchrobench/downloads","issues_url":"https://api.github.com/repos/harrisonrodgers/synchrobench/issues{/number}","pulls_url":"https://api.github.com/repos/harrisonrodgers/synchrobench/pulls{/number}","milestones_url":"https://api.github.com/repos/harrisonrodgers/synchrobench/milestones{/number}","notifications_url":"https://api.github.com/repos/harrisonrodgers/synchrobench/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/harrisonrodgers/synchrobench/labels{/name}","releases_url":"https://api.github.com/repos/harrisonrodgers/synchrobench/releases{/id}","deployments_url":"https://api.github.com/repos/harrisonrodgers/synchrobench/deployments","created_at":"2016-03-29T03:22:55Z","updated_at":"2016-03-29T03:23:01Z","pushed_at":"2016-10-21T07:19:02Z","git_url":"git://github.com/harrisonrodgers/synchrobench.git","ssh_url":"git@github.com:harrisonrodgers/synchrobench.git","clone_url":"https://github.com/harrisonrodgers/synchrobench.git","svn_url":"https://github.com/harrisonrodgers/synchrobench","homepage":"","size":1750,"stargazers_count":0,"watchers_count":0,"language":"Java","has_issues":false,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"gramoli:master","ref":"master","sha":"a55eb6471659fd5629680496f014627c87ebc15e","user":{"login":"gramoli","id":1244122,"avatar_url":"https://avatars.githubusercontent.com/u/1244122?v=3","gravatar_id":"","url":"https://api.github.com/users/gramoli","html_url":"https://github.com/gramoli","followers_url":"https://api.github.com/users/gramoli/followers","following_url":"https://api.github.com/users/gramoli/following{/other_user}","gists_url":"https://api.github.com/users/gramoli/gists{/gist_id}","starred_url":"https://api.github.com/users/gramoli/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/gramoli/subscriptions","organizations_url":"https://api.github.com/users/gramoli/orgs","repos_url":"https://api.github.com/users/gramoli/repos","events_url":"https://api.github.com/users/gramoli/events{/privacy}","received_events_url":"https://api.github.com/users/gramoli/received_events","type":"User","site_admin":false},"repo":{"id":2924861,"name":"synchrobench","full_name":"gramoli/synchrobench","owner":{"login":"gramoli","id":1244122,"avatar_url":"https://avatars.githubusercontent.com/u/1244122?v=3","gravatar_id":"","url":"https://api.github.com/users/gramoli","html_url":"https://github.com/gramoli","followers_url":"https://api.github.com/users/gramoli/followers","following_url":"https://api.github.com/users/gramoli/following{/other_user}","gists_url":"https://api.github.com/users/gramoli/gists{/gist_id}","starred_url":"https://api.github.com/users/gramoli/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/gramoli/subscriptions","organizations_url":"https://api.github.com/users/gramoli/orgs","repos_url":"https://api.github.com/users/gramoli/repos","events_url":"https://api.github.com/users/gramoli/events{/privacy}","received_events_url":"https://api.github.com/users/gramoli/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/gramoli/synchrobench","description":"A benchmark to compare synchronization techniques for multicore programming ","fork":false,"url":"https://api.github.com/repos/gramoli/synchrobench","forks_url":"https://api.github.com/repos/gramoli/synchrobench/forks","keys_url":"https://api.github.com/repos/gramoli/synchrobench/keys{/key_id}","collaborators_url":"https://api.github.com/repos/gramoli/synchrobench/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/gramoli/synchrobench/teams","hooks_url":"https://api.github.com/repos/gramoli/synchrobench/hooks","issue_events_url":"https://api.github.com/repos/gramoli/synchrobench/issues/events{/number}","events_url":"https://api.github.com/repos/gramoli/synchrobench/events","assignees_url":"https://api.github.com/repos/gramoli/synchrobench/assignees{/user}","branches_url":"https://api.github.com/repos/gramoli/synchrobench/branches{/branch}","tags_url":"https://api.github.com/repos/gramoli/synchrobench/tags","blobs_url":"https://api.github.com/repos/gramoli/synchrobench/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/gramoli/synchrobench/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/gramoli/synchrobench/git/refs{/sha}","trees_url":"https://api.github.com/repos/gramoli/synchrobench/git/trees{/sha}","statuses_url":"https://api.github.com/repos/gramoli/synchrobench/statuses/{sha}","languages_url":"https://api.github.com/repos/gramoli/synchrobench/languages","stargazers_url":"https://api.github.com/repos/gramoli/synchrobench/stargazers","contributors_url":"https://api.github.com/repos/gramoli/synchrobench/contributors","subscribers_url":"https://api.github.com/repos/gramoli/synchrobench/subscribers","subscription_url":"https://api.github.com/repos/gramoli/synchrobench/subscription","commits_url":"https://api.github.com/repos/gramoli/synchrobench/commits{/sha}","git_commits_url":"https://api.github.com/repos/gramoli/synchrobench/git/commits{/sha}","comments_url":"https://api.github.com/repos/gramoli/synchrobench/comments{/number}","issue_comment_url":"https://api.github.com/repos/gramoli/synchrobench/issues/comments{/number}","contents_url":"https://api.github.com/repos/gramoli/synchrobench/contents/{+path}","compare_url":"https://api.github.com/repos/gramoli/synchrobench/compare/{base}...{head}","merges_url":"https://api.github.com/repos/gramoli/synchrobench/merges","archive_url":"https://api.github.com/repos/gramoli/synchrobench/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/gramoli/synchrobench/downloads","issues_url":"https://api.github.com/repos/gramoli/synchrobench/issues{/number}","pulls_url":"https://api.github.com/repos/gramoli/synchrobench/pulls{/number}","milestones_url":"https://api.github.com/repos/gramoli/synchrobench/milestones{/number}","notifications_url":"https://api.github.com/repos/gramoli/synchrobench/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/gramoli/synchrobench/labels{/name}","releases_url":"https://api.github.com/repos/gramoli/synchrobench/releases{/id}","deployments_url":"https://api.github.com/repos/gramoli/synchrobench/deployments","created_at":"2011-12-06T13:30:37Z","updated_at":"2016-10-16T18:37:10Z","pushed_at":"2016-10-03T04:47:55Z","git_url":"git://github.com/gramoli/synchrobench.git","ssh_url":"git@github.com:gramoli/synchrobench.git","clone_url":"https://github.com/gramoli/synchrobench.git","svn_url":"https://github.com/gramoli/synchrobench","homepage":"","size":1718,"stargazers_count":77,"watchers_count":77,"language":"Java","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":31,"mirror_url":null,"open_issues_count":1,"forks":31,"open_issues":1,"watchers":77,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/gramoli/synchrobench/pulls/12"},"html":{"href":"https://github.com/gramoli/synchrobench/pull/12"},"issue":{"href":"https://api.github.com/repos/gramoli/synchrobench/issues/12"},"comments":{"href":"https://api.github.com/repos/gramoli/synchrobench/issues/12/comments"},"review_comments":{"href":"https://api.github.com/repos/gramoli/synchrobench/pulls/12/comments"},"review_comment":{"href":"https://api.github.com/repos/gramoli/synchrobench/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/gramoli/synchrobench/pulls/12/commits"},"statuses":{"href":"https://api.github.com/repos/gramoli/synchrobench/statuses/486897a9bf68fa7330aee4ff7930c7c29fbf1e85"}},"merged":false,"mergeable":null,"mergeable_state":"unknown","merged_by":null,"comments":0,"review_comments":0,"commits":2,"additions":129,"deletions":71,"changed_files":28}}
{"actor":{"display_login":"harrisonrodgers"}}