{"action":"created","issue":{"url":"https://api.github.com/repos/JuliaLang/julia/issues/29048","repository_url":"https://api.github.com/repos/JuliaLang/julia","labels_url":"https://api.github.com/repos/JuliaLang/julia/issues/29048/labels{/name}","comments_url":"https://api.github.com/repos/JuliaLang/julia/issues/29048/comments","events_url":"https://api.github.com/repos/JuliaLang/julia/issues/29048/events","html_url":"https://github.com/JuliaLang/julia/pull/29048","id":357222412,"node_id":"MDExOlB1bGxSZXF1ZXN0MjEzMjg4Mzc0","number":29048,"title":"RFC: Iterate over smaller set for setdiff[!](a,b)","user":{"login":"laborg","id":9527104,"node_id":"MDQ6VXNlcjk1MjcxMDQ=","avatar_url":"https://avatars1.githubusercontent.com/u/9527104?v=4","gravatar_id":"","url":"https://api.github.com/users/laborg","html_url":"https://github.com/laborg","followers_url":"https://api.github.com/users/laborg/followers","following_url":"https://api.github.com/users/laborg/following{/other_user}","gists_url":"https://api.github.com/users/laborg/gists{/gist_id}","starred_url":"https://api.github.com/users/laborg/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/laborg/subscriptions","organizations_url":"https://api.github.com/users/laborg/orgs","repos_url":"https://api.github.com/users/laborg/repos","events_url":"https://api.github.com/users/laborg/events{/privacy}","received_events_url":"https://api.github.com/users/laborg/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":0,"created_at":"2018-09-05T13:11:03Z","updated_at":"2018-09-09T22:26:05Z","closed_at":null,"author_association":"NONE","pull_request":{"url":"https://api.github.com/repos/JuliaLang/julia/pulls/29048","html_url":"https://github.com/JuliaLang/julia/pull/29048","diff_url":"https://github.com/JuliaLang/julia/pull/29048.diff","patch_url":"https://github.com/JuliaLang/julia/pull/29048.patch"},"body":"Attempt to fix https://github.com/JuliaLang/julia/issues/25317 by specialising on `setdiff!(a::Set, b::Set)` and iterating over `a` instead of `b` if `length(a) < length(b) * 0.5`. This `0.5` length threshold is a conservative guess after benchmarking has shown, that the iteration over `a` in case `length(a) == length(b)` slows down execution by ~20%.\r\n\r\n`setdiff()` uses `setdiff!` internally, so both profit from the performance improvement.\r\n\r\n## Benchmarks\r\n#### Code:\r\n```\r\nusing Combinatorics\r\ns = Set.([[1],1:450_000,1:550_000,1:1_000_000]);\r\np = collect(permutations([1,2,3,4],2));\r\nfor x in p\r\n    for f in [setdiff, setdiff!]\r\n        l,r = length(s[x[1]]), length(s[x[2]])\r\n        print(lpad(string(f,\"(\",l,\",\",r,\"): \"),28))\r\n        @btime $(f)(y...) evals=1 setup=(y=($copy($s[$x[1]]),$copy($s[$x[2]])))\r\n    end\r\nend\r\n```\r\n#### Master:\r\n```\r\n         setdiff(1,450000):   11.234 ms (5 allocations: 496 bytes)\r\n        setdiff!(1,450000):   11.197 ms (0 allocations: 0 bytes)\r\n         setdiff(1,550000):   12.250 ms (5 allocations: 496 bytes)\r\n        setdiff!(1,550000):   12.740 ms (0 allocations: 0 bytes)\r\n        setdiff(1,1000000):   24.942 ms (5 allocations: 496 bytes)\r\n       setdiff!(1,1000000):   25.276 ms (0 allocations: 0 bytes)\r\n         setdiff(450000,1):   1.742 ms (7 allocations: 9.00 MiB)\r\n        setdiff!(450000,1):   742.000 ns (0 allocations: 0 bytes)\r\n    setdiff(450000,550000):   21.525 ms (7 allocations: 9.00 MiB)\r\n   setdiff!(450000,550000):   18.574 ms (0 allocations: 0 bytes)\r\n   setdiff(450000,1000000):   37.417 ms (7 allocations: 9.00 MiB)\r\n  setdiff!(450000,1000000):   35.589 ms (0 allocations: 0 bytes)\r\n         setdiff(550000,1):   1.719 ms (7 allocations: 9.00 MiB)\r\n        setdiff!(550000,1):   409.000 ns (0 allocations: 0 bytes)\r\n    setdiff(550000,450000):   20.650 ms (7 allocations: 9.00 MiB)\r\n   setdiff!(550000,450000):   18.009 ms (0 allocations: 0 bytes)\r\n   setdiff(550000,1000000):   40.565 ms (7 allocations: 9.00 MiB)\r\n  setdiff!(550000,1000000):   38.338 ms (0 allocations: 0 bytes)\r\n        setdiff(1000000,1):   4.435 ms (7 allocations: 18.00 MiB)\r\n       setdiff!(1000000,1):   748.000 ns (0 allocations: 0 bytes)\r\n   setdiff(1000000,450000):   22.211 ms (7 allocations: 18.00 MiB)\r\n  setdiff!(1000000,450000):   18.457 ms (0 allocations: 0 bytes)\r\n   setdiff(1000000,550000):   24.539 ms (7 allocations: 18.00 MiB)\r\n  setdiff!(1000000,550000):   20.906 ms (0 allocations: 0 bytes)\r\n```\r\n#### This PR:\r\n```\r\n         setdiff(1,450000):   815.000 ns (5 allocations: 496 bytes)\r\n        setdiff!(1,450000):   474.000 ns (0 allocations: 0 bytes)\r\n         setdiff(1,550000):   916.000 ns (5 allocations: 496 bytes)\r\n        setdiff!(1,550000):   414.000 ns (0 allocations: 0 bytes)\r\n        setdiff(1,1000000):   1.813 μs (5 allocations: 496 bytes)\r\n       setdiff!(1,1000000):   715.000 ns (0 allocations: 0 bytes)\r\n         setdiff(450000,1):   1.579 ms (7 allocations: 9.00 MiB)\r\n        setdiff!(450000,1):   341.000 ns (0 allocations: 0 bytes)\r\n    setdiff(450000,550000):   20.185 ms (7 allocations: 9.00 MiB)\r\n   setdiff!(450000,550000):   18.336 ms (0 allocations: 0 bytes)\r\n   setdiff(450000,1000000):   18.241 ms (7 allocations: 9.00 MiB)\r\n  setdiff!(450000,1000000):   16.689 ms (0 allocations: 0 bytes)\r\n         setdiff(550000,1):   1.575 ms (7 allocations: 9.00 MiB)\r\n        setdiff!(550000,1):   391.000 ns (0 allocations: 0 bytes)\r\n    setdiff(550000,450000):   19.741 ms (7 allocations: 9.00 MiB)\r\n   setdiff!(550000,450000):   17.697 ms (0 allocations: 0 bytes)\r\n   setdiff(550000,1000000):   39.603 ms (7 allocations: 9.00 MiB)\r\n  setdiff!(550000,1000000):   38.109 ms (0 allocations: 0 bytes)\r\n        setdiff(1000000,1):   3.316 ms (7 allocations: 18.00 MiB)\r\n       setdiff!(1000000,1):   705.000 ns (0 allocations: 0 bytes)\r\n   setdiff(1000000,450000):   21.766 ms (7 allocations: 18.00 MiB)\r\n  setdiff!(1000000,450000):   18.333 ms (0 allocations: 0 bytes)\r\n   setdiff(1000000,550000):   24.342 ms (7 allocations: 18.00 MiB)\r\n  setdiff!(1000000,550000):   21.027 ms (0 allocations: 0 bytes)\r\n```\r\n"},"comment":{"url":"https://api.github.com/repos/JuliaLang/julia/issues/comments/419749524","html_url":"https://github.com/JuliaLang/julia/pull/29048#issuecomment-419749524","issue_url":"https://api.github.com/repos/JuliaLang/julia/issues/29048","id":419749524,"node_id":"MDEyOklzc3VlQ29tbWVudDQxOTc0OTUyNA==","user":{"login":"StefanKarpinski","id":153596,"node_id":"MDQ6VXNlcjE1MzU5Ng==","avatar_url":"https://avatars2.githubusercontent.com/u/153596?v=4","gravatar_id":"","url":"https://api.github.com/users/StefanKarpinski","html_url":"https://github.com/StefanKarpinski","followers_url":"https://api.github.com/users/StefanKarpinski/followers","following_url":"https://api.github.com/users/StefanKarpinski/following{/other_user}","gists_url":"https://api.github.com/users/StefanKarpinski/gists{/gist_id}","starred_url":"https://api.github.com/users/StefanKarpinski/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/StefanKarpinski/subscriptions","organizations_url":"https://api.github.com/users/StefanKarpinski/orgs","repos_url":"https://api.github.com/users/StefanKarpinski/repos","events_url":"https://api.github.com/users/StefanKarpinski/events{/privacy}","received_events_url":"https://api.github.com/users/StefanKarpinski/received_events","type":"User","site_admin":false},"created_at":"2018-09-09T22:26:05Z","updated_at":"2018-09-09T22:26:05Z","author_association":"MEMBER","body":"Is the 2x length ration threshold empirically determined or is there some intuition behind it? Either way it's probably worth noting in a comment."}}
{"actor":{"display_login":"StefanKarpinski"}}