chain() make collect very slow

[Stargateur]

While working on a SO question.

We was wondering if chain() would produce an acceptable speed, after some digging and benchmark, we come to the conclusion that collect() is slow because it use while let. Unfortunately, this make collect very slow, I don't really understand why but that a fact.

But we saw that for_each() (probably thank to fold()) implementation of chain() don't have this problem and produce something a lot faster.

#![feature(test)]
extern crate test;

use either::Either; // 1.5.2
use std::iter;

#[derive(Debug, Default)]
pub struct Data<X, Y> {
    head: Option<Y>,
    pairs: Vec<(X, Y)>,
    tail: Option<X>,
}

impl<X, Y> Data<X, Y> {
    pub fn iter(&self) -> impl Iterator<Item = Either<&X, &Y>> {
        let head = self.head.iter().map(Either::Right);

        let pairs = self.pairs.iter().flat_map(|(a, b)| {
            let a = iter::once(Either::Left(a));
            let b = iter::once(Either::Right(b));
            a.chain(b)
        });

        let tail = self.tail.iter().map(Either::Left);

        head.chain(pairs).chain(tail)
    }
}

#[derive(Debug)]
struct AData(usize);
#[derive(Debug)]
struct BData(usize);

#[cfg(test)]
mod tests {
    use crate::{AData, BData, Data};
    use test::Bencher; // 1.5.2

    #[bench]
    fn test_for_each(b: &mut Bencher) {
        b.iter(|| {
            let data = Data {
                head: Some(BData(84)),
                pairs: std::iter::repeat_with(|| (AData(42), BData(84)))
                    .take(20998)
                    .collect(),
                tail: Some(AData(42)),
            };

            let mut data_bis = Vec::with_capacity(21000);
            data.iter().for_each(|x| data_bis.push(x));
        });
    }

    #[bench]
    fn test_collect(b: &mut Bencher) {
        b.iter(|| {
            let data = Data {
                head: Some(BData(84)),
                pairs: std::iter::repeat_with(|| (AData(42), BData(84)))
                    .take(20998)
                    .collect(),
                tail: Some(AData(42)),
            };

            let _: Vec<_> = data.iter().collect();
        });
    }
}

test tests::test_collect  ... bench:   1,682,529 ns/iter (+/- 2,157,023)
test tests::test_for_each ... bench:     609,031 ns/iter (+/- 750,944)

So, should we change implementation of collect to use for_each() ? Note that a for loop doesn't solve the problem. For this to be optimized we need to use for_each().

[Centril]

cc @scottmcm

[scottmcm]

Sounds like a good change; please make a PR, @Stargateur! Let me know if you need any assistance.

I don't really understand why but that a fact.

There are some resources about why linked from #45595

[Stargateur]

I need to search a lot more because I find simple case where collect() look much better, but in some case that the exact opposite. As it's a core function I do not want to change anything if I'm not sure this is better on most case.

I find some bench test for vector, so I will try to add some and see if for_each() really improve thing. I'm not sure it will:

    fn extend_desugared<I: Iterator<Item = T>>(&mut self, iterator: I) {
        // This is the case for a general iterator.
        //
        // This function should be the moral equivalent of:
        //
        //      for item in iterator {
        //          self.push(item);
        //      }

        let (lower, upper) = iterator.size_hint();
        if let Some(upper) = upper {
            self.reserve(upper); // why not ?
        }
        else {
            self.reserve(lower)
        }

        // We use `for_each()` that should allow more efficient code
        iterator.for_each(|element| {
            let len = self.len();
            if len == self.capacity() {
                self.reserve(1);
            }
            unsafe {
                ptr::write(self.get_unchecked_mut(len), element);
                // NB can't overflow since we would have had to alloc the address space
                self.set_len(len + 1);
            }
        })
    }

The main difference (actuel code) is that we can't anymore check the lower bound of the iterator in the loop, also I wonder why not take the upper bound if it exist. Well, I suppose this is for saving memory but I don't know if it's make sense because reserve already take more memory in a lot of case. So why not just hint what should be the max ?

Also, Rust take like forever to compile on my PC, this going to take a while to do my search.

[tesuji]

You could try https://internals.rust-lang.org/t/gcc-compile-farm-for-rustc/9511, but it will take
a while (half a month) to receive a confirm mail from the build farm moderators.

[Stargateur]

#50481, well better give up for now, I can't wait 10 hours everytime to compile rust for each little change.

[hbina]

Here's my bench result

hbina085@akarin:~/Documents/issue_63340_chain_bench$ cargo bench
   Compiling issue_63340_chain_bench v0.1.0 (/home/hbina085/Documents/issue_63340_chain_bench)
    Finished bench [optimized] target(s) in 0.77s
     Running target/release/deps/issue_63340_chain_bench-51e8cb2b35e76763

running 2 tests
test tests::test_collect  ... bench:     206,178 ns/iter (+/- 213,147)
test tests::test_for_each ... bench:     216,507 ns/iter (+/- 6,650)

test result: ok. 0 passed; 0 failed; 0 ignored; 2 measured; 0 filtered out

     Running target/release/deps/issue_63340_chain_bench-d3cab5b8c9523cd3

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

While the average performance is about the same, the variance is still larger. Another run...

hbina085@akarin:~/Documents/issue_63340_chain_bench$ cargo bench
    Finished bench [optimized] target(s) in 0.01s
     Running target/release/deps/issue_63340_chain_bench-51e8cb2b35e76763

running 2 tests
test tests::test_collect  ... bench:     186,086 ns/iter (+/- 13,684)
test tests::test_for_each ... bench:     223,619 ns/iter (+/- 57,158)

test result: ok. 0 passed; 0 failed; 0 ignored; 2 measured; 0 filtered out

     Running target/release/deps/issue_63340_chain_bench-d3cab5b8c9523cd3

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

I don't even know anymore...

[hbina]

@rustbot claim

[csmoe]

@hbina cargo bench'd on my machine, ".for_each() faster than .collect()" still holds:

running 2 tests
test tests::test_collect  ... bench:     410,982 ns/iter (+/- 4,466)
test tests::test_for_each ... bench:     343,862 ns/iter (+/- 1,747)

test result: ok. 0 passed; 0 failed; 0 ignored; 2 measured; 0 filtered out

running 2 tests
test tests::test_collect  ... bench:     410,948 ns/iter (+/- 2,077)
test tests::test_for_each ... bench:     331,491 ns/iter (+/- 1,559)

[mati865]

It could be due to different performance characteristics between different microarchitectures (especially AMD vs Intel). Although variance in hbina results is quite high.