[rustc.git] / vendor / smallvec / benches / bench.rs

#![feature(test)]
#![allow(deprecated)]

#[macro_use]
extern crate smallvec;
extern crate test;

use self::test::Bencher;
use smallvec::{ExtendFromSlice, SmallVec};

const VEC_SIZE: usize = 16;
const SPILLED_SIZE: usize = 100;

trait Vector<T>: for<'a> From<&'a [T]> + Extend<T> + ExtendFromSlice<T> {
    fn new() -> Self;
    fn push(&mut self, val: T);
    fn pop(&mut self) -> Option<T>;
    fn remove(&mut self, p: usize) -> T;
    fn insert(&mut self, n: usize, val: T);
    fn from_elem(val: T, n: usize) -> Self;
    fn from_elems(val: &[T]) -> Self;
}

impl<T: Copy> Vector<T> for Vec<T> {
    fn new() -> Self {
        Self::with_capacity(VEC_SIZE)
    }

    fn push(&mut self, val: T) {
        self.push(val)
    }

    fn pop(&mut self) -> Option<T> {
        self.pop()
    }

    fn remove(&mut self, p: usize) -> T {
        self.remove(p)
    }

    fn insert(&mut self, n: usize, val: T) {
        self.insert(n, val)
    }

    fn from_elem(val: T, n: usize) -> Self {
        vec![val; n]
    }

    fn from_elems(val: &[T]) -> Self {
        val.to_owned()
    }
}

impl<T: Copy> Vector<T> for SmallVec<[T; VEC_SIZE]> {
    fn new() -> Self {
        Self::new()
    }

    fn push(&mut self, val: T) {
        self.push(val)
    }

    fn pop(&mut self) -> Option<T> {
        self.pop()
    }

    fn remove(&mut self, p: usize) -> T {
        self.remove(p)
    }

    fn insert(&mut self, n: usize, val: T) {
        self.insert(n, val)
    }

    fn from_elem(val: T, n: usize) -> Self {
        smallvec![val; n]
    }

    fn from_elems(val: &[T]) -> Self {
        SmallVec::from_slice(val)
    }
}

macro_rules! make_benches {
    ($typ:ty { $($b_name:ident => $g_name:ident($($args:expr),*),)* }) => {
        $(
            #[bench]
            fn $b_name(b: &mut Bencher) {
                $g_name::<$typ>($($args,)* b)
            }
        )*
    }
}

make_benches! {
    SmallVec<[u64; VEC_SIZE]> {
        bench_push => gen_push(SPILLED_SIZE as _),
        bench_push_small => gen_push(VEC_SIZE as _),
        bench_insert => gen_insert(SPILLED_SIZE as _),
        bench_insert_small => gen_insert(VEC_SIZE as _),
        bench_remove => gen_remove(SPILLED_SIZE as _),
        bench_remove_small => gen_remove(VEC_SIZE as _),
        bench_extend => gen_extend(SPILLED_SIZE as _),
        bench_extend_small => gen_extend(VEC_SIZE as _),
        bench_from_iter => gen_from_iter(SPILLED_SIZE as _),
        bench_from_iter_small => gen_from_iter(VEC_SIZE as _),
        bench_from_slice => gen_from_slice(SPILLED_SIZE as _),
        bench_from_slice_small => gen_from_slice(VEC_SIZE as _),
        bench_extend_from_slice => gen_extend_from_slice(SPILLED_SIZE as _),
        bench_extend_from_slice_small => gen_extend_from_slice(VEC_SIZE as _),
        bench_macro_from_elem => gen_from_elem(SPILLED_SIZE as _),
        bench_macro_from_elem_small => gen_from_elem(VEC_SIZE as _),
        bench_pushpop => gen_pushpop(),
    }
}

make_benches! {
    Vec<u64> {
        bench_push_vec => gen_push(SPILLED_SIZE as _),
        bench_push_vec_small => gen_push(VEC_SIZE as _),
        bench_insert_vec => gen_insert(SPILLED_SIZE as _),
        bench_insert_vec_small => gen_insert(VEC_SIZE as _),
        bench_remove_vec => gen_remove(SPILLED_SIZE as _),
        bench_remove_vec_small => gen_remove(VEC_SIZE as _),
        bench_extend_vec => gen_extend(SPILLED_SIZE as _),
        bench_extend_vec_small => gen_extend(VEC_SIZE as _),
        bench_from_iter_vec => gen_from_iter(SPILLED_SIZE as _),
        bench_from_iter_vec_small => gen_from_iter(VEC_SIZE as _),
        bench_from_slice_vec => gen_from_slice(SPILLED_SIZE as _),
        bench_from_slice_vec_small => gen_from_slice(VEC_SIZE as _),
        bench_extend_from_slice_vec => gen_extend_from_slice(SPILLED_SIZE as _),
        bench_extend_from_slice_vec_small => gen_extend_from_slice(VEC_SIZE as _),
        bench_macro_from_elem_vec => gen_from_elem(SPILLED_SIZE as _),
        bench_macro_from_elem_vec_small => gen_from_elem(VEC_SIZE as _),
        bench_pushpop_vec => gen_pushpop(),
    }
}

