Rust array index bounds check benchmark

.gitignore

target

access.c

#include <stddef.h>
#include <stdint.h>

uint64_t direct_c(const uint64_t *arr, size_t len)
{
    uint64_t sum =  0;
    for (size_t i = 0; i < len; i++) {
        sum += arr[i];
    }
    return sum;
}

uint64_t indirect_c(const uint64_t *arr, const size_t *idx, size_t idx_len)
{
    uint64_t sum =  0;
    for (size_t i = 0; i < idx_len; i++) {
        sum += arr[idx[i]];
    }
    return sum;
}

build.rs

extern crate gcc;

fn main() {
    gcc::Config::new()
        .compiler("clang")
        .file("access.c")
        .compile("libaccess.a");
}

Cargo.lock

[root]
name = "array-bench"
version = "0.1.0"
dependencies = [
 "gcc 0.3.28 (registry+https://github.com/rust-lang/crates.io-index)",
 "lazy_static 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)",
 "libc 0.2.11 (registry+https://github.com/rust-lang/crates.io-index)",
 "rand 0.3.14 (registry+https://github.com/rust-lang/crates.io-index)",
]

[[package]]
name = "gcc"
version = "0.3.28"
source = "registry+https://github.com/rust-lang/crates.io-index"

[[package]]
name = "lazy_static"
version = "0.2.1"
source = "registry+https://github.com/rust-lang/crates.io-index"

[[package]]
name = "libc"
version = "0.2.11"
source = "registry+https://github.com/rust-lang/crates.io-index"

[[package]]
name = "rand"
version = "0.3.14"
source = "registry+https://github.com/rust-lang/crates.io-index"
dependencies = [
 "libc 0.2.11 (registry+https://github.com/rust-lang/crates.io-index)",
]

Cargo.toml

[package]
name = "array-bench"
version = "0.1.0"
authors = ["gifnksm <makoto.nksm+github@gmail.com>"]
build = "build.rs"

[[bin]]
name = "array-bench"
path = "main.rs"

[dependencies]
rand = "0.3"
libc = "0.2"

[build-dependencies]
gcc = "0.3"

[dev-dependencies]
lazy_static = "0.2"

main.rs

#![feature(test)]

extern crate libc;
extern crate rand;
extern crate test;

#[cfg(test)]
#[macro_use]
extern crate lazy_static;

use std::env;
use std::time::{Duration, Instant};

use rand::Rng;

fn gen_array(len: usize) -> Vec<u64> {
    rand::thread_rng().gen_iter::<u8>().map(|n| n as u64).take(len).collect()
}

#[inline(never)]
pub fn direct_index(arr: &[u64]) -> u64 {
    let mut sum = 0;
    for i in 0..arr.len() {
        sum += arr[i];
    }
    sum
}

#[inline(never)]
pub fn direct_index_len(arr: &[u64], len: usize) -> u64 {
    let mut sum = 0;
    for i in 0..len {
        sum += arr[i];
    }
    sum
}

#[inline(never)]
pub fn direct_iter(arr: &[u64]) -> u64 {
    let mut sum = 0;
    for &n in arr {
        sum += n;
    }
    sum
}

extern "C" {
    pub fn direct_c(arr: *const libc::uint64_t, len: libc::size_t) -> libc::uint64_t;
}


#[inline(never)]
fn indirect_iter(arr: &[u64], idx: &[usize]) -> u64 {
    let mut sum = 0;
    for &i in idx {
        sum += arr[i];
    }
    sum
}

#[inline(never)]
unsafe fn indirect_iter_uc(arr: &[u64], idx: &[usize]) -> u64 {
    let mut sum = 0;
    for &i in idx {
        sum += *arr.get_unchecked(i);
    }
    sum
}

extern "C" {
    fn indirect_c(arr: *const libc::uint64_t,
                  idx: *const libc::size_t,
                  idx_len: libc::size_t)
                  -> libc::uint64_t;
}

