{"action":"closed","number":619,"pull_request":{"url":"https://api.github.com/repos/boostorg/compute/pulls/619","id":74801339,"html_url":"https://github.com/boostorg/compute/pull/619","diff_url":"https://github.com/boostorg/compute/pull/619.diff","patch_url":"https://github.com/boostorg/compute/pull/619.patch","issue_url":"https://api.github.com/repos/boostorg/compute/issues/619","number":619,"state":"closed","locked":false,"title":"Comparison sort (for GPUs)","user":{"login":"haahh","id":2720260,"avatar_url":"https://avatars.githubusercontent.com/u/2720260?v=3","gravatar_id":"","url":"https://api.github.com/users/haahh","html_url":"https://github.com/haahh","followers_url":"https://api.github.com/users/haahh/followers","following_url":"https://api.github.com/users/haahh/following{/other_user}","gists_url":"https://api.github.com/users/haahh/gists{/gist_id}","starred_url":"https://api.github.com/users/haahh/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/haahh/subscriptions","organizations_url":"https://api.github.com/users/haahh/orgs","repos_url":"https://api.github.com/users/haahh/repos","events_url":"https://api.github.com/users/haahh/events{/privacy}","received_events_url":"https://api.github.com/users/haahh/received_events","type":"User","site_admin":false},"body":"This adds comparison sort,  sort-by-key, stable sort, stable sort-by-key algorithms. They're all based on counting merge sort. Additionally, for non-stable sorts there is a block sort step (i.e. sorting subarrays of elements) based on bitonic sorter which uses local memory. \r\n\r\nTests included.\r\n\r\nLater this week I'll test stable block sort.\r\n\r\n### Performance\r\n\r\nI couldn't make a working `perf_bolt_comparison_sort`. I think there's something wrong with Bolt or my installation of Bolt. However, I've manged to make a change inside Bolt library that forces it to use comparison sort in sort().\r\n\r\n```\r\n=== comparison_sort with compute (it's not stable) ===\r\nsize,time (ms)\r\n2,0.090120\r\n4,0.100572\r\n8,0.095840\r\n16,0.124584\r\n32,0.253873\r\n64,0.154097\r\n128,0.135110\r\n256,0.161665\r\n512,0.328393\r\n1024,0.421878\r\n2048,0.562983\r\n4096,0.666007\r\n8192,0.826941\r\n16384,0.943715\r\n32768,1.160150\r\n65536,1.135010\r\n131072,1.387090\r\n262144,1.277340\r\n524288,2.092640\r\n1048576,3.362030\r\n2097152,6.242780\r\n4194304,12.996700\r\n8388608,28.479800\r\n16777216,61.555000\r\n33554432,134.799000\r\n\r\n=== sort with bolt (forced to use comparison sort, stable) ===\r\nsize,time (ms)\r\n2,0.062625\r\n4,0.049883\r\n8,0.053240\r\n16,0.063964\r\n32,0.064557\r\n64,0.059619\r\n128,0.998828\r\n256,1.116950\r\n512,1.208020\r\n1024,1.242320\r\n2048,1.148320\r\n4096,1.205540\r\n8192,1.148740\r\n16384,1.215990\r\n32768,1.295780\r\n65536,1.522320\r\n131072,2.452030\r\n262144,1.685660\r\n524288,2.143900\r\n1048576,3.853150\r\n2097152,8.349480\r\n4194304,17.739800\r\n8388608,38.839500\r\n16777216,83.740300\r\n33554432,182.363000\r\n\r\n=== comparison_sort with compute (stable) ===\r\nsize,time (ms)\r\n2,0.078412\r\n4,0.093083\r\n8,0.113689\r\n16,0.132868\r\n32,0.625694\r\n64,0.739580\r\n128,0.875305\r\n256,0.968895\r\n512,1.103770\r\n1024,1.185820\r\n2048,1.333790\r\n4096,1.417630\r\n8192,1.587050\r\n16384,1.886840\r\n32768,1.879140\r\n65536,1.955670\r\n131072,2.141840\r\n262144,2.393540\r\n524288,3.265350\r\n1048576,4.328050\r\n2097152,7.674590\r\n4194304,15.662900\r\n8388608,33.965800\r\n16777216,73.278500\r\n33554432,159.330000\r\n```","created_at":"2016-06-22T15:08:27Z","updated_at":"2016-06-24T03:24:38Z","closed_at":"2016-06-24T03:24:38Z","merged_at":"2016-06-24T03:24:38Z","merge_commit_sha":"b3633eb54b8cf3d45c28f75ad69c05d5d2744362","assignee":null,"assignees":[],"milestone":null,"commits_url":"https://api.github.com/repos/boostorg/compute/pulls/619/commits","review_comments_url":"https://api.github.com/repos/boostorg/compute/pulls/619/comments","review_comment_url":"https://api.github.com/repos/boostorg/compute/pulls/comments{/number}","comments_url":"https://api.github.com/repos/boostorg/compute/issues/619/comments","statuses_url":"https://api.github.com/repos/boostorg/compute/statuses/5d31bd0f0797c0fb66b55d12079c6a1ededff7d2","head":{"label":"haahh:pr_comp_sort","ref":"pr_comp_sort","sha":"5d31bd0f0797c0fb66b55d12079c6a1ededff7d2","user":{"login":"haahh","id":2720260,"avatar_url":"https://avatars.githubusercontent.com/u/2720260?v=3","gravatar_id":"","url":"https://api.github.com/users/haahh","html_url":"https://github.com/haahh","followers_url":"https://api.github.com/users/haahh/followers","following_url":"https://api.github.com/users/haahh/following{/other_user}","gists_url":"https://api.github.com/users/haahh/gists{/gist_id}","starred_url":"https://api.github.com/users/haahh/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/haahh/subscriptions","organizations_url":"https://api.github.com/users/haahh/orgs","repos_url":"https://api.github.com/users/haahh/repos","events_url":"https://api.github.com/users/haahh/events{/privacy}","received_events_url":"https://api.github.com/users/haahh/received_events","type":"User","site_admin":false},"repo":{"id":31648019,"name":"compute","full_name":"haahh/compute","owner":{"login":"haahh","id":2720260,"avatar_url":"https://avatars.githubusercontent.com/u/2720260?v=3","gravatar_id":"","url":"https://api.github.com/users/haahh","html_url":"https://github.com/haahh","followers_url":"https://api.github.com/users/haahh/followers","following_url":"https://api.github.com/users/haahh/following{/other_user}","gists_url":"https://api.github.com/users/haahh/gists{/gist_id}","starred_url":"https://api.github.com/users/haahh/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/haahh/subscriptions","organizations_url":"https://api.github.com/users/haahh/orgs","repos_url":"https://api.github.com/users/haahh/repos","events_url":"https://api.github.com/users/haahh/events{/privacy}","received_events_url":"https://api.github.com/users/haahh/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/haahh/compute","description":"A C++ GPU Computing Library for OpenCL","fork":true,"url":"https://api.github.com/repos/haahh/compute","forks_url":"https://api.github.com/repos/haahh/compute/forks","keys_url":"https://api.github.com/repos/haahh/compute/keys{/key_id}","collaborators_url":"https://api.github.com/repos/haahh/compute/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/haahh/compute/teams","hooks_url":"https://api.github.com/repos/haahh/compute/hooks","issue_events_url":"https://api.github.com/repos/haahh/compute/issues/events{/number}","events_url":"https://api.github.com/repos/haahh/compute/events","assignees_url":"https://api.github.com/repos/haahh/compute/assignees{/user}","branches_url":"https://api.github.com/repos/haahh/compute/branches{/branch}","tags_url":"https://api.github.com/repos/haahh/compute/tags","blobs_url":"https://api.github.com/repos/haahh/compute/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/haahh/compute/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/haahh/compute/git/refs{/sha}","trees_url":"https://api.github.com/repos/haahh/compute/git/trees{/sha}","statuses_url":"https://api.github.com/repos/haahh/compute/statuses/{sha}","languages_url":"https://api.github.com/repos/haahh/compute/languages","stargazers_url":"https://api.github.com/repos/haahh/compute/stargazers","contributors_url":"https://api.github.com/repos/haahh/compute/contributors","subscribers_url":"https://api.github.com/repos/haahh/compute/subscribers","subscription_url":"https://api.github.com/repos/haahh/compute/subscription","commits_url":"https://api.github.com/repos/haahh/compute/commits{/sha}","git_commits_url":"https://api.github.com/repos/haahh/compute/git/commits{/sha}","comments_url":"https://api.github.com/repos/haahh/compute/comments{/number}","issue_comment_url":"https://api.github.com/repos/haahh/compute/issues/comments{/number}","contents_url":"https://api.github.com/repos/haahh/compute/contents/{+path}","compare_url":"https://api.github.com/repos/haahh/compute/compare/{base}...{head}","merges_url":"https://api.github.com/repos/haahh/compute/merges","archive_url":"https://api.github.com/repos/haahh/compute/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/haahh/compute/downloads","issues_url":"https://api.github.com/repos/haahh/compute/issues{/number}","pulls_url":"https://api.github.com/repos/haahh/compute/pulls{/number}","milestones_url":"https://api.github.com/repos/haahh/compute/milestones{/number}","notifications_url":"https://api.github.com/repos/haahh/compute/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/haahh/compute/labels{/name}","releases_url":"https://api.github.com/repos/haahh/compute/releases{/id}","deployments_url":"https://api.github.com/repos/haahh/compute/deployments","created_at":"2015-03-04T09:11:05Z","updated_at":"2016-03-09T14:14:39Z","pushed_at":"2016-06-23T13:57:50Z","git_url":"git://github.com/haahh/compute.git","ssh_url":"git@github.com:haahh/compute.git","clone_url":"https://github.com/haahh/compute.git","svn_url":"https://github.com/haahh/compute","homepage":"http://kylelutz.github.io/compute/","size":8378,"stargazers_count":0,"watchers_count":0,"language":"C++","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":"boostorg:develop","ref":"develop","sha":"04e7dde2204fb30eb223679ddefe437757a6feb9","user":{"login":"boostorg","id":3170529,"avatar_url":"https://avatars.githubusercontent.com/u/3170529?v=3","gravatar_id":"","url":"https://api.github.com/users/boostorg","html_url":"https://github.com/boostorg","followers_url":"https://api.github.com/users/boostorg/followers","following_url":"https://api.github.com/users/boostorg/following{/other_user}","gists_url":"https://api.github.com/users/boostorg/gists{/gist_id}","starred_url":"https://api.github.com/users/boostorg/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/boostorg/subscriptions","organizations_url":"https://api.github.com/users/boostorg/orgs","repos_url":"https://api.github.com/users/boostorg/repos","events_url":"https://api.github.com/users/boostorg/events{/privacy}","received_events_url":"https://api.github.com/users/boostorg/received_events","type":"Organization","site_admin":false},"repo":{"id":8526347,"name":"compute","full_name":"boostorg/compute","owner":{"login":"boostorg","id":3170529,"avatar_url":"https://avatars.githubusercontent.com/u/3170529?v=3","gravatar_id":"","url":"https://api.github.com/users/boostorg","html_url":"https://github.com/boostorg","followers_url":"https://api.github.com/users/boostorg/followers","following_url":"https://api.github.com/users/boostorg/following{/other_user}","gists_url":"https://api.github.com/users/boostorg/gists{/gist_id}","starred_url":"https://api.github.com/users/boostorg/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/boostorg/subscriptions","organizations_url":"https://api.github.com/users/boostorg/orgs","repos_url":"https://api.github.com/users/boostorg/repos","events_url":"https://api.github.com/users/boostorg/events{/privacy}","received_events_url":"https://api.github.com/users/boostorg/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/boostorg/compute","description":"A C++ GPU Computing Library for OpenCL","fork":false,"url":"https://api.github.com/repos/boostorg/compute","forks_url":"https://api.github.com/repos/boostorg/compute/forks","keys_url":"https://api.github.com/repos/boostorg/compute/keys{/key_id}","collaborators_url":"https://api.github.com/repos/boostorg/compute/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/boostorg/compute/teams","hooks_url":"https://api.github.com/repos/boostorg/compute/hooks","issue_events_url":"https://api.github.com/repos/boostorg/compute/issues/events{/number}","events_url":"https://api.github.com/repos/boostorg/compute/events","assignees_url":"https://api.github.com/repos/boostorg/compute/assignees{/user}","branches_url":"https://api.github.com/repos/boostorg/compute/branches{/branch}","tags_url":"https://api.github.com/repos/boostorg/compute/tags","blobs_url":"https://api.github.com/repos/boostorg/compute/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/boostorg/compute/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/boostorg/compute/git/refs{/sha}","trees_url":"https://api.github.com/repos/boostorg/compute/git/trees{/sha}","statuses_url":"https://api.github.com/repos/boostorg/compute/statuses/{sha}","languages_url":"https://api.github.com/repos/boostorg/compute/languages","stargazers_url":"https://api.github.com/repos/boostorg/compute/stargazers","contributors_url":"https://api.github.com/repos/boostorg/compute/contributors","subscribers_url":"https://api.github.com/repos/boostorg/compute/subscribers","subscription_url":"https://api.github.com/repos/boostorg/compute/subscription","commits_url":"https://api.github.com/repos/boostorg/compute/commits{/sha}","git_commits_url":"https://api.github.com/repos/boostorg/compute/git/commits{/sha}","comments_url":"https://api.github.com/repos/boostorg/compute/comments{/number}","issue_comment_url":"https://api.github.com/repos/boostorg/compute/issues/comments{/number}","contents_url":"https://api.github.com/repos/boostorg/compute/contents/{+path}","compare_url":"https://api.github.com/repos/boostorg/compute/compare/{base}...{head}","merges_url":"https://api.github.com/repos/boostorg/compute/merges","archive_url":"https://api.github.com/repos/boostorg/compute/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/boostorg/compute/downloads","issues_url":"https://api.github.com/repos/boostorg/compute/issues{/number}","pulls_url":"https://api.github.com/repos/boostorg/compute/pulls{/number}","milestones_url":"https://api.github.com/repos/boostorg/compute/milestones{/number}","notifications_url":"https://api.github.com/repos/boostorg/compute/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/boostorg/compute/labels{/name}","releases_url":"https://api.github.com/repos/boostorg/compute/releases{/id}","deployments_url":"https://api.github.com/repos/boostorg/compute/deployments","created_at":"2013-03-02T20:15:58Z","updated_at":"2016-06-22T16:11:57Z","pushed_at":"2016-06-24T03:24:38Z","git_url":"git://github.com/boostorg/compute.git","ssh_url":"git@github.com:boostorg/compute.git","clone_url":"https://github.com/boostorg/compute.git","svn_url":"https://github.com/boostorg/compute","homepage":"http://boostorg.github.io/compute/","size":9456,"stargazers_count":556,"watchers_count":556,"language":"C++","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":true,"forks_count":134,"mirror_url":null,"open_issues_count":101,"forks":134,"open_issues":101,"watchers":556,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/boostorg/compute/pulls/619"},"html":{"href":"https://github.com/boostorg/compute/pull/619"},"issue":{"href":"https://api.github.com/repos/boostorg/compute/issues/619"},"comments":{"href":"https://api.github.com/repos/boostorg/compute/issues/619/comments"},"review_comments":{"href":"https://api.github.com/repos/boostorg/compute/pulls/619/comments"},"review_comment":{"href":"https://api.github.com/repos/boostorg/compute/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/boostorg/compute/pulls/619/commits"},"statuses":{"href":"https://api.github.com/repos/boostorg/compute/statuses/5d31bd0f0797c0fb66b55d12079c6a1ededff7d2"}},"merged":true,"mergeable":null,"mergeable_state":"unknown","merged_by":{"login":"kylelutz","id":45812,"avatar_url":"https://avatars.githubusercontent.com/u/45812?v=3","gravatar_id":"","url":"https://api.github.com/users/kylelutz","html_url":"https://github.com/kylelutz","followers_url":"https://api.github.com/users/kylelutz/followers","following_url":"https://api.github.com/users/kylelutz/following{/other_user}","gists_url":"https://api.github.com/users/kylelutz/gists{/gist_id}","starred_url":"https://api.github.com/users/kylelutz/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/kylelutz/subscriptions","organizations_url":"https://api.github.com/users/kylelutz/orgs","repos_url":"https://api.github.com/users/kylelutz/repos","events_url":"https://api.github.com/users/kylelutz/events{/privacy}","received_events_url":"https://api.github.com/users/kylelutz/received_events","type":"User","site_admin":false},"comments":1,"review_comments":0,"commits":6,"additions":1264,"deletions":11,"changed_files":11}}
{"actor":{"display_login":"kylelutz"}}