fn gen_push<V: Vector<u64>>(n: u64, b: &mut Bencher) {
    #[inline(never)]
    fn push_noinline<V: Vector<u64>>(vec: &mut V, x: u64) {
        vec.push(x);
    }

    b.iter(|| {
        let mut vec = V::new();
        for x in 0..n {
            push_noinline(&mut vec, x);
        }
        vec
    });
}

fn gen_insert<V: Vector<u64>>(n: u64, b: &mut Bencher) {
    #[inline(never)]
    fn insert_noinline<V: Vector<u64>>(vec: &mut V, p: usize, x: u64) {
        vec.insert(p, x)
    }

    b.iter(|| {
        let mut vec = V::new();
        // Add one element, with each iteration we insert one before the end.
        // This means that we benchmark the insertion operation and not the
        // time it takes to `ptr::copy` the data.
        vec.push(0);
        for x in 0..n {
            insert_noinline(&mut vec, x as _, x);
        }
        vec
    });
}

fn gen_remove<V: Vector<u64>>(n: usize, b: &mut Bencher) {
    #[inline(never)]
    fn remove_noinline<V: Vector<u64>>(vec: &mut V, p: usize) -> u64 {
        vec.remove(p)
    }

    b.iter(|| {
        let mut vec = V::from_elem(0, n as _);

        for x in (0..n - 1).rev() {
            remove_noinline(&mut vec, x);
        }
    });
}

fn gen_extend<V: Vector<u64>>(n: u64, b: &mut Bencher) {
    b.iter(|| {
        let mut vec = V::new();
        vec.extend(0..n);
        vec
    });
}

fn gen_from_iter<V: Vector<u64>>(n: u64, b: &mut Bencher) {
    let v: Vec<u64> = (0..n).collect();
    b.iter(|| {
        let vec = V::from(&v);
        vec
    });
}

fn gen_from_slice<V: Vector<u64>>(n: u64, b: &mut Bencher) {
    let v: Vec<u64> = (0..n).collect();
    b.iter(|| {
        let vec = V::from_elems(&v);
        vec
    });
}

fn gen_extend_from_slice<V: Vector<u64>>(n: u64, b: &mut Bencher) {
    let v: Vec<u64> = (0..n).collect();
    b.iter(|| {
        let mut vec = V::new();
        vec.extend_from_slice(&v);
        vec
    });
}

fn gen_pushpop<V: Vector<u64>>(b: &mut Bencher) {
    #[inline(never)]
    fn pushpop_noinline<V: Vector<u64>>(vec: &mut V, x: u64) -> Option<u64> {
        vec.push(x);
        vec.pop()
    }

    b.iter(|| {
        let mut vec = V::new();
        for x in 0..SPILLED_SIZE as _ {
            pushpop_noinline(&mut vec, x);
        }
        vec
    });
}

fn gen_from_elem<V: Vector<u64>>(n: usize, b: &mut Bencher) {
    b.iter(|| {
        let vec = V::from_elem(42, n);
        vec
    });
}

#[bench]
fn bench_insert_many(b: &mut Bencher) {
    #[inline(never)]
    fn insert_many_noinline<I: IntoIterator<Item = u64>>(
        vec: &mut SmallVec<[u64; VEC_SIZE]>,
        index: usize,
        iterable: I,
    ) {
        vec.insert_many(index, iterable)
    }

    b.iter(|| {
        let mut vec = SmallVec::<[u64; VEC_SIZE]>::new();
        insert_many_noinline(&mut vec, 0, 0..SPILLED_SIZE as _);
        insert_many_noinline(&mut vec, 0, 0..SPILLED_SIZE as _);
        vec
    });
}

#[bench]
fn bench_insert_from_slice(b: &mut Bencher) {
    let v: Vec<u64> = (0..SPILLED_SIZE as _).collect();
    b.iter(|| {
        let mut vec = SmallVec::<[u64; VEC_SIZE]>::new();
        vec.insert_from_slice(0, &v);
        vec.insert_from_slice(0, &v);
        vec
    });
}

