Skip to content

/rust

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

iter::Zip is now invariant #35727

Closed
Stebalien opened this Issue Aug 16, 2016 · 15 comments

Comments

Assignees

@bluss bluss

Labels
E-help-wanted T-libs regression-from-stable-to-beta
Projects
None yet
Milestone
No milestone
7 participants
@Stebalien @brson @alexcrichton @bluss @aturon @nikomatsakis @apasel422
@Stebalien
Copy link
Contributor

Stebalien commented Aug 16, 2016

The following compiles on stable but not beta:

use std::iter::Zip;

fn test<'a, A, B>(iter: Zip<&'static A, &'static B>) -> Zip<&'a A, &'a B> { iter }

fn main() {}

@Stebalien Stebalien referenced this issue Aug 16, 2016

Merged

Implement 1581 (FusedIterator) #35656

0 of 3 tasks complete

@apasel422 apasel422 added the A-libs label Aug 16, 2016

@Stebalien

This comment has been minimized.

Sign in to view
Copy link
Contributor Author

Stebalien commented Aug 16, 2016

(also a regression from stable to beta)

@Stebalien Stebalien referenced this issue Aug 16, 2016

Merged

Bump version to 1.13 #35725

@apasel422 apasel422 added the regression-from-stable-to-beta label Aug 16, 2016

@alexcrichton alexcrichton added I-nominated T-libs labels Aug 16, 2016

@brson

This comment has been minimized.

Sign in to view
Copy link
Contributor

brson commented Aug 16, 2016

If this is a beta regression that means it is going to hit stable thursday.
@brson

This comment has been minimized.

Sign in to view
Copy link
Contributor

brson commented Aug 16, 2016

If somebody fixed and landed this right now and we started a stable build tonight we might be able to manage getting this into a Thursday release.
@brson

This comment has been minimized.

Sign in to view
Copy link
Contributor

brson commented Aug 16, 2016

... or we could just end up flubbing and missing our date.

@frewsxcv frewsxcv referenced this issue Aug 16, 2016

Merged

Specialize .zip() for efficient slice and slice iteration #33090

@alexcrichton

This comment has been minimized.

Sign in to view
Copy link
Member

alexcrichton commented Aug 16, 2016

I don't think this is a serious enough regression to halt the release. @Stebalien this was just manufactured, right? There's no code that actually hit this?
@Stebalien

This comment has been minimized.

Sign in to view
Copy link
Contributor Author

Stebalien commented Aug 17, 2016

