{"action":"created","issue":{"url":"https://api.github.com/repos/JuliaLang/julia/issues/15356","repository_url":"https://api.github.com/repos/JuliaLang/julia","labels_url":"https://api.github.com/repos/JuliaLang/julia/issues/15356/labels{/name}","comments_url":"https://api.github.com/repos/JuliaLang/julia/issues/15356/comments","events_url":"https://api.github.com/repos/JuliaLang/julia/issues/15356/events","html_url":"https://github.com/JuliaLang/julia/pull/15356","id":138492593,"number":15356,"title":"Add shareindexes macro for (sometimes) faster iteration","user":{"login":"timholy","id":1525481,"avatar_url":"https://avatars.githubusercontent.com/u/1525481?v=3","gravatar_id":"","url":"https://api.github.com/users/timholy","html_url":"https://github.com/timholy","followers_url":"https://api.github.com/users/timholy/followers","following_url":"https://api.github.com/users/timholy/following{/other_user}","gists_url":"https://api.github.com/users/timholy/gists{/gist_id}","starred_url":"https://api.github.com/users/timholy/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/timholy/subscriptions","organizations_url":"https://api.github.com/users/timholy/orgs","repos_url":"https://api.github.com/users/timholy/repos","events_url":"https://api.github.com/users/timholy/events{/privacy}","received_events_url":"https://api.github.com/users/timholy/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":35,"created_at":"2016-03-04T14:45:33Z","updated_at":"2016-03-06T14:24:52Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/JuliaLang/julia/pulls/15356","html_url":"https://github.com/JuliaLang/julia/pull/15356","diff_url":"https://github.com/JuliaLang/julia/pull/15356.diff","patch_url":"https://github.com/JuliaLang/julia/pull/15356.patch"},"body":"I'm preparing another couple of PRs that will expand the range of array iterators (and I'm planning even further expansion later on). I'm thinking ahead about loops that involve multiple arrays. \r\n\r\n### The problem\r\n\r\nCurrently we have two options:\r\n```jl\r\nfor I in eachindex(A, B)\r\n    # body\r\nend\r\n```\r\nand\r\n```jl\r\nfor (IA, IB) in zip(eachindex(A), eachindex(B))\r\n    # body\r\nend\r\n```\r\nMy sense is that our `eachindex(A, B)` mechanism is too limited for the coming brave new world, and should gradually be retired. That means we should use `zip`. However, `zip` sometimes still has performance issues, some of which are unavoidable: when you have to increment two iterators rather than one, it's going to be slower, especially if incrementing is more expensive than the body. See benchmarks below.\r\n\r\n### This PR's solution\r\n\r\nThis PR introduces a new macro, `@shareindexes`, which takes a block like this:\r\n```jl\r\n@shareindexes for (IA,IB) in zip(eachindex(A), eachindex(B))\r\n    @inbounds s += A[IA]*B[IB]\r\nend\r\n```\r\nand turns it into\r\n```jl\r\nRA, RB = eachindex(A), eachindex(B)\r\nif RA == RB\r\n    for I in RA\r\n        @inbounds s += A[I]*B[I]\r\n    end\r\nelse\r\n    for (IA,IB) in zip(RA, RB)\r\n        @inbounds s += A[IA]*B[IB]\r\n    end\r\nend\r\n```\r\n\r\n### An alternative that didn't work\r\n\r\nI tried an alternative implementation based on\r\n```jl\r\nimmutable Zip2Each{I1, I2} <: AbstractZipIterator\r\n    same::Bool\r\n    a::I1\r\n    b::I2\r\nend\r\n```\r\nand then defining `start`, `done`, and `next` functions that test `same` at runtime. Unfortunately, this was slower than just plain `zip`. If we could hoist that `same` check out of the entire block, then this solution would be just like the macro-based solution (but prettier).\r\n\r\n### Benchmarks\r\n\r\nUsing the functions `mydot1`, `mydot2`, and `mydotshared` in the new tests (with a `@simd` added in front of the loop in `mydot1` for good measure), with arrays of size (10001,10000), here are timings.\r\n\r\n```jl\r\nmydot1\r\n  0.093147 seconds (5 allocations: 176 bytes)\r\n  0.094556 seconds (5 allocations: 176 bytes)\r\n  0.094084 seconds (5 allocations: 176 bytes)\r\nmydot2\r\n  0.115129 seconds (5 allocations: 176 bytes)\r\n  0.796566 seconds (5 allocations: 176 bytes)\r\n  0.161923 seconds (5 allocations: 176 bytes)\r\nmydotshared\r\n  0.114697 seconds (5 allocations: 176 bytes)\r\n  0.180229 seconds (5 allocations: 176 bytes)\r\n  0.161990 seconds (5 allocations: 176 bytes)\r\n```\r\nLike in the tests, the first in each block is for a pair of `LinearFast` arrays, the second for `LinearSlow` arrays, and third with one of each.\r\n\r\nI'm not quite sure why `mydotshared` isn't as fast as `mydot1`, but I've verified that this also holds when I write out that function manually rather than using the macro. The noteworthy case is when there are two `CartesianRange` iterators, which yields a ~4x speedup.\r\n\r\nCC @JeffBezanson, @mbauman.\r\n"},"comment":{"url":"https://api.github.com/repos/JuliaLang/julia/issues/comments/192895734","html_url":"https://github.com/JuliaLang/julia/pull/15356#issuecomment-192895734","issue_url":"https://api.github.com/repos/JuliaLang/julia/issues/15356","id":192895734,"user":{"login":"nalimilan","id":1120448,"avatar_url":"https://avatars.githubusercontent.com/u/1120448?v=3","gravatar_id":"","url":"https://api.github.com/users/nalimilan","html_url":"https://github.com/nalimilan","followers_url":"https://api.github.com/users/nalimilan/followers","following_url":"https://api.github.com/users/nalimilan/following{/other_user}","gists_url":"https://api.github.com/users/nalimilan/gists{/gist_id}","starred_url":"https://api.github.com/users/nalimilan/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/nalimilan/subscriptions","organizations_url":"https://api.github.com/users/nalimilan/orgs","repos_url":"https://api.github.com/users/nalimilan/repos","events_url":"https://api.github.com/users/nalimilan/events{/privacy}","received_events_url":"https://api.github.com/users/nalimilan/received_events","type":"User","site_admin":false},"created_at":"2016-03-06T14:24:52Z","updated_at":"2016-03-06T14:24:52Z","body":"Oops, so `false` wouldn't have made any difference. This means on my machine `Zip2Same` is fast already. Could you post the native code for `Zip2Same` and `mydot1` for two `LinearFast` arrays? I don't understand what should make such a difference... (Then I should go back to work. :-)"}}