benching inside-out iterators

bench-imperative-iterator.rs

#![feature(test)]

#[derive(Clone)]
struct Iterate<T, F> {
    cur: T,
    func: F,
}

impl<T, F> Iterator for Iterate<T, F>
    where F: FnMut(T) -> T,
          T: Clone
{
    type Item = T;
    fn next(&mut self) -> Option<Self::Item> {
        let next = (self.func)(self.cur.clone());
        Some(::std::mem::replace(&mut self.cur, next))
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        (usize::max_value(), None)
    }
}
fn iterate<T, F: FnMut(T) -> T>(x: T, f: F) -> Iterate<T, F> {
    return Iterate { cur: x, func: f };
}

extern crate test;
use test::Bencher;

//=================
//  THE SPECIMENS
//=================

fn each_range<F>(center: f64, radius: f64, mut cb: F)
    where F: FnMut((f64, f64))
{
    // crosses the left boundary
    if center - radius < 0.0 {
        cb((center - radius + 1.0, 1.0));
        cb((0.0, center + radius));

        // crosses the right boundary
    } else if center + radius > 1.0 {
        cb((center - radius, 1.0));
        cb((0.0, center + radius - 1.0));

    } else {
        cb((center - radius, center + radius));
    }
}

fn ranges(center: f64, radius: f64) -> Vec<(f64, f64)> {
    // crosses the left boundary
    if center - radius < 0.0 {
        vec![
            (center - radius + 1.0, 1.0),
            (0.0, center + radius),
        ]

        // crosses the right boundary
    } else if center + radius > 1.0 {
        vec![
            (center - radius, 1.0),
            (0.0, center + radius - 1.0),
        ]

    } else {
        vec![
            (center - radius, center + radius),
        ]
    }
}

fn ranges_diehard
    (center: f64,
     radius: f64)
     -> ::std::iter::Chain<::std::iter::Once<(f64, f64)>, std::option::IntoIter<(f64, f64)>> {
    // crosses the left boundary
    if center - radius < 0.0 {
        ::std::iter::once((center - radius + 1.0, 1.0))
            .chain(Some((0.0, center + radius)).into_iter())

        // crosses the right boundary
    } else if center + radius > 1.0 {
        ::std::iter::once((center - radius, 1.0))
            .chain(Some((0.0, center + radius - 1.0)).into_iter())

    } else {
        ::std::iter::once((center - radius, center + radius)).chain(None.into_iter())
    }
}

//=====================
//  THE BENCH WRAPPERS
//=====================

const N: usize = 1_000_000;
const STEP: f64 = 0.1849827852;
const RADIUS: f64 = 0.002;

#[bench]
fn bench_imperative_iterator(b: &mut Bencher) {
    b.iter(|| {
        let iter = iterate(0., |x| (x + STEP).fract()).take(N);
        let mut out = Vec::with_capacity(2 * N);

        // This is the only line that differs between the tests.
        for x in iter {
            each_range(x, RADIUS, |e| out.push(e));
        }

        ::test::black_box(out);
    });
}

#[bench]
fn bench_flat_map_vec(b: &mut Bencher) {
    b.iter(|| {
        let iter = iterate(0., |x| (x + STEP).fract()).take(N);
        let mut out = Vec::with_capacity(2 * N);

        out.extend(iter.flat_map(|x| ranges(x, RADIUS)));

        ::test::black_box(out);
    });
}

#[bench]
fn bench_flat_map_stack(b: &mut Bencher) {
    b.iter(|| {
        let iter = iterate(0., |x| (x + STEP).fract()).take(N);
        let mut out = Vec::with_capacity(2 * N);

        out.extend(iter.flat_map(|x| ranges_diehard(x, RADIUS)));

        ::test::black_box(out);
    });
}