@brson. The fix is to either revert the zip specializations (simplest) or put the extra fields needed by specialization into the main Zip struct. We can keep the enumerate specialization as-is (it doesn't need extra specialized fields).

@alexcrichton Not my code.
@bluss

This comment has been minimized.

Sign in to view
Copy link
Contributor

bluss commented Aug 17, 2016

Ah this is troublesome, indeed it's the associated types/struct field specialization that causes this, not just the regular "behavioral" specialization isn't it. I can't think of a workaround, we could back out the whole optimization, or just the associated type part?
@alexcrichton

This comment has been minimized.

Sign in to view
Copy link
Member

alexcrichton commented Aug 23, 2016

Discussed at @rust-lang/libs triage today, we concluded that we're likely to revert but we're not sure. @aturon wasn't present unfortunately and he'll likely also have opinions on this as well. We'll discuss again soon.

Our other conclusion was that this wasn't super urgent because it's already hit stable.
@aturon

This comment has been minimized.

Sign in to view
Copy link
Member

aturon commented Sep 12, 2016

cc @nikomatsakis This is a pretty interesting tradeoff -- using specialization on representation destroys any variance.
@nikomatsakis

This comment has been minimized.

Sign in to view
Copy link
Contributor

nikomatsakis commented Sep 12, 2016

That is an interesting dilemma! I don't see an obvious solution though except maybe for explicit variance annotations on traits (that could then be checked by its implementors). i.e., you could say "all values of <T as Foo<'a>>::Type must be covariant w/r/t 'a' and T of something". That seemed like a big pain when we last visited this question.
@aturon

This comment has been minimized.

Sign in to view
Copy link
Member

aturon commented Sep 12, 2016

@nikomatsakis That pretty much echos my thoughts as well.
@nikomatsakis

This comment has been minimized.

Sign in to view
Copy link
Contributor

nikomatsakis commented Sep 12, 2016

@aturon there is a general desire for being able to prevent variance regressions (as expressed by e.g. @brson). I had thought about solving this in various ways (including as part of a more general semver checker), but this may tilt the balance in favor of adding some way to declare variance (even if it is optional).
@alexcrichton

This comment has been minimized.

Sign in to view
Copy link
Member

alexcrichton commented Sep 12, 2016

Decision at the libs team triage today was that we should revert the specialization of the structure of Zip. @bluss would you be interested in backing out just that particular piece? (taking the strategy of Fuse)

@alexcrichton alexcrichton added E-help-wanted and removed I-nominated labels Sep 12, 2016

@bluss

This comment has been minimized.

Sign in to view
Copy link
Contributor

bluss commented Sep 13, 2016

Sure. What do you mean by the Fuse strategy? Just no specialization of the data, only the methods?
@alexcrichton

This comment has been minimized.

Sign in to view
Copy link
Member

alexcrichton commented Sep 13, 2016

Ah yeah sorry I mean to just specialize the methods, not the struct representation (which we believe fixes this bug)

@brson brson assigned bluss Sep 13, 2016

@bluss bluss referenced this issue Sep 15, 2016

Merged

Remove data structure specialization for .zip() iterator #36490

Manishearth added a commit to Manishearth/rust that referenced this issue Sep 17, 2016

@Manishearth
Rollup merge of rust-lang#36490 - bluss:zip-slightly-despecialized-ed… 
…ition, r=alexcrichton

Remove data structure specialization for .zip() iterator

Go back on half the specialization, the part that changed the Zip
struct's fields themselves depending on the types of the iterators.

Previous PR: rust-lang#33090

This means that the Zip iterator will always carry two usize fields,
which are sometimes unused. If a whole for loop using a .zip() iterator is
inlined, these are simply removed and have no effect.

The same improvement for Zip of for example slice iterators remain, and
they still optimize well. However, like when the specialization of zip
was merged, the compiler is still very sensistive to the exact context.

For example this code only autovectorizes if the function is used, not
if the code in zip_sum_i32 is inserted inline where it was called:

```rust
fn zip_sum_i32(xs: &[i32], ys: &[i32]) -> i32 {
    let mut s = 0;
    for (&x, &y) in xs.iter().zip(ys) {
        s += x * y;
    }
    s
}

fn zipdot_i32_default_zip(b: &mut test::Bencher)
{
    let xs = vec![1; 1024];
    let ys = vec![1; 1024];

    b.iter(|| {
        zip_sum_i32(&xs, &ys)
    })
}
```

Include a test that checks that `Zip<T, U>` is covariant w.r.t. T and U.

Fixes rust-lang#35727
fe7a33f

bors added a commit that referenced this issue Sep 17, 2016

@bors
Auto merge of #36490 - bluss:zip-slightly-despecialized-edition, r=al… 
…excrichton

Remove data structure specialization for .zip() iterator

Go back on half the specialization, the part that changed the Zip
struct's fields themselves depending on the types of the iterators.

Previous PR: #33090

This means that the Zip iterator will always carry two usize fields,
which are sometimes unused. If a whole for loop using a .zip() iterator is
inlined, these are simply removed and have no effect.

The same improvement for Zip of for example slice iterators remain, and
they still optimize well. However, like when the specialization of zip
was merged, the compiler is still very sensistive to the exact context.

For example this code only autovectorizes if the function is used, not
if the code in zip_sum_i32 is inserted inline where it was called:

```rust
fn zip_sum_i32(xs: &[i32], ys: &[i32]) -> i32 {
    let mut s = 0;
    for (&x, &y) in xs.iter().zip(ys) {
        s += x * y;
    }
    s
}

fn zipdot_i32_default_zip(b: &mut test::Bencher)
{
    let xs = vec![1; 1024];
    let ys = vec![1; 1024];

    b.iter(|| {
        zip_sum_i32(&xs, &ys)
    })
}
```

Include a test that checks that `Zip<T, U>` is covariant w.r.t. T and U.

Fixes #35727
fb62f4d

@bors bors closed this in #36490 Sep 17, 2016

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.