#[bench]
fn bench_macro_from_list(b: &mut Bencher) {
    b.iter(|| {
        let vec: SmallVec<[u64; 16]> = smallvec![
            0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 20, 24, 32, 36, 0x40, 0x80,
            0x100, 0x200, 0x400, 0x800, 0x1000, 0x2000, 0x4000, 0x8000, 0x10000, 0x20000, 0x40000,
            0x80000, 0x100000,
        ];
        vec
    });
}

#[bench]
fn bench_macro_from_list_vec(b: &mut Bencher) {
    b.iter(|| {
        let vec: Vec<u64> = vec![
            0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 20, 24, 32, 36, 0x40, 0x80,
            0x100, 0x200, 0x400, 0x800, 0x1000, 0x2000, 0x4000, 0x8000, 0x10000, 0x20000, 0x40000,
            0x80000, 0x100000,
        ];
        vec
    });
}
Commit	Line	Data
83c7162d	1	#![feature(test)]
3dfed10e	2	#![allow(deprecated)]
83c7162d	3
8faf50e0	4	#[macro_use]
83c7162d XL	5	extern crate smallvec;
	6	extern crate test;
	7
83c7162d	8	use self::test::Bencher;
8faf50e0	9	use smallvec::{ExtendFromSlice, SmallVec};
83c7162d	10
8faf50e0 XL	11	const VEC_SIZE: usize = 16;
	12	const SPILLED_SIZE: usize = 100;
	13
	14	trait Vector<T>: for<'a> From<&'a [T]> + Extend<T> + ExtendFromSlice<T> {
	15	fn new() -> Self;
	16	fn push(&mut self, val: T);
	17	fn pop(&mut self) -> Option<T>;
	18	fn remove(&mut self, p: usize) -> T;
	19	fn insert(&mut self, n: usize, val: T);
	20	fn from_elem(val: T, n: usize) -> Self;
b7449926	21	fn from_elems(val: &[T]) -> Self;
8faf50e0 XL	22	}
	23
	24	impl<T: Copy> Vector<T> for Vec<T> {
	25	fn new() -> Self {
	26	Self::with_capacity(VEC_SIZE)
	27	}
	28
	29	fn push(&mut self, val: T) {
	30	self.push(val)
	31	}
	32
	33	fn pop(&mut self) -> Option<T> {
	34	self.pop()
	35	}
	36
	37	fn remove(&mut self, p: usize) -> T {
	38	self.remove(p)
	39	}
	40
	41	fn insert(&mut self, n: usize, val: T) {
	42	self.insert(n, val)
	43	}
	44
	45	fn from_elem(val: T, n: usize) -> Self {
	46	vec![val; n]
	47	}
b7449926 XL	48
	49	fn from_elems(val: &[T]) -> Self {
	50	val.to_owned()
	51	}
8faf50e0 XL	52	}
	53
	54	impl<T: Copy> Vector<T> for SmallVec<[T; VEC_SIZE]> {
	55	fn new() -> Self {
	56	Self::new()
	57	}
	58
	59	fn push(&mut self, val: T) {
	60	self.push(val)
	61	}
	62
	63	fn pop(&mut self) -> Option<T> {
	64	self.pop()
	65	}
	66
	67	fn remove(&mut self, p: usize) -> T {
	68	self.remove(p)
	69	}
	70
	71	fn insert(&mut self, n: usize, val: T) {
	72	self.insert(n, val)
	73	}
	74
	75	fn from_elem(val: T, n: usize) -> Self {
	76	smallvec![val; n]
	77	}
b7449926 XL	78
	79	fn from_elems(val: &[T]) -> Self {
	80	SmallVec::from_slice(val)
	81	}
8faf50e0 XL	82	}
	83
	84	macro_rules! make_benches {
	85	($typ:ty { $($b_name:ident => $g_name:ident($($args:expr),),) }) => {
	86	$(
	87	#[bench]
	88	fn $b_name(b: &mut Bencher) {
	89	$g_name::<$typ>($($args,)* b)
	90	}
	91	)*
	92	}
	93	}
	94
	95	make_benches! {
	96	SmallVec<[u64; VEC_SIZE]> {
	97	bench_push => gen_push(SPILLED_SIZE as _),
	98	bench_push_small => gen_push(VEC_SIZE as _),
	99	bench_insert => gen_insert(SPILLED_SIZE as _),
	100	bench_insert_small => gen_insert(VEC_SIZE as _),
	101	bench_remove => gen_remove(SPILLED_SIZE as _),
	102	bench_remove_small => gen_remove(VEC_SIZE as _),
	103	bench_extend => gen_extend(SPILLED_SIZE as _),
	104	bench_extend_small => gen_extend(VEC_SIZE as _),
b7449926 XL	105	bench_from_iter => gen_from_iter(SPILLED_SIZE as _),
b7449926 XL	106	bench_from_iter_small => gen_from_iter(VEC_SIZE as _),
8faf50e0 XL	107	bench_from_slice => gen_from_slice(SPILLED_SIZE as _),
	108	bench_from_slice_small => gen_from_slice(VEC_SIZE as _),
	109	bench_extend_from_slice => gen_extend_from_slice(SPILLED_SIZE as _),
	110	bench_extend_from_slice_small => gen_extend_from_slice(VEC_SIZE as _),
	111	bench_macro_from_elem => gen_from_elem(SPILLED_SIZE as _),
	112	bench_macro_from_elem_small => gen_from_elem(VEC_SIZE as _),
	113	bench_pushpop => gen_pushpop(),
	114	}
	115	}
	116
	117	make_benches! {
	118	Vec<u64> {
	119	bench_push_vec => gen_push(SPILLED_SIZE as _),
	120	bench_push_vec_small => gen_push(VEC_SIZE as _),
	121	bench_insert_vec => gen_insert(SPILLED_SIZE as _),
	122	bench_insert_vec_small => gen_insert(VEC_SIZE as _),
	123	bench_remove_vec => gen_remove(SPILLED_SIZE as _),
	124	bench_remove_vec_small => gen_remove(VEC_SIZE as _),
	125	bench_extend_vec => gen_extend(SPILLED_SIZE as _),
	126	bench_extend_vec_small => gen_extend(VEC_SIZE as _),
b7449926 XL	127	bench_from_iter_vec => gen_from_iter(SPILLED_SIZE as _),
b7449926 XL	128	bench_from_iter_vec_small => gen_from_iter(VEC_SIZE as _),
8faf50e0 XL	129	bench_from_slice_vec => gen_from_slice(SPILLED_SIZE as _),
	130	bench_from_slice_vec_small => gen_from_slice(VEC_SIZE as _),
	131	bench_extend_from_slice_vec => gen_extend_from_slice(SPILLED_SIZE as _),
	132	bench_extend_from_slice_vec_small => gen_extend_from_slice(VEC_SIZE as _),
	133	bench_macro_from_elem_vec => gen_from_elem(SPILLED_SIZE as _),
	134	bench_macro_from_elem_vec_small => gen_from_elem(VEC_SIZE as _),
	135	bench_pushpop_vec => gen_pushpop(),
	136	}
	137	}
	138
	139	fn gen_push<V: Vector<u64>>(n: u64, b: &mut Bencher) {
83c7162d	140	#[inline(never)]
8faf50e0 XL	141	fn push_noinline<V: Vector<u64>>(vec: &mut V, x: u64) {
8faf50e0 XL	142	vec.push(x);
83c7162d XL	143	}
	144
	145	b.iter(\|\| {
8faf50e0 XL	146	let mut vec = V::new();
8faf50e0 XL	147	for x in 0..n {
83c7162d XL	148	push_noinline(&mut vec, x);
	149	}
	150	vec
	151	});
	152	}
	153
