Skip to content

Instantly share code, notes, and snippets.

@overvenus

overvenus/bench_map.rs

Created January 23, 2017 10:45
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save overvenus/a6db993e71a4fcb22f63329320a8fe19 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save overvenus/a6db993e71a4fcb22f63329320a8fe19 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. overvenus created this gist Jan 23, 2017.
    189 changes: 189 additions & 0 deletions bench_map.rs
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,189 @@
    #![feature(test)]

    extern crate test;
    extern crate fnv;
    extern crate rand;

    use std::collections::{BTreeMap, HashMap};
    use std::cell::RefCell;

    use test::Bencher;
    use fnv::FnvBuildHasher;
    use rand::{Rng, ChaChaRng};

    fn rand_u64<T: Rng>(source: &mut T) -> u64 {
    source.next_u64()
    }

    macro_rules! bench_small_map {
    ($NAME:ident, $MAP:expr, $SIZE:expr) => {

    #[bench]
    fn $NAME(b: &mut Bencher) {
    let mut source = ChaChaRng::new_unseeded();

    let size = $SIZE;
    let mut map = $MAP;
    let mut keys = Vec::with_capacity(size);
    for _ in 0..size {
    let key = rand_u64(&mut source);
    map.insert(key, 0);
    keys.push(key);
    }

    let new_keys = vec![rand_u64(&mut source), rand_u64(&mut source)];
    let mut bench_map = RefCell::new(map);

    b.iter(|| {
    // insert.
    for k in &new_keys {
    bench_map.get_mut().insert(*k, 0);
    }

    // query.
    for k in &keys {
    bench_map.get_mut().get(k);
    }

    // remove.
    for k in keys.iter().take(2) {
    bench_map.get_mut().remove(k);
    }
    })
    }

    }
    }

    // querying a small Map (normally 3 or 5 entries) and with little inserts/remove;
    bench_small_map!{bench_btreemap_small_set, BTreeMap::new(), 5}
    bench_small_map!{bench_sip_hashmap_small_set, HashMap::new(), 5}
    bench_small_map!{
    bench_fnv_hashmap_small_set,
    {
    let fnv = FnvBuildHasher::default();
    HashMap::with_hasher(fnv)
    },
    5
    }

    bench_small_map!{bench_btreemap_small_set_12, BTreeMap::new(), 12}
    bench_small_map!{bench_sip_hashmap_small_set_12, HashMap::new(), 12}
    bench_small_map!{
    bench_fnv_hashmap_small_set_12,
    {
    let fnv = FnvBuildHasher::default();
    HashMap::with_hasher(fnv)
    },
    12
    }

    macro_rules! bench_raw_small_map {
    ($NAME:ident, $T:ty, $SIZE:expr) => {

    #[bench]
    fn $NAME(b: &mut Bencher) {
    let mut source = ChaChaRng::new_unseeded();

    let keys: Vec<_> = (0..$SIZE).into_iter().map(|_| rand_u64(&mut source)).collect();
    b.iter(|| {
    let mut bench_map: $T = Default::default();
    // insert.
    for k in &keys {
    bench_map.insert(*k, 0);
    }

    // query.
    for k in &keys {
    bench_map.get(k);
    }

    // remove.
    for k in keys.iter().take(2) {
    bench_map.remove(k);
    }
    })
    }

    }
    }

    // querying a small Map (normally 3 or 5 entries) and with little inserts/remove;
    bench_raw_small_map!{bench_btreemap_raw_small_set, BTreeMap<u64, u64>, 5}
    bench_raw_small_map!{bench_sip_hashmap_raw_small_set, HashMap<u64, u64>, 5}
    bench_raw_small_map!{
    bench_fnv_hashmap_raw_small_set,
    HashMap<u64, u64, FnvBuildHasher>,
    5
    }

    bench_raw_small_map!{bench_btreemap_raw_small_set_12, BTreeMap<u64, u64>, 12}
    bench_raw_small_map!{bench_sip_hashmap_raw_small_set_12, HashMap<u64, u64>, 12}
    bench_raw_small_map!{
    bench_fnv_hashmap_raw_small_set_12,
    HashMap<u64, u64, FnvBuildHasher>,
    12
    }

    macro_rules! bench_large_map {
    ($NAME:ident, $MAP:expr) => {

    #[bench]
    fn $NAME(b: &mut Bencher) {
    let mut source = ChaChaRng::new_unseeded();

    let size = 12000;
    let mut map = $MAP;
    let mut keys = Vec::with_capacity(size);
    for _ in 0..size {
    let key = rand_u64(&mut source);
    map.insert(key, 0);
    keys.push(key);
    }

    let per_loop_count = 3000;
    let mut keys = keys.iter().cycle();
    let mut bench_map = RefCell::new(map);

    b.iter(|| {
    for _ in 0..5 {
    // query.
    let mut count = 0;
    for k in keys.by_ref() {
    bench_map.get_mut().get(k);

    count += 1;
    if count == per_loop_count {
    break;
    }
    }

    // update.
    count = 0;
    for k in keys.by_ref() {
    if let Some(v) = bench_map.get_mut().get_mut(k) {
    *v += 1;
    }

    count += 1;
    if count == per_loop_count {
    break;
    }
    }
    }
    })
    }

    }
    }

    // updating and querying a large map (may contains 10000+ entries) very frequently.
    bench_large_map!{bench_btreemap_large_set, BTreeMap::new()}
    bench_large_map!{bench_sip_hashmap_large_set, HashMap::new()}
    bench_large_map!{
    bench_fnv_hashmap_large_set,
    {
    let fnv = FnvBuildHasher::default();
    HashMap::with_hasher(fnv)
    }
    }