fn main() {
    let args = env::args().collect::<Vec<_>>();
    let n_elem = args[1].parse().unwrap();
    let n_try = args[2].parse().unwrap();

    let arr = gen_array(n_elem);

    benchmark("D index", n_try, || direct_index(&arr));
    benchmark("D index_len", n_try, || direct_index_len(&arr, arr.len()));
    benchmark("D iter", n_try, || direct_iter(&arr));
    benchmark("D c",
              n_try,
              || unsafe { direct_c(arr.as_ptr(), arr.len()) });

    let mut idx = (0..n_elem).collect::<Vec<_>>();
    benchmark("I iter", n_try, || indirect_iter(&arr, &idx));
    benchmark("I iter_uc",
              n_try,
              || unsafe { indirect_iter_uc(&arr, &idx) });
    benchmark("I c",
              n_try,
              || unsafe { indirect_c(arr.as_ptr(), idx.as_ptr(), idx.len()) });

    rand::thread_rng().shuffle(&mut idx);
    benchmark("R iter", n_try, || indirect_iter(&arr, &idx));
    benchmark("R iter_uc",
              n_try,
              || unsafe { indirect_iter_uc(&arr, &idx) });
    benchmark("R c",
              n_try,
              || unsafe { indirect_c(arr.as_ptr(), idx.as_ptr(), idx.len()) });
}

fn benchmark<F>(name: &str, n_try: u32, mut f: F)
    where F: FnMut() -> u64
{
    let mut total = Duration::new(0, 0);
    test::black_box(f());
    for _ in 0..n_try {
        let start = Instant::now();
        test::black_box(f());
        total += start.elapsed();
    }
    let dur = total / n_try;
    println!("{:20}: {:3}.{:09}", name, dur.as_secs(), dur.subsec_nanos());
}

#[cfg(test)]
mod tests {
    use super::*;
    use rand::{self, Rng};
    use test::{self, Bencher};

    const N_ELEM: usize = 100000;

    lazy_static! {
        static ref ARRAY: Vec<u64> = super::gen_array(N_ELEM);
        static ref SEQ_INDEX: Vec<usize> = (0..N_ELEM).collect();
        static ref RAND_INDEX: Vec<usize> = {
            let mut idx = (0..N_ELEM).collect::<Vec<_>>();
            rand::thread_rng().shuffle(&mut idx);
            idx
        };
    }

    #[bench]
    fn D_index(b: &mut Bencher) {
        let array = &*ARRAY;
        b.iter(|| test::black_box(super::direct_index(array)));
    }

    #[bench]
    fn D_index_len(b: &mut Bencher) {
        let array = &*ARRAY;
        b.iter(|| test::black_box(super::direct_index_len(&array, array.len())));
    }

    #[bench]
    fn D_iter(b: &mut Bencher) {
        let array = &*ARRAY;
        b.iter(|| test::black_box(super::direct_iter(&array)));
    }

    #[bench]
    fn D_c(b: &mut Bencher) {
        let array = &*ARRAY;
        b.iter(|| test::black_box(unsafe { direct_c(array.as_ptr(), array.len()) }));
    }

    #[bench]
    fn I_iter(b: &mut Bencher) {
        let array = &*ARRAY;
        let idx = &*SEQ_INDEX;
        b.iter(|| test::black_box(super::indirect_iter(&array, &idx)))
    }

    #[bench]
    fn I_iter_uc(b: &mut Bencher) {
        let array = &*ARRAY;
        let idx = &*SEQ_INDEX;
        b.iter(|| test::black_box(unsafe { super::indirect_iter_uc(&array, &idx) }))
    }

    #[bench]
    fn I_c(b: &mut Bencher) {
        let array = &*ARRAY;
        let idx = &*SEQ_INDEX;
        b.iter(|| {
            test::black_box(unsafe { super::indirect_c(array.as_ptr(), idx.as_ptr(), idx.len()) })
        })
    }

    #[bench]
    fn R_iter(b: &mut Bencher) {
        let array = &*ARRAY;
        let idx = &*RAND_INDEX;
        b.iter(|| test::black_box(super::indirect_iter(&array, &idx)))
    }

    #[bench]
    fn R_iter_uc(b: &mut Bencher) {
        let array = &*ARRAY;
        let idx = &*RAND_INDEX;
        b.iter(|| test::black_box(unsafe { super::indirect_iter_uc(&array, &idx) }))
    }

    #[bench]
    fn R_c(b: &mut Bencher) {
        let array = &*ARRAY;
        let idx = &*RAND_INDEX;
        b.iter(|| {
            test::black_box(unsafe { super::indirect_c(array.as_ptr(), idx.as_ptr(), idx.len()) })
        })
    }
}