{"action":"closed","issue":{"url":"https://api.github.com/repos/boostorg/compute/issues/405","repository_url":"https://api.github.com/repos/boostorg/compute","labels_url":"https://api.github.com/repos/boostorg/compute/issues/405/labels{/name}","comments_url":"https://api.github.com/repos/boostorg/compute/issues/405/comments","events_url":"https://api.github.com/repos/boostorg/compute/issues/405/events","html_url":"https://github.com/boostorg/compute/issues/405","id":53185156,"number":405,"title":"Unexpected performance discrepancy in set algorithms","user":{"login":"jbytheway","id":52664,"avatar_url":"https://avatars0.githubusercontent.com/u/52664?v=3","gravatar_id":"","url":"https://api.github.com/users/jbytheway","html_url":"https://github.com/jbytheway","followers_url":"https://api.github.com/users/jbytheway/followers","following_url":"https://api.github.com/users/jbytheway/following{/other_user}","gists_url":"https://api.github.com/users/jbytheway/gists{/gist_id}","starred_url":"https://api.github.com/users/jbytheway/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jbytheway/subscriptions","organizations_url":"https://api.github.com/users/jbytheway/orgs","repos_url":"https://api.github.com/users/jbytheway/repos","events_url":"https://api.github.com/users/jbytheway/events{/privacy}","received_events_url":"https://api.github.com/users/jbytheway/received_events","type":"User","site_admin":false},"labels":[{"id":30392182,"url":"https://api.github.com/repos/boostorg/compute/labels/bug","name":"bug","color":"fc2929","default":true}],"state":"closed","locked":false,"assignee":{"login":"jszuppe","id":2720260,"avatar_url":"https://avatars2.githubusercontent.com/u/2720260?v=3","gravatar_id":"","url":"https://api.github.com/users/jszuppe","html_url":"https://github.com/jszuppe","followers_url":"https://api.github.com/users/jszuppe/followers","following_url":"https://api.github.com/users/jszuppe/following{/other_user}","gists_url":"https://api.github.com/users/jszuppe/gists{/gist_id}","starred_url":"https://api.github.com/users/jszuppe/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jszuppe/subscriptions","organizations_url":"https://api.github.com/users/jszuppe/orgs","repos_url":"https://api.github.com/users/jszuppe/repos","events_url":"https://api.github.com/users/jszuppe/events{/privacy}","received_events_url":"https://api.github.com/users/jszuppe/received_events","type":"User","site_admin":false},"assignees":[{"login":"jszuppe","id":2720260,"avatar_url":"https://avatars2.githubusercontent.com/u/2720260?v=3","gravatar_id":"","url":"https://api.github.com/users/jszuppe","html_url":"https://github.com/jszuppe","followers_url":"https://api.github.com/users/jszuppe/followers","following_url":"https://api.github.com/users/jszuppe/following{/other_user}","gists_url":"https://api.github.com/users/jszuppe/gists{/gist_id}","starred_url":"https://api.github.com/users/jszuppe/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jszuppe/subscriptions","organizations_url":"https://api.github.com/users/jszuppe/orgs","repos_url":"https://api.github.com/users/jszuppe/repos","events_url":"https://api.github.com/users/jszuppe/events{/privacy}","received_events_url":"https://api.github.com/users/jszuppe/received_events","type":"User","site_admin":false}],"milestone":null,"comments":7,"created_at":"2014-12-31T14:03:47Z","updated_at":"2017-06-14T16:16:46Z","closed_at":"2017-06-14T16:16:46Z","body":"On my system (using an NVidia GeForce GTX 660), I get a huge discrepancy between the performance of the various set_\\* algorithms.  set_intersection and set_difference are _very_ fast; for example:\n\n```\n=== set_intersection with stl ===\nsize,time (ms)\n2,0.000698\n4,0.000768\n8,0.000838\n16,0.000769\n32,0.001118\n64,0.000838\n128,0.001048\n256,0.001187\n512,0.001955\n1024,0.002723\n2048,0.004260\n4096,0.007193\n8192,0.012920\n16384,0.024305\n32768,0.047003\n65536,0.092749\n131072,0.184521\n262144,0.367295\n524288,0.735636\n1048576,1.607250\n2097152,3.364600\n4194304,7.629370\n8388608,13.173300\n16777216,26.183100\n33554432,52.908400\n=== set_intersection with compute ===\nsize,time (ms)\n2,0.473732\n4,0.475967\n8,0.459625\n16,0.470938\n32,0.465002\n64,0.462488\n128,0.462348\n256,0.452012\n512,0.453619\n1024,0.491263\n2048,0.546367\n4096,0.694710\n8192,0.531910\n16384,0.493218\n32768,0.578773\n65536,0.523530\n131072,0.521364\n262144,0.824754\n524288,0.784455\n1048576,0.788227\n2097152,0.847941\n4194304,0.821052\n8388608,0.786342\n16777216,0.815046\n33554432,0.959408\n```\n\nThis is about 50 times faster than STL.\n\nOn the other hand, set_union and set_symmetric_difference are rather slow.  For example:\n\n```\n=== set_union with stl ===\nsize,time (ms)\n2,0.000838\n4,0.000698\n8,0.000838\n16,0.000769\n32,0.000768\n64,0.000838\n128,0.000908\n256,0.001257\n512,0.001188\n1024,0.001676\n2048,0.002654\n4096,0.003912\n8192,0.007194\n16384,0.012571\n32768,0.024095\n65536,0.047073\n131072,0.092540\n262144,0.183892\n524288,0.367783\n1048576,0.784456\n2097152,1.638820\n4194304,3.238810\n8388608,6.572260\n16777216,13.024300\n33554432,26.403500\n=== set_union with compute ===\nsize,time (ms)\n2,0.472266\n4,0.509141\n8,0.491751\n16,0.475758\n32,0.485187\n64,0.746532\n128,0.575072\n256,0.522341\n512,0.549720\n1024,0.664678\n2048,1.182900\n4096,1.145460\n8192,1.549360\n16384,1.812800\n32768,2.984660\n65536,5.497330\n131072,5.033870\n262144,4.798710\n524288,4.750030\n1048576,5.041970\n2097152,7.866690\n4194304,10.583900\n8388608,22.466900\n16777216,48.658900\n33554432,91.906000\n```\n\nThis is about 3 times slower than STL.  The implementations of the algorithms are very similar, so I wonder what could cause this 100-fold difference in their performance.\n\nI suspect that the test data used in the performance test could be to blame.  I haven't looked, but it would be easy to generate data in such a way that the intersection of the two sets was extremely small, which might cause this (although even then I wouldn't expect quite such a huge discrepancy as this...)\n## \n"}}
{"actor":{"display_login":"jszuppe"}}