7 use self::test
::Bencher
;
8 use smallvec
::{ExtendFromSlice, SmallVec}
;
10 const VEC_SIZE
: usize = 16;
11 const SPILLED_SIZE
: usize = 100;
13 trait Vector
<T
>: for<'a
> From
<&'a
[T
]> + Extend
<T
> + ExtendFromSlice
<T
> {
15 fn push(&mut self, val
: T
);
16 fn pop(&mut self) -> Option
<T
>;
17 fn remove(&mut self, p
: usize) -> T
;
18 fn insert(&mut self, n
: usize, val
: T
);
19 fn from_elem(val
: T
, n
: usize) -> Self;
20 fn from_elems(val
: &[T
]) -> Self;
23 impl<T
: Copy
> Vector
<T
> for Vec
<T
> {
25 Self::with_capacity(VEC_SIZE
)
28 fn push(&mut self, val
: T
) {
32 fn pop(&mut self) -> Option
<T
> {
36 fn remove(&mut self, p
: usize) -> T
{
40 fn insert(&mut self, n
: usize, val
: T
) {
44 fn from_elem(val
: T
, n
: usize) -> Self {
48 fn from_elems(val
: &[T
]) -> Self {
53 impl<T
: Copy
> Vector
<T
> for SmallVec
<[T
; VEC_SIZE
]> {
58 fn push(&mut self, val
: T
) {
62 fn pop(&mut self) -> Option
<T
> {
66 fn remove(&mut self, p
: usize) -> T
{
70 fn insert(&mut self, n
: usize, val
: T
) {
74 fn from_elem(val
: T
, n
: usize) -> Self {
78 fn from_elems(val
: &[T
]) -> Self {
79 SmallVec
::from_slice(val
)
83 macro_rules
! make_benches
{
84 ($typ
:ty { $($b_name:ident => $g_name:ident($($args:expr),*),)* }
) => {
87 fn $
b_name(b
: &mut Bencher
) {
88 $g_name
::<$typ
>($
($args
,)* b
)
95 SmallVec
<[u64; VEC_SIZE
]> {
96 bench_push
=> gen_push(SPILLED_SIZE
as _
),
97 bench_push_small
=> gen_push(VEC_SIZE
as _
),
98 bench_insert
=> gen_insert(SPILLED_SIZE
as _
),
99 bench_insert_small
=> gen_insert(VEC_SIZE
as _
),
100 bench_remove
=> gen_remove(SPILLED_SIZE
as _
),
101 bench_remove_small
=> gen_remove(VEC_SIZE
as _
),
102 bench_extend
=> gen_extend(SPILLED_SIZE
as _
),
103 bench_extend_small
=> gen_extend(VEC_SIZE
as _
),
104 bench_from_iter
=> gen_from_iter(SPILLED_SIZE
as _
),
105 bench_from_iter_small
=> gen_from_iter(VEC_SIZE
as _
),
106 bench_from_slice
=> gen_from_slice(SPILLED_SIZE
as _
),
107 bench_from_slice_small
=> gen_from_slice(VEC_SIZE
as _
),
108 bench_extend_from_slice
=> gen_extend_from_slice(SPILLED_SIZE
as _
),
109 bench_extend_from_slice_small
=> gen_extend_from_slice(VEC_SIZE
as _
),
110 bench_macro_from_elem
=> gen_from_elem(SPILLED_SIZE
as _
),
111 bench_macro_from_elem_small
=> gen_from_elem(VEC_SIZE
as _
),
112 bench_pushpop
=> gen_pushpop(),
118 bench_push_vec
=> gen_push(SPILLED_SIZE
as _
),
119 bench_push_vec_small
=> gen_push(VEC_SIZE
as _
),
120 bench_insert_vec
=> gen_insert(SPILLED_SIZE
as _
),
121 bench_insert_vec_small
=> gen_insert(VEC_SIZE
as _
),
122 bench_remove_vec
=> gen_remove(SPILLED_SIZE
as _
),
123 bench_remove_vec_small
=> gen_remove(VEC_SIZE
as _
),
124 bench_extend_vec
=> gen_extend(SPILLED_SIZE
as _
),
125 bench_extend_vec_small
=> gen_extend(VEC_SIZE
as _
),
126 bench_from_iter_vec
=> gen_from_iter(SPILLED_SIZE
as _
),
127 bench_from_iter_vec_small
=> gen_from_iter(VEC_SIZE
as _
),
128 bench_from_slice_vec
=> gen_from_slice(SPILLED_SIZE
as _
),
129 bench_from_slice_vec_small
=> gen_from_slice(VEC_SIZE
as _
),
130 bench_extend_from_slice_vec
=> gen_extend_from_slice(SPILLED_SIZE
as _
),
131 bench_extend_from_slice_vec_small
=> gen_extend_from_slice(VEC_SIZE
as _
),
132 bench_macro_from_elem_vec
=> gen_from_elem(SPILLED_SIZE
as _
),
133 bench_macro_from_elem_vec_small
=> gen_from_elem(VEC_SIZE
as _
),
134 bench_pushpop_vec
=> gen_pushpop(),
138 fn gen_push
<V
: Vector
<u64>>(n
: u64, b
: &mut Bencher
) {
140 fn push_noinline
<V
: Vector
<u64>>(vec
: &mut V
, x
: u64) {
145 let mut vec
= V
::new();
147 push_noinline(&mut vec
, x
);
153 fn gen_insert
<V
: Vector
<u64>>(n
: u64, b
: &mut Bencher
) {
155 fn insert_noinline
<V
: Vector
<u64>>(vec
: &mut V
, p
: usize, x
: u64) {
160 let mut vec
= V
::new();
161 // Add one element, with each iteration we insert one before the end.
162 // This means that we benchmark the insertion operation and not the
163 // time it takes to `ptr::copy` the data.
166 insert_noinline(&mut vec
, x
as _
, x
);
172 fn gen_remove
<V
: Vector
<u64>>(n
: usize, b
: &mut Bencher
) {
174 fn remove_noinline
<V
: Vector
<u64>>(vec
: &mut V
, p
: usize) -> u64 {
179 let mut vec
= V
::from_elem(0, n
as _
);
181 for x
in (0..n
- 1).rev() {
182 remove_noinline(&mut vec
, x
);
187 fn gen_extend
<V
: Vector
<u64>>(n
: u64, b
: &mut Bencher
) {
189 let mut vec
= V
::new();
195 fn gen_from_iter
<V
: Vector
<u64>>(n
: u64, b
: &mut Bencher
) {
196 let v
: Vec
<u64> = (0..n
).collect();
198 let vec
= V
::from(&v
);
203 fn gen_from_slice
<V
: Vector
<u64>>(n
: u64, b
: &mut Bencher
) {
204 let v
: Vec
<u64> = (0..n
).collect();
206 let vec
= V
::from_elems(&v
);
211 fn gen_extend_from_slice
<V
: Vector
<u64>>(n
: u64, b
: &mut Bencher
) {
212 let v
: Vec
<u64> = (0..n
).collect();
214 let mut vec
= V
::new();
215 vec
.extend_from_slice(&v
);
220 fn gen_pushpop
<V
: Vector
<u64>>(b
: &mut Bencher
) {
222 fn pushpop_noinline
<V
: Vector
<u64>>(vec
: &mut V
, x
: u64) -> Option
<u64> {
228 let mut vec
= V
::new();
229 for x
in 0..SPILLED_SIZE
as _
{
230 pushpop_noinline(&mut vec
, x
);
236 fn gen_from_elem
<V
: Vector
<u64>>(n
: usize, b
: &mut Bencher
) {
238 let vec
= V
::from_elem(42, n
);
244 fn bench_insert_many(b
: &mut Bencher
) {
246 fn insert_many_noinline
<I
: IntoIterator
<Item
= u64>>(
247 vec
: &mut SmallVec
<[u64; VEC_SIZE
]>,
251 vec
.insert_many(index
, iterable
)
255 let mut vec
= SmallVec
::<[u64; VEC_SIZE
]>::new();
256 insert_many_noinline(&mut vec
, 0, 0..SPILLED_SIZE
as _
);
257 insert_many_noinline(&mut vec
, 0, 0..SPILLED_SIZE
as _
);
263 fn bench_insert_from_slice(b
: &mut Bencher
) {
264 let v
: Vec
<u64> = (0..SPILLED_SIZE
as _
).collect();
266 let mut vec
= SmallVec
::<[u64; VEC_SIZE
]>::new();
267 vec
.insert_from_slice(0, &v
);
268 vec
.insert_from_slice(0, &v
);
274 fn bench_macro_from_list(b
: &mut Bencher
) {
276 let vec
: SmallVec
<[u64; 16]> = smallvec
![
277 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 20, 24, 32, 36, 0x40, 0x80,
278 0x100, 0x200, 0x400, 0x800, 0x1000, 0x2000, 0x4000, 0x8000, 0x10000, 0x20000, 0x40000,
286 fn bench_macro_from_list_vec(b
: &mut Bencher
) {
288 let vec
: Vec
<u64> = vec
![
289 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 20, 24, 32, 36, 0x40, 0x80,
290 0x100, 0x200, 0x400, 0x800, 0x1000, 0x2000, 0x4000, 0x8000, 0x10000, 0x20000, 0x40000,