#![feature(test)]
#![cfg_attr(feature = "cargo-clippy", allow(unreadable_literal))]
extern crate im;
extern crate rand;
extern crate test;
use rand::{weak_rng, Rng};
use std::iter::FromIterator;
use test::Bencher;
use im::ordmap::OrdMap;
fn random_keys(size: usize) -> Vec<i64> {
let mut gen = weak_rng();
let mut set = Vec::new();
while set.len() < size {
let next = gen.gen::<i64>() % 10000;
if !set.contains(&next) {
set.push(next);
}
}
set
}
fn reorder<A: Copy>(vec: &[A]) -> Vec<A> {
let mut gen = weak_rng();
let mut set = vec.to_owned();
let mut out = Vec::new();
while !set.is_empty() {
let i = gen.gen::<usize>() % set.len();
let v = set.remove(i);
out.push(v)
}
out
}
fn ordmap_lookup_n(size: usize, b: &mut Bencher) {
let keys = random_keys(size);
let order = reorder(&keys);
let m = OrdMap::from_iter(keys.into_iter().map(|i| (i, 1)));
b.iter(|| {
for i in &order {
m.get(i);
}
})
}
#[bench]
fn ordmap_lookup_10(b: &mut Bencher) {
ordmap_lookup_n(10, b)
}
#[bench]
fn ordmap_lookup_100(b: &mut Bencher) {
ordmap_lookup_n(100, b)
}
#[bench]
fn ordmap_lookup_1000(b: &mut Bencher) {
ordmap_lookup_n(1000, b)
}
fn ordmap_insert_n(size: usize, b: &mut Bencher) {
let keys = random_keys(size);
b.iter(|| {
let mut m = OrdMap::new();
for i in keys.clone() {
m = m.insert(i, i)
}
})
}
#[bench]
fn ordmap_insert_10(b: &mut Bencher) {
ordmap_insert_n(10, b)
}
#[bench]
fn ordmap_insert_100(b: &mut Bencher) {
ordmap_insert_n(100, b)
}
#[bench]
fn ordmap_insert_1000(b: &mut Bencher) {
ordmap_insert_n(1000, b)
}
fn ordmap_insert_mut_n(size: usize, b: &mut Bencher) {
let keys = random_keys(size);
b.iter(|| {
let mut m = OrdMap::new();
for i in keys.clone() {
m.insert_mut(i, i)
}
})
}
#[bench]
fn ordmap_insert_mut_10(b: &mut Bencher) {
ordmap_insert_mut_n(10, b)
}
#[bench]
fn ordmap_insert_mut_100(b: &mut Bencher) {
ordmap_insert_mut_n(100, b)
}
#[bench]
fn ordmap_insert_mut_1000(b: &mut Bencher) {
ordmap_insert_mut_n(1000, b)
}
fn ordmap_remove_n(size: usize, b: &mut Bencher) {
let keys = random_keys(size);
let order = reorder(&keys);
let map = OrdMap::from_iter(keys.into_iter().map(|i| (i, i)));
b.iter(|| {
let mut m = map.clone();
for i in &order {
m = m.remove(i)
}
})
}
#[bench]
fn ordmap_remove_10(b: &mut Bencher) {
ordmap_remove_n(10, b)
}
#[bench]
fn ordmap_remove_100(b: &mut Bencher) {
ordmap_remove_n(100, b)
}
#[bench]
fn ordmap_remove_1000(b: &mut Bencher) {
ordmap_remove_n(1000, b)
}
fn ordmap_remove_mut_n(size: usize, b: &mut Bencher) {
let keys = random_keys(size);
let order = reorder(&keys);
let map: OrdMap<i64, i64> = OrdMap::from_iter(keys.into_iter().map(|i| (i, i)));
b.iter(|| {
let mut m = map.clone();
for i in &order {
m.remove_mut(i)
}
})
}
#[bench]
fn ordmap_remove_mut_10(b: &mut Bencher) {
ordmap_remove_mut_n(10, b)
}
#[bench]
fn ordmap_remove_mut_100(b: &mut Bencher) {
ordmap_remove_mut_n(100, b)
}
#[bench]
fn ordmap_remove_mut_1000(b: &mut Bencher) {
ordmap_remove_mut_n(1000, b)
}
#[bench]
fn ordmap_remove_min(b: &mut Bencher) {
let map = OrdMap::from_iter((0..1000).into_iter().map(|i| (i, i)));
b.iter(|| {
let mut m = map.clone();
assert!(!m.is_empty());
for _ in 0..1000 {
m = m.delete_min()
}
assert!(m.is_empty())
})
}
#[bench]
fn ordmap_remove_max(b: &mut Bencher) {
let map = OrdMap::from_iter((0..1000).into_iter().map(|i| (i, i)));
b.iter(|| {
let mut m = map.clone();
assert!(!m.is_empty());
for _ in 0..1000 {
m = m.delete_max()
}
assert!(m.is_empty())
})
}
fn ordmap_insert_once_n(size: usize, b: &mut Bencher) {
let mut keys = random_keys(size + 1);
let key = keys.pop().unwrap();
let map = OrdMap::from_iter(keys.into_iter().map(|i| (i, i)));
b.iter(|| map.insert(key, key))
}
#[bench]
fn ordmap_insert_once_10(b: &mut Bencher) {
ordmap_insert_once_n(10, b)
}
#[bench]
fn ordmap_insert_once_100(b: &mut Bencher) {
ordmap_insert_once_n(100, b)
}
#[bench]
fn ordmap_insert_once_1000(b: &mut Bencher) {
ordmap_insert_once_n(1000, b)
}
#[bench]
fn ordmap_insert_once_10000(b: &mut Bencher) {
ordmap_insert_once_n(10000, b)
}
fn ordmap_remove_once_n(size: usize, b: &mut Bencher) {
let keys = random_keys(size + 1);
let key = keys[0];
let map = OrdMap::from_iter(keys.into_iter().map(|i| (i, i)));
b.iter(|| map.remove(&key))
}
#[bench]
fn ordmap_remove_once_10(b: &mut Bencher) {
ordmap_remove_once_n(10, b)
}
#[bench]
fn ordmap_remove_once_100(b: &mut Bencher) {
ordmap_remove_once_n(100, b)
}
#[bench]
fn ordmap_remove_once_1000(b: &mut Bencher) {
ordmap_remove_once_n(1000, b)
}
#[bench]
fn ordmap_remove_once_10000(b: &mut Bencher) {
ordmap_remove_once_n(10000, b)
}
fn ordmap_lookup_once_n(size: usize, b: &mut Bencher) {
let keys = random_keys(size + 1);
let key = keys[0];
let map = OrdMap::from_iter(keys.into_iter().map(|i| (i, i)));
b.iter(|| map.get(&key))
}
#[bench]
fn ordmap_lookup_once_10(b: &mut Bencher) {
ordmap_lookup_once_n(10, b)
}
#[bench]
fn ordmap_lookup_once_100(b: &mut Bencher) {
ordmap_lookup_once_n(100, b)
}
#[bench]
fn ordmap_lookup_once_1000(b: &mut Bencher) {
ordmap_lookup_once_n(1000, b)
}
#[bench]
fn ordmap_lookup_once_10000(b: &mut Bencher) {
ordmap_lookup_once_n(10000, b)
}