8faf50e0	154	fn gen_insert<V: Vector<u64>>(n: u64, b: &mut Bencher) {
83c7162d	155	#[inline(never)]
8faf50e0 XL	156	fn insert_noinline<V: Vector<u64>>(vec: &mut V, p: usize, x: u64) {
8faf50e0 XL	157	vec.insert(p, x)
83c7162d XL	158	}
	159
	160	b.iter(\|\| {
8faf50e0 XL	161	let mut vec = V::new();
	162	// Add one element, with each iteration we insert one before the end.
	163	// This means that we benchmark the insertion operation and not the
	164	// time it takes to `ptr::copy` the data.
	165	vec.push(0);
	166	for x in 0..n {
	167	insert_noinline(&mut vec, x as _, x);
83c7162d XL	168	}
	169	vec
	170	});
	171	}
	172
8faf50e0	173	fn gen_remove<V: Vector<u64>>(n: usize, b: &mut Bencher) {
83c7162d	174	#[inline(never)]
8faf50e0 XL	175	fn remove_noinline<V: Vector<u64>>(vec: &mut V, p: usize) -> u64 {
8faf50e0 XL	176	vec.remove(p)
83c7162d XL	177	}
	178
	179	b.iter(\|\| {
8faf50e0 XL	180	let mut vec = V::from_elem(0, n as _);
	181
	182	for x in (0..n - 1).rev() {
	183	remove_noinline(&mut vec, x);
	184	}
	185	});
	186	}
	187
	188	fn gen_extend<V: Vector<u64>>(n: u64, b: &mut Bencher) {
	189	b.iter(\|\| {
	190	let mut vec = V::new();
	191	vec.extend(0..n);
83c7162d XL	192	vec
	193	});
	194	}
	195
