{"action":"created","issue":{"url":"https://api.github.com/repos/JuliaLang/julia/issues/15009","repository_url":"https://api.github.com/repos/JuliaLang/julia","labels_url":"https://api.github.com/repos/JuliaLang/julia/issues/15009/labels{/name}","comments_url":"https://api.github.com/repos/JuliaLang/julia/issues/15009/comments","events_url":"https://api.github.com/repos/JuliaLang/julia/issues/15009/events","html_url":"https://github.com/JuliaLang/julia/pull/15009","id":132581880,"number":15009,"title":"Optimized unique and union! methods","user":{"login":"gajomi","id":244887,"avatar_url":"https://avatars.githubusercontent.com/u/244887?v=3","gravatar_id":"","url":"https://api.github.com/users/gajomi","html_url":"https://github.com/gajomi","followers_url":"https://api.github.com/users/gajomi/followers","following_url":"https://api.github.com/users/gajomi/following{/other_user}","gists_url":"https://api.github.com/users/gajomi/gists{/gist_id}","starred_url":"https://api.github.com/users/gajomi/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/gajomi/subscriptions","organizations_url":"https://api.github.com/users/gajomi/orgs","repos_url":"https://api.github.com/users/gajomi/repos","events_url":"https://api.github.com/users/gajomi/events{/privacy}","received_events_url":"https://api.github.com/users/gajomi/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":8,"created_at":"2016-02-10T01:05:46Z","updated_at":"2016-02-19T06:49:59Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/JuliaLang/julia/pulls/15009","html_url":"https://github.com/JuliaLang/julia/pull/15009","diff_url":"https://github.com/JuliaLang/julia/pull/15009.diff","patch_url":"https://github.com/JuliaLang/julia/pull/15009.patch"},"body":"This PR implements performance improvements for unique and union! and adds an additional method signature for unique. The basic outline of the different performance issues can be found in #14649. There are four separates commits in the pull request which implement\r\n\r\n1. optimized methods for associative collections\r\n2. optimized methods for collections with \"small\" eltypes, as well as an additional method unique(c,k), which returns at most k unique elements from a collection c. This is used in the implementation of the aforementioned optimizations, but I think is a useful method in its own right and worth exposing to the user.\r\n3. optimized unique method for range types\r\n4. optimized unique and union methods for sparse-like arrays such as Diagonal,Bidiagonal,SparseVector etc.\r\n\r\nEach of these optimizations have different regimes in which performance improvements become apparent. A benchmark that illustrates performance improvements for unique in action can be seen by looking at the diff in this gist: https://gist.github.com/gajomi/0c184160042ddfc329ab/revisions (results similar for union!). Generally speaking, one sees improvements in walltime performance, although there are some minor performance regressions in memory allocation for some methods. \r\n"},"comment":{"url":"https://api.github.com/repos/JuliaLang/julia/issues/comments/186088930","html_url":"https://github.com/JuliaLang/julia/pull/15009#issuecomment-186088930","issue_url":"https://api.github.com/repos/JuliaLang/julia/issues/15009","id":186088930,"user":{"login":"gajomi","id":244887,"avatar_url":"https://avatars.githubusercontent.com/u/244887?v=3","gravatar_id":"","url":"https://api.github.com/users/gajomi","html_url":"https://github.com/gajomi","followers_url":"https://api.github.com/users/gajomi/followers","following_url":"https://api.github.com/users/gajomi/following{/other_user}","gists_url":"https://api.github.com/users/gajomi/gists{/gist_id}","starred_url":"https://api.github.com/users/gajomi/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/gajomi/subscriptions","organizations_url":"https://api.github.com/users/gajomi/orgs","repos_url":"https://api.github.com/users/gajomi/repos","events_url":"https://api.github.com/users/gajomi/events{/privacy}","received_events_url":"https://api.github.com/users/gajomi/received_events","type":"User","site_admin":false},"created_at":"2016-02-19T06:49:59Z","updated_at":"2016-02-19T06:49:59Z","body":"OK, this took quite a bit longer than I expected (there were many forks in the road I'll to revisit later), but the latest commits should address all the issues raised above. \r\n\r\nNew performance benchmarks can be found here: https://gist.github.com/gajomi/617466a1502dbf920252/revisions?diff=split\r\n\r\nDifferences from first commits:\r\n* The various `union!` specializations to container types versus `eltype`s follows the strategy suggested by @timholy. \r\n* The new  `union!` implementation distinguishes between diagonal dispatch on specialized `eltype`s in both set/array arguments and single dispatch on the `eltype` of the array, which extends the optimization to new cases. \r\n* Where appropriate `Set` annotation are generalized to `AbstractSet`.\r\n* The test coverage was expanded to cover `union!` methods. "}}