chain_find.rs

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

// Copy of the Chain adapter from libcore, with an added impl for `find`.

#[derive(Clone, Debug)]
pub struct Chain<A, B> {
    a: A,
    b: B,
    state: ChainState,
}

#[derive(Clone, Debug)]
enum ChainState {
    Both,
    Front,
    Back,
}

impl<A, B> Iterator for Chain<A, B> where A: Iterator, B: Iterator<Item = A::Item>
{
    type Item = A::Item;

    #[inline]
    fn next(&mut self) -> Option<A::Item> {
        match self.state {
            ChainState::Both => match self.a.next() {
                elt @ Some(..) => elt,
                None => {
                    self.state = ChainState::Back;
                    self.b.next()
                }
            },
            ChainState::Front => self.a.next(),
            ChainState::Back => self.b.next(),
        }
    }

    #[inline]
    fn find<P>(&mut self, mut predicate: P) -> Option<Self::Item> where
        Self: Sized,
        P: FnMut(&Self::Item) -> bool,
    {
        match self.state {
            ChainState::Both => match self.a.find(&mut predicate) {
                elt @ Some(..) => elt,
                None => {
                    self.state = ChainState::Back;
                    self.b.find(predicate)
                }
            },
            ChainState::Front => self.a.find(predicate),
            ChainState::Back => self.b.find(predicate),
        }
    }
}

fn new_chain<I, U>(selfi: I, other: U) -> Chain<I, U::IntoIter> where
    I: Iterator, U: IntoIterator<Item=I::Item>,
{
    Chain { a: selfi, b: other.into_iter(), state: ChainState::Both }
}

#[bench]
fn with_old_chain(b: &mut test::Bencher) {
    let d0 = (2..100).collect::<Vec<_>>();
    let d1 = (0..2).collect::<Vec<_>>();
    b.iter(|| d0.iter().chain(d1.iter()).find(|&&i| i == 1).unwrap());
}

#[bench]
fn with_new_chain(b: &mut test::Bencher) {
    let d0 = (2..100).collect::<Vec<_>>();
    let d1 = (0..2).collect::<Vec<_>>();
    b.iter(|| new_chain(d0.iter(), d1.iter()).find(|&&i| i == 1).unwrap());
}

#[bench]
fn without_chain(b: &mut test::Bencher) {
    let d0 = (2..100).collect::<Vec<_>>();
    let d1 = (0..2).collect::<Vec<_>>();
    b.iter(|| d0.iter().find(|&&i| i == 1).or_else(|| d1.iter().find(|&&i| i == 1)).unwrap());
}

output

running 3 tests
test with_new_chain ... bench:          55 ns/iter (+/- 6)
test with_old_chain ... bench:         105 ns/iter (+/- 10)
test without_chain  ... bench:          55 ns/iter (+/- 2)