b7449926	196	fn gen_from_iter<V: Vector<u64>>(n: u64, b: &mut Bencher) {
8faf50e0	197	let v: Vec<u64> = (0..n).collect();
83c7162d	198	b.iter(\|\| {
8faf50e0	199	let vec = V::from(&v);
83c7162d XL	200	vec
	201	});
	202	}
	203
b7449926 XL	204	fn gen_from_slice<V: Vector<u64>>(n: u64, b: &mut Bencher) {
	205	let v: Vec<u64> = (0..n).collect();
	206	b.iter(\|\| {
	207	let vec = V::from_elems(&v);
	208	vec
	209	});
	210	}
	211
8faf50e0 XL	212	fn gen_extend_from_slice<V: Vector<u64>>(n: u64, b: &mut Bencher) {
	213	let v: Vec<u64> = (0..n).collect();
	214	b.iter(\|\| {
	215	let mut vec = V::new();
	216	vec.extend_from_slice(&v);
	217	vec
	218	});
	219	}
	220
	221	fn gen_pushpop<V: Vector<u64>>(b: &mut Bencher) {
	222	#[inline(never)]
	223	fn pushpop_noinline<V: Vector<u64>>(vec: &mut V, x: u64) -> Option<u64> {
	224	vec.push(x);
	225	vec.pop()
	226	}
	227
	228	b.iter(\|\| {
	229	let mut vec = V::new();
	230	for x in 0..SPILLED_SIZE as _ {
	231	pushpop_noinline(&mut vec, x);
	232	}
	233	vec
	234	});
	235	}
	236
	237	fn gen_from_elem<V: Vector<u64>>(n: usize, b: &mut Bencher) {
83c7162d	238	b.iter(\|\| {
8faf50e0	239	let vec = V::from_elem(42, n);
83c7162d XL	240	vec
	241	});
	242	}
	243
	244	#[bench]
8faf50e0 XL	245	fn bench_insert_many(b: &mut Bencher) {
	246	#[inline(never)]
	247	fn insert_many_noinline<I: IntoIterator<Item = u64>>(
	248	vec: &mut SmallVec<[u64; VEC_SIZE]>,
	249	index: usize,
	250	iterable: I,
	251	) {
	252	vec.insert_many(index, iterable)
	253	}
	254
83c7162d	255	b.iter(\|\| {
8faf50e0 XL	256	let mut vec = SmallVec::<[u64; VEC_SIZE]>::new();
	257	insert_many_noinline(&mut vec, 0, 0..SPILLED_SIZE as _);
	258	insert_many_noinline(&mut vec, 0, 0..SPILLED_SIZE as _);
83c7162d XL	259	vec
	260	});
	261	}
	262
	263	#[bench]
	264	fn bench_insert_from_slice(b: &mut Bencher) {
8faf50e0	265	let v: Vec<u64> = (0..SPILLED_SIZE as _).collect();
83c7162d	266	b.iter(\|\| {
8faf50e0	267	let mut vec = SmallVec::<[u64; VEC_SIZE]>::new();
83c7162d XL	268	vec.insert_from_slice(0, &v);
	269	vec.insert_from_slice(0, &v);
	270	vec
	271	});
	272	}
	273
	274	#[bench]
8faf50e0 XL	275	fn bench_macro_from_list(b: &mut Bencher) {
	276	b.iter(\|\| {
	277	let vec: SmallVec<[u64; 16]> = smallvec![
	278	0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 20, 24, 32, 36, 0x40, 0x80,
	279	0x100, 0x200, 0x400, 0x800, 0x1000, 0x2000, 0x4000, 0x8000, 0x10000, 0x20000, 0x40000,
	280	0x80000, 0x100000,
	281	];
	282	vec
	283	});
	284	}
83c7162d	285
8faf50e0 XL	286	#[bench]
8faf50e0 XL	287	fn bench_macro_from_list_vec(b: &mut Bencher) {
83c7162d	288	b.iter(\|\| {
8faf50e0 XL	289	let vec: Vec<u64> = vec![
	290	0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 20, 24, 32, 36, 0x40, 0x80,
	291	0x100, 0x200, 0x400, 0x800, 0x1000, 0x2000, 0x4000, 0x8000, 0x10000, 0x20000, 0x40000,
	292	0x80000, 0x100000,
	293	];
83c7162d XL	294	vec
	295	});
	296	}