{"action":"created","issue":{"url":"https://api.github.com/repos/rust-lang/rust/issues/33090","repository_url":"https://api.github.com/repos/rust-lang/rust","labels_url":"https://api.github.com/repos/rust-lang/rust/issues/33090/labels{/name}","comments_url":"https://api.github.com/repos/rust-lang/rust/issues/33090/comments","events_url":"https://api.github.com/repos/rust-lang/rust/issues/33090/events","html_url":"https://github.com/rust-lang/rust/pull/33090","id":149451782,"number":33090,"title":"Specialize .zip() for efficient slice and slice iteration","user":{"login":"bluss","id":3209739,"avatar_url":"https://avatars.githubusercontent.com/u/3209739?v=3","gravatar_id":"","url":"https://api.github.com/users/bluss","html_url":"https://github.com/bluss","followers_url":"https://api.github.com/users/bluss/followers","following_url":"https://api.github.com/users/bluss/following{/other_user}","gists_url":"https://api.github.com/users/bluss/gists{/gist_id}","starred_url":"https://api.github.com/users/bluss/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/bluss/subscriptions","organizations_url":"https://api.github.com/users/bluss/orgs","repos_url":"https://api.github.com/users/bluss/repos","events_url":"https://api.github.com/users/bluss/events{/privacy}","received_events_url":"https://api.github.com/users/bluss/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/rust-lang/rust/labels/T-libs","name":"T-libs","color":"bfd4f2"}],"state":"open","locked":false,"assignee":{"login":"aturon","id":709807,"avatar_url":"https://avatars.githubusercontent.com/u/709807?v=3","gravatar_id":"","url":"https://api.github.com/users/aturon","html_url":"https://github.com/aturon","followers_url":"https://api.github.com/users/aturon/followers","following_url":"https://api.github.com/users/aturon/following{/other_user}","gists_url":"https://api.github.com/users/aturon/gists{/gist_id}","starred_url":"https://api.github.com/users/aturon/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/aturon/subscriptions","organizations_url":"https://api.github.com/users/aturon/orgs","repos_url":"https://api.github.com/users/aturon/repos","events_url":"https://api.github.com/users/aturon/events{/privacy}","received_events_url":"https://api.github.com/users/aturon/received_events","type":"User","site_admin":false},"milestone":null,"comments":14,"created_at":"2016-04-19T12:48:37Z","updated_at":"2016-04-22T20:04:59Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/rust-lang/rust/pulls/33090","html_url":"https://github.com/rust-lang/rust/pull/33090","diff_url":"https://github.com/rust-lang/rust/pull/33090.diff","patch_url":"https://github.com/rust-lang/rust/pull/33090.patch"},"body":"The idea is to introduce a private trait TrustedRandomAccess and specialize .zip() for random access iterators into a counted loop.\r\n\r\nThe implementation in the PR is internal and has no visible effect in the API\r\n\r\nWhy a counted loop? To have each slice iterator compile to just a pointer, and both pointers are indexed with the same loop counter value in the generated code. When this succeeds, copying loops are readily recognized and replaced with memcpy and addition loops autovectorize well.\r\n\r\n\r\n### TrustedRandomAccess\r\n\r\nThe TrustedRandomAccess approach works very well on the surface. Microbenchmarks optimize well, following the ideas above, and that is a dramatic improvement of .zip()'s codegen.\r\n\r\n```rust\r\n// old zip before this PR: bad, byte-for-byte loop\r\n// with specialized zip: memcpy\r\npub fn copy_zip(xs: &[u8], ys: &mut [u8]) {\r\n    for (a, b) in ys.iter_mut().zip(xs) {\r\n        *a = *b;\r\n    }\r\n}\r\n\r\n// old zip before this PR: single addition per iteration\r\n// with specialized zip: vectorized\r\npub fn add_zip(xs: &[f32], ys: &mut [f32]) {\r\n    for (a, b) in ys.iter_mut().zip(xs) { *a += *b; }\r\n}\r\n\r\n\r\n// old zip before this PR: single addition per iteration\r\n// with specialized zip: vectorized (!!)\r\npub fn add_zip3(xs: &[f32], ys: &[f32], zs: &mut [f32]) {\r\n    for ((a, b), c) in zs.iter_mut().zip(xs).zip(ys) { *a += *b * *c; }\r\n}\r\n```\r\n\r\n## Non-null issues\r\n\r\nYet in more complex situations, the .zip() loop can still fall back to its old behavior where phantom null checks throw in fake premature end of the loop conditionals. Remember that a NULL inside\r\nOption<(&T, &T)> makes it a `None` value and a premature (in this case)\r\nend of the loop.\r\n\r\nSo even if we have 1) an explicit `Some` in the code and 2) the types of the pointers are `&T` or `&mut T` which are nonnull, we can still get a phantom null check at that point.\r\n\r\nOne example that illustrates the difference is `copy_zip` with slice versus Vec arguments. The involved iterator types are exactly the same, but the Vec version doesn't compile down to memcpy. Investigating into this, the function argument metadata emitted to llvm plays the biggest role. As @eddyb summarized, we need nonnull for the loop to autovectorize and noalias for it to replace with memcpy.\r\n\r\nThere was an experiment to use `assume` to add a non-null assumption on each of the two elements in the specialized zip iterator, but this only helped in some of the test cases and regressed others. Instead I think the nonnull/noalias metadata issue is something we need to solve separately anyway.\r\n\r\n### Adaptors\r\n\r\nThese have conditionally implemented TrustedRandomAccess\r\n\r\n- Enumerate\r\n- Zip\r\n\r\nThese have not implemented it\r\n\r\n- Map is sideeffectful. The forward case would be workable, but the double ended case is complicated.\r\n- Chain, exact length semantics unclear\r\n- Filter, FilterMap, FlatMap and many others don't offer random access and/or exact length"},"comment":{"url":"https://api.github.com/repos/rust-lang/rust/issues/comments/213571641","html_url":"https://github.com/rust-lang/rust/pull/33090#issuecomment-213571641","issue_url":"https://api.github.com/repos/rust-lang/rust/issues/33090","id":213571641,"user":{"login":"alexcrichton","id":64996,"avatar_url":"https://avatars.githubusercontent.com/u/64996?v=3","gravatar_id":"","url":"https://api.github.com/users/alexcrichton","html_url":"https://github.com/alexcrichton","followers_url":"https://api.github.com/users/alexcrichton/followers","following_url":"https://api.github.com/users/alexcrichton/following{/other_user}","gists_url":"https://api.github.com/users/alexcrichton/gists{/gist_id}","starred_url":"https://api.github.com/users/alexcrichton/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/alexcrichton/subscriptions","organizations_url":"https://api.github.com/users/alexcrichton/orgs","repos_url":"https://api.github.com/users/alexcrichton/repos","events_url":"https://api.github.com/users/alexcrichton/events{/privacy}","received_events_url":"https://api.github.com/users/alexcrichton/received_events","type":"User","site_admin":false},"created_at":"2016-04-22T20:04:59Z","updated_at":"2016-04-22T20:04:59Z","body":"Nice!\r\n\r\nI'm definitely in favor of merging :) (but will defer to libs triage at least)"}}