Create a gist now

Instantly share code, notes, and snippets.

@gifnksm /.gitignore
Last active May 31, 2016

Rust array index bounds check benchmark
#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;
}
extern crate gcc;
fn main() {
gcc::Config::new()
.compiler("clang")
.file("access.c")
.compile("libaccess.a");
}
[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)",
]
[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"
#![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()) })
})
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment