step() slowness

[palacaze]

I encountered a case where the step() method leads to incredibly slow code:

#![feature(step_by)]
extern crate time;
use time::PreciseTime;
extern crate itertools;
use itertools::Itertools;

fn calc2(n: usize) -> Vec<usize> {
    let mut t = vec![0; n] ;
    for i in 2..n {
        if t[i] == 0 {
            t[i] = i - 1;
            for j in (2*i..n).step_by(i) {
                if t[j] == 0 {
                    t[j] = j;
                }
                t[j] = t[j] * (i - 1) / i;
            }
        }
    }
    t
}

fn calc1(n: usize) -> Vec<usize> {
    let mut t = vec![0; n] ;
    for i in 2..n {
        if t[i] == 0 {
            t[i] = i - 1;
            for j in (2*i..n).step(i) {
                if t[j] == 0 {
                    t[j] = j;
                }
                t[j] = t[j] * (i - 1) / i;
            }
        }
    }
    t
}

fn main() {
    let nb = 100_001;
    let start = PreciseTime::now();
    let s = calc2(nb).into_iter().fold(0, |a, c| a + c);
    println!("sum (step_by): {} {:?}", s, start.to(PreciseTime::now()));

    let start = PreciseTime::now();
    let s = calc1(nb).into_iter().fold(0, |a, c| a + c);
    println!("sum (step): {} {:?}", s, start.to(PreciseTime::now()));
}

Replacing step() with the unstable step_by() gives a 100 fold improvement in execution time, as can be observed on the playground here.

[bluss]

It's not really surprising, .step() is written for general iterators and uses .fuse() among other things (whose performance impediment is well known).

[palacaze]

Thanks for the explanation. I see now that step_by() is only implemented for ranges.
Should the performance implications be mentioned in the documentation, as a few iterators, such as interleave(), make use of Fuse internally?

[bluss]

It's not just fuse, it's a lot of stuff that needs to be covered. Every adaptor could have its own performance story explained.

Step could possibly be improved with specialization (also fuse-related specialization).

[bluss]

One prerequisite for making the best step iterator for slices (like Stride/StrideMut) is to have arith_offset as a stable function. Then specialization to let us do interesting specializations in itertools itself.

[bluss]

std has Iterator::step_by now. We can deprecate step() when it's stable.

[bluss]

Step has been deprecated in itertools 0.8