{"action":"closed","number":489,"pull_request":{"url":"https://api.github.com/repos/boostorg/compute/pulls/489","id":41405148,"html_url":"https://github.com/boostorg/compute/pull/489","diff_url":"https://github.com/boostorg/compute/pull/489.diff","patch_url":"https://github.com/boostorg/compute/pull/489.patch","issue_url":"https://api.github.com/repos/boostorg/compute/issues/489","number":489,"state":"closed","locked":false,"title":"Using serial merge in merge() for small inputs","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":"It turns out that for relatively small serial merge algorithm outperforms merge with merge path, so I added `serial_merge_threshold` (what is considered \"small\" depends on used device). When input size is less or equal to `serial_merge_threshold` serial merge is used; otherwise merge with merge path is used. \r\n\r\nI thought I would have had to implement the serial merge, but it had been already implemented, just not used.\r\n\r\nDefault `serial_merge_threshold` threshold value depends on device type - for CPUs it's 32768, for GPUs only 2048 (these values were obtained experimentally and are customizable). \r\n\r\nBenchmarks (thresholds are marked by `<---- `):\r\n\r\nstd::merge():\r\n```\r\n=== merge with stl ===\r\nsize,time (ms)\r\n2,0.000229\r\n4,0.000233\r\n8,0.000236\r\n16,0.000250\r\n32,0.000279\r\n64,0.000394\r\n128,0.000617\r\n256,0.000846\r\n512,0.002174\r\n1024,0.004317\r\n2048,0.008136\r\n4096,0.015567\r\n8192,0.030530\r\n16384,0.061601\r\n32768,0.121734\r\n65536,0.244034\r\n131072,0.496816\r\n262144,0.981112\r\n524288,1.984900\r\n1048576,4.030950\r\n2097152,8.135040\r\n4194304,16.310800\r\n8388608,32.556800\r\n16777216,65.152000\r\n33554432,130.599000\r\n```\r\n\r\nboost::compute::merge() on a CPU (AMD Phenom(tm) II X3 710 Processor):\r\n```\r\n=== merge with compute === [ without serial_merge (only merge with merge path) ]\r\nsize,time (ms)\r\n2,0.137814\r\n4,0.137454\r\n8,0.141248\r\n16,0.142791\r\n32,0.143798\r\n64,0.143406\r\n128,0.141068\r\n256,0.143525\r\n512,0.141164\r\n1024,0.169392\r\n2048,0.172788\r\n4096,0.180366\r\n8192,0.169614\r\n16384,0.182455\r\n32768,0.254819  <---- \r\n65536,0.289103\r\n131072,0.412289\r\n262144,0.654884\r\n524288,1.164300\r\n1048576,2.134720\r\n2097152,4.380490\r\n4194304,8.719900\r\n8388608,17.663100\r\n16777216,38.439100\r\n33554432,72.113500\r\n\r\n=== merge with compute === [ only serial merge ]\r\nsize,time (ms)\r\n2,0.058376\r\n4,0.057207\r\n8,0.062837\r\n16,0.058138\r\n32,0.062957\r\n64,0.061984\r\n128,0.059702\r\n256,0.062744\r\n512,0.062106\r\n1024,0.063178\r\n2048,0.071656\r\n4096,0.076726\r\n8192,0.095142\r\n16384,0.125700\r\n32768,0.195831  <---- \r\n65536,0.339624\r\n131072,0.642904\r\n262144,1.202200\r\n524288,2.312620\r\n1048576,4.715070\r\n2097152,9.641130\r\n4194304,19.093200\r\n8388608,37.998500\r\n16777216,75.857500\r\n33554432,146.022000\r\n\r\n=== merge with compute === [ serial merge if total number of elements in merged arrays <= 32768 ]\r\nsize,time (ms)\r\n2,0.058443\r\n4,0.063942\r\n8,0.063722\r\n16,0.064250\r\n32,0.060205\r\n64,0.060295\r\n128,0.064665\r\n256,0.065801\r\n512,0.066322\r\n1024,0.065031\r\n2048,0.072310\r\n4096,0.081465\r\n8192,0.094621\r\n16384,0.133090\r\n32768,0.202007 <---- \r\n65536,0.284340\r\n131072,0.416663\r\n262144,0.648286\r\n524288,1.170250\r\n1048576,2.150280\r\n2097152,4.402920\r\n4194304,8.793680\r\n8388608,17.586700\r\n16777216,38.545000\r\n33554432,71.988800\r\n```\r\n\r\nboost::compute::merge() on a GPU (AMD Radeon HD7770 1GB / Capeverde):\r\n\r\n```\r\n=== merge with compute === [ without serial_merge ]\r\nsize,time (ms)\r\n2,0.328907\r\n4,0.335311\r\n8,0.347259\r\n16,0.357102\r\n32,0.365325\r\n64,0.403433\r\n128,0.490579\r\n256,0.450781\r\n512,0.544281\r\n1024,0.952850\r\n2048,1.112820  <---- \r\n4096,1.311940\r\n8192,1.522100\r\n16384,1.808190\r\n32768,2.086470\r\n65536,2.497830\r\n131072,2.580760\r\n262144,2.882870\r\n524288,2.946730\r\n1048576,3.831830\r\n2097152,10.249500\r\n4194304,25.594700\r\n8388608,36.070100\r\n16777216,57.824400\r\n33554432,106.386000\r\n\r\n=== merge with compute === [ serial merge if total number of elements in merged arrays <= 2048 ]\r\nsize,time (ms)\r\n2,0.105126\r\n4,0.106514\r\n8,0.103712\r\n16,0.115010\r\n32,0.130541\r\n64,0.159552\r\n128,0.217301\r\n256,0.286446\r\n512,0.469712\r\n1024,0.350405\r\n2048,0.674871 <---- \r\n4096,1.366230\r\n8192,1.519220\r\n16384,1.833550\r\n32768,2.160120\r\n65536,2.509000\r\n131072,2.604350\r\n262144,2.880300\r\n524288,2.940640\r\n1048576,3.862740\r\n2097152,11.878900\r\n4194304,26.006100\r\n8388608,35.588900\r\n16777216,60.163800\r\n33554432,106.400000\r\n```\r\n\r\nI also added `queue.finish()` to `perf_merge.cpp`, without execution time is measured wrongly as `boost::compute::merge()` is not synchronous.","created_at":"2015-08-01T17:45:44Z","updated_at":"2015-08-01T20:44:52Z","closed_at":"2015-08-01T20:44:52Z","merged_at":"2015-08-01T20:44:52Z","merge_commit_sha":"4f5ea78d58d066402465797c89426db4d84c8eef","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/boostorg/compute/pulls/489/commits","review_comments_url":"https://api.github.com/repos/boostorg/compute/pulls/489/comments","review_comment_url":"https://api.github.com/repos/boostorg/compute/pulls/comments{/number}","comments_url":"https://api.github.com/repos/boostorg/compute/issues/489/comments","statuses_url":"https://api.github.com/repos/boostorg/compute/statuses/e3324f887da776dc726d61beb492d4267d352d88","head":{"label":"haahh:pr_serial_merge","ref":"pr_serial_merge","sha":"e3324f887da776dc726d61beb492d4267d352d88","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}","created_at":"2015-03-04T09:11:05Z","updated_at":"2015-03-04T09:11:06Z","pushed_at":"2015-08-01T17:42:20Z","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":8624,"stargazers_count":0,"watchers_count":0,"language":"C++","has_issues":false,"has_downloads":true,"has_wiki":true,"has_pages":true,"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":"ffd35b09ebbe0c6012a8a58a2ae8ec6c492d8c82","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}","created_at":"2013-03-02T20:15:58Z","updated_at":"2015-08-01T06:28:13Z","pushed_at":"2015-08-01T20:44:52Z","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":12000,"stargazers_count":414,"watchers_count":414,"language":"C++","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":true,"forks_count":85,"mirror_url":null,"open_issues_count":90,"forks":85,"open_issues":90,"watchers":414,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/boostorg/compute/pulls/489"},"html":{"href":"https://github.com/boostorg/compute/pull/489"},"issue":{"href":"https://api.github.com/repos/boostorg/compute/issues/489"},"comments":{"href":"https://api.github.com/repos/boostorg/compute/issues/489/comments"},"review_comments":{"href":"https://api.github.com/repos/boostorg/compute/pulls/489/comments"},"review_comment":{"href":"https://api.github.com/repos/boostorg/compute/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/boostorg/compute/pulls/489/commits"},"statuses":{"href":"https://api.github.com/repos/boostorg/compute/statuses/e3324f887da776dc726d61beb492d4267d352d88"}},"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":0,"review_comments":0,"commits":1,"additions":65,"deletions":26,"changed_files":4}}