{"action":"created","issue":{"url":"https://api.github.com/repos/apple/swift/issues/576","labels_url":"https://api.github.com/repos/apple/swift/issues/576/labels{/name}","comments_url":"https://api.github.com/repos/apple/swift/issues/576/comments","events_url":"https://api.github.com/repos/apple/swift/issues/576/events","html_url":"https://github.com/apple/swift/pull/576","id":122431315,"number":576,"title":"[Performance] iterate the smaller set during Set.intersect()","user":{"login":"dduan","id":75067,"avatar_url":"https://avatars.githubusercontent.com/u/75067?v=3","gravatar_id":"","url":"https://api.github.com/users/dduan","html_url":"https://github.com/dduan","followers_url":"https://api.github.com/users/dduan/followers","following_url":"https://api.github.com/users/dduan/following{/other_user}","gists_url":"https://api.github.com/users/dduan/gists{/gist_id}","starred_url":"https://api.github.com/users/dduan/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/dduan/subscriptions","organizations_url":"https://api.github.com/users/dduan/orgs","repos_url":"https://api.github.com/users/dduan/repos","events_url":"https://api.github.com/users/dduan/events{/privacy}","received_events_url":"https://api.github.com/users/dduan/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":4,"created_at":"2015-12-16T05:25:26Z","updated_at":"2015-12-16T07:18:31Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/apple/swift/pulls/576","html_url":"https://github.com/apple/swift/pull/576","diff_url":"https://github.com/apple/swift/pull/576.diff","patch_url":"https://github.com/apple/swift/pull/576.patch"},"body":"For Set's `intersect()` operation, iterate over the smaller of the two.\r\n\r\nThis change introduces ~~about 1% overhead in speed for average case~~ a small constant cost, but greatly optimizes worst case.\r\n\r\n[Benchmark](https://gist.github.com/dduan/76cdee98624f0ef74bde) result:\r\n\r\n```\r\nmaster, -R\r\n\r\nsmall ∩ large * 100 -- 0.268759667873383\r\nlarge ∩ small * 100 -- 7.67079079151154\r\nsmall ∩ small * 100 -- 0.279738128185272\r\nlarge ∩ large * 100 -- 17.1418876051903\r\ntotal time spent ----- 25.3611761927605\r\n\r\noptimized, -R\r\n\r\nsmall ∩ large * 100 -- 0.275687038898468\r\nlarge ∩ small * 100 -- 0.267830967903137\r\nsmall ∩ small * 100 -- 0.27216911315918\r\nlarge ∩ large * 100 -- 17.287498831749\r\ntotal time spent ----- 18.1031859517097\r\n```\r\n\r\nNote: the benchmark was written for `intersectInPlace()`, which simply calls `intersect()`. Tests in *validation-test/stdlib/Set.swift * passes.\r\n\r\n"},"comment":{"url":"https://api.github.com/repos/apple/swift/issues/comments/165020882","html_url":"https://github.com/apple/swift/pull/576#issuecomment-165020882","issue_url":"https://api.github.com/repos/apple/swift/issues/576","id":165020882,"user":{"login":"dabrahams","id":44065,"avatar_url":"https://avatars.githubusercontent.com/u/44065?v=3","gravatar_id":"","url":"https://api.github.com/users/dabrahams","html_url":"https://github.com/dabrahams","followers_url":"https://api.github.com/users/dabrahams/followers","following_url":"https://api.github.com/users/dabrahams/following{/other_user}","gists_url":"https://api.github.com/users/dabrahams/gists{/gist_id}","starred_url":"https://api.github.com/users/dabrahams/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/dabrahams/subscriptions","organizations_url":"https://api.github.com/users/dabrahams/orgs","repos_url":"https://api.github.com/users/dabrahams/repos","events_url":"https://api.github.com/users/dabrahams/events{/privacy}","received_events_url":"https://api.github.com/users/dabrahams/received_events","type":"User","site_admin":false},"created_at":"2015-12-16T07:18:31Z","updated_at":"2015-12-16T07:18:31Z","body":"@dduan Regarding the 1%, that's reassuring, and what I would have expected.  Regarding converting `other` to Set, it's \"OK\" semantically, but it is very wasteful.  If `other` is not a set (e.g. an array) we should treat it as the smaller of the two arguments."}}