1 // Copyright 2012-2014 The Rust Project Developers.
2 // Copyright 2017 Matt Brubeck.
3 // See the COPYRIGHT file at the top-level directory of this distribution and at
4 // http://rust-lang.org/COPYRIGHT.
5 //
6 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
7 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
8 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
9 // option. This file may not be copied, modified, or distributed
10 // except according to those terms.
11
12 #![feature(test)]
13
14 extern crate bit_vec;
15 extern crate rand;
16 extern crate smallbitvec;
17 extern crate test;
18
19 use bit_vec::BitVec;
20 use rand::{weak_rng, Rng, XorShiftRng};
21 use smallbitvec::SmallBitVec;
22 use test::{black_box, Bencher};
23
24 const BENCH_BITS: usize = 1 << 14;
25 const USIZE_BITS: usize = ::std::mem::size_of::<usize>() * 8;
26
rng() -> XorShiftRng27 fn rng() -> XorShiftRng {
28 weak_rng()
29 }
30
31 #[bench]
bench_bit_set_big_fixed_bv(b: &mut Bencher)32 fn bench_bit_set_big_fixed_bv(b: &mut Bencher) {
33 let mut r = rng();
34 let mut bit_vec = BitVec::from_elem(BENCH_BITS, false);
35 b.iter(|| {
36 for _ in 0..100 {
37 bit_vec.set((r.next_u64() as usize) % BENCH_BITS, true);
38 }
39 black_box(&bit_vec);
40 });
41 }
42
43 #[bench]
bench_bit_set_big_fixed_sbv(b: &mut Bencher)44 fn bench_bit_set_big_fixed_sbv(b: &mut Bencher) {
45 let mut r = rng();
46 let mut bit_vec = SmallBitVec::from_elem(BENCH_BITS, false);
47 b.iter(|| {
48 for _ in 0..100 {
49 bit_vec.set(r.next_u64() as usize % BENCH_BITS, true);
50 }
51 black_box(&bit_vec);
52 });
53 }
54
55 #[bench]
bench_big_set_big_variable_bv(b: &mut Bencher)56 fn bench_big_set_big_variable_bv(b: &mut Bencher) {
57 let mut r = rng();
58 let mut bit_vec = BitVec::from_elem(BENCH_BITS, false);
59 b.iter(|| {
60 for _ in 0..100 {
61 bit_vec.set((r.next_u64() as usize) % BENCH_BITS, r.gen());
62 }
63 black_box(&bit_vec);
64 });
65 }
66
67 #[bench]
bench_bit_set_big_variable_sbv(b: &mut Bencher)68 fn bench_bit_set_big_variable_sbv(b: &mut Bencher) {
69 let mut r = rng();
70 let mut bit_vec = SmallBitVec::from_elem(BENCH_BITS, false);
71 b.iter(|| {
72 for _ in 0..100 {
73 bit_vec.set(r.next_u64() as usize % BENCH_BITS, r.gen());
74 }
75 black_box(&bit_vec);
76 });
77 }
78
79 #[bench]
bench_bit_set_small_bv(b: &mut Bencher)80 fn bench_bit_set_small_bv(b: &mut Bencher) {
81 let mut r = rng();
82 let mut bit_vec = BitVec::from_elem(USIZE_BITS, false);
83 b.iter(|| {
84 for _ in 0..100 {
85 bit_vec.set((r.next_u64() as usize) % USIZE_BITS, true);
86 }
87 black_box(&bit_vec);
88 });
89 }
90
91 #[bench]
bench_bit_set_small_sbv(b: &mut Bencher)92 fn bench_bit_set_small_sbv(b: &mut Bencher) {
93 let mut r = rng();
94 let mut bit_vec = SmallBitVec::from_elem(USIZE_BITS, false);
95 b.iter(|| {
96 for _ in 0..100 {
97 bit_vec.set(r.next_u64() as usize % USIZE_BITS, true);
98 }
99 black_box(&bit_vec);
100 });
101 }
102
103 #[bench]
bench_bit_vec_small_eq_bv(b: &mut Bencher)104 fn bench_bit_vec_small_eq_bv(b: &mut Bencher) {
105 let x = BitVec::from_elem(USIZE_BITS, false);
106 let y = BitVec::from_elem(USIZE_BITS, false);
107 b.iter(|| x == y);
108 }
109
110 #[bench]
bench_bit_vec_small_eq_sbv(b: &mut Bencher)111 fn bench_bit_vec_small_eq_sbv(b: &mut Bencher) {
112 let x = SmallBitVec::from_elem(USIZE_BITS, false);
113 let y = SmallBitVec::from_elem(USIZE_BITS, false);
114 b.iter(|| x == y);
115 }
116
117 #[bench]
bench_bit_vec_big_eq_bv(b: &mut Bencher)118 fn bench_bit_vec_big_eq_bv(b: &mut Bencher) {
119 let x = BitVec::from_elem(BENCH_BITS, false);
120 let y = BitVec::from_elem(BENCH_BITS, false);
121 b.iter(|| x == y);
122 }
123
124 #[bench]
bench_bit_vec_big_eq_sbv(b: &mut Bencher)125 fn bench_bit_vec_big_eq_sbv(b: &mut Bencher) {
126 let x = SmallBitVec::from_elem(BENCH_BITS, false);
127 let y = SmallBitVec::from_elem(BENCH_BITS, false);
128 b.iter(|| x == y);
129 }
130
131 #[bench]
bench_bit_vec_small_iter_bv(b: &mut Bencher)132 fn bench_bit_vec_small_iter_bv(b: &mut Bencher) {
133 let bit_vec = BitVec::from_elem(USIZE_BITS, false);
134 b.iter(|| {
135 let mut sum = 0;
136 for _ in 0..10 {
137 for pres in &bit_vec {
138 sum += pres as usize;
139 }
140 }
141 sum
142 })
143 }
144
145 #[bench]
bench_bit_vec_small_iter_sbv(b: &mut Bencher)146 fn bench_bit_vec_small_iter_sbv(b: &mut Bencher) {
147 let bit_vec = SmallBitVec::from_elem(USIZE_BITS, false);
148 b.iter(|| {
149 let mut sum = 0;
150 for _ in 0..10 {
151 for pres in &bit_vec {
152 sum += pres as usize;
153 }
154 }
155 sum
156 })
157 }
158
159 #[bench]
bench_bit_vec_big_iter_bv(b: &mut Bencher)160 fn bench_bit_vec_big_iter_bv(b: &mut Bencher) {
161 let bit_vec = BitVec::from_elem(BENCH_BITS, false);
162 b.iter(|| {
163 let mut sum = 0;
164 for pres in &bit_vec {
165 sum += pres as usize;
166 }
167 sum
168 })
169 }
170
171 #[bench]
bench_bit_vec_big_iter_sbv(b: &mut Bencher)172 fn bench_bit_vec_big_iter_sbv(b: &mut Bencher) {
173 let bit_vec = SmallBitVec::from_elem(BENCH_BITS, false);
174 b.iter(|| {
175 let mut sum = 0;
176 for pres in &bit_vec {
177 sum += pres as usize;
178 }
179 sum
180 })
181 }
182
183 #[bench]
bench_from_elem_bv(b: &mut Bencher)184 fn bench_from_elem_bv(b: &mut Bencher) {
185 let cap = black_box(BENCH_BITS);
186 let bit = black_box(true);
187 b.iter(|| BitVec::from_elem(cap, bit));
188 b.bytes = cap as u64 / 8;
189 }
190
191 #[bench]
bench_from_elem_sbv(b: &mut Bencher)192 fn bench_from_elem_sbv(b: &mut Bencher) {
193 let cap = black_box(BENCH_BITS);
194 let bit = black_box(true);
195 b.iter(|| SmallBitVec::from_elem(cap, bit));
196 b.bytes = cap as u64 / 8;
197 }
198
199 #[bench]
bench_remove_small(b: &mut Bencher)200 fn bench_remove_small(b: &mut Bencher) {
201 b.iter(|| {
202 let mut v = SmallBitVec::from_elem(USIZE_BITS, false);
203 for _ in 0..USIZE_BITS {
204 v.remove(0);
205 }
206 });
207 }
208
209 #[bench]
bench_remove_big(b: &mut Bencher)210 fn bench_remove_big(b: &mut Bencher) {
211 b.iter(|| {
212 let mut v = SmallBitVec::from_elem(BENCH_BITS, false);
213 for _ in 0..200 {
214 v.remove(0);
215 }
216 });
217 }
218