Update Iterator::eq implementation for better performance

[bluss]

The itertools equal function expresses the same functionality as Iterator::eq in a way that compiles better / performs better. Import their implementation into libstd, also see if other iterator comparison functions can be improved.

The problem could be that the libstd code is using match on a tuple of options.

[bluss]

The itertools code is not the end station of course, there could be improvements on top of that.

[mister-walter]

I'd like to take a shot at this - I'll go check out Gitter when I have time later today (I'm currently on JST)

[lezgomatt]

hey @mister-walter, are you still interested in working on this? If not, I'd like to give this issue a try 😃

[bluss]

Feel free to find me on irc or here

[mister-walter]

I'm really sorry about that, I got super caught up in work and this fell by the wayside... Matt, feel free to take this up!

…

On Oct 1, 2017 5:00 PM, "Matt" ***@***.***> wrote: hey @mister-walter <https://github.com/mister-walter>, are you still interested in working on this? If not, I'd like to give this issue a try 😃 — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#44729 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ABysYa9eVqtCXnK1dE4gj3lcp2pY_ZYBks5sn0ahgaJpZM4PeiOM> .

[lezgomatt]

Awesome, thanks!

I tried a few approaches out and it seems that the matching on the tuples does indeed cause slower code to be generated (best on some quick benchmarking).

The current implementation does the ff:

loop {
    match (self.next(), other.next()) {
        (None, None) => return true,
        (None, _) | (_, None) => return false,
        (Some(x), Some(y)) => if x != y { return false },
    }
}

Modifying the code to separate the matching resulted in some nice gains:

loop {
    match self.next() {
        None => return other.next().is_none(),
        Some(x) => match other.next() {
            None => return false,
            Some(y) => if x != y { return false },
        },
    };
}

Alternatively (to reduce nesting):

loop {
    let x = match self.next() {
        None => return other.next().is_none(),
        Some(val) => val,
    };

    let y = match other.next() {
        None => return false,
        Some(val) => val,
    };

    if x != y {
        return false;
    }
}

I haven't taken a good look at the MIR generated though. I also tested it out on the other comparison functions and noticed similar gains. I'll try to take a deeper look at the code generated soon.

[bluss]

Oh nice, the new versions are side-effect compatible as well right? self.next() and other.next() are called exactly as many times as before.