performance of all_equal

[RSabet]

Here is a comparison of itertools::all_equal with two alternatives for a vector consisting of 5_000_000 zeroes followed by 5_000_000 ones on rust playground:

• using itertools::all_equal: 607 msecs
• using any: 487 msecs
• using a simple for loop: 536 msecs

i would love if all_qual was as fast

playground

[bluss]

@RSabet That's a very reasonable concern. Note that we must use Release mode compiles to make meaningful performance comparisons. I'm not sure you'll have a different conclusion with that, but you'll have faster timings across the board, and the code will need to be fixed to not optimize out some parts of the benchmark.

[RSabet]

You are right, trying to hide the values in the vector from the optimizer one can use:

let mut v: Vec<i32> = (0..5_000_000).map(|_| rng.gen_range(1, 2)).collect();
v.extend((0..5_000_000).map(|_| rng.gen_range(2, 3)) .collect::<Vec<i32>>());

again 5_000_000 ones followed by 5_000_000 twos

and now in release mode:

• using itertools::all_equal: 5 msecs
• using any: 3 msecs
• using a simple for loop: 0 msecs (guess the compiler still found a way to optimize)

playground

[timvermeulen]

all_equal's implementation is currently suboptimal:

fn all_equal(&mut self) -> bool
    where Self::Item: PartialEq,
{
    self.dedup().nth(1).is_none()
}

This doesn't necessarily iterate the entire iterator, but in @RSabet's example code, it does evaluate all the 2s.

[Philippe-Cholet]

Solved by #342.