1 // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
4 //
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
10
11 #![feature(test)]
12
13 extern crate test;
14 extern crate rand;
15 extern crate rand_xorshift;
16 extern crate bit_vec;
17
18 use test::{Bencher, black_box};
19 use rand::{Rng, RngCore, SeedableRng};
20 use rand_xorshift::XorShiftRng;
21 use bit_vec::BitVec;
22
23 const HUGE_BENCH_BITS : usize = 1 << 20;
24 const BENCH_BITS : usize = 1 << 14;
25 const U32_BITS: usize = 32;
26
small_rng() -> XorShiftRng27 fn small_rng() -> XorShiftRng {
28 XorShiftRng::from_entropy()
29 }
30
31 #[bench]
bench_usize_small(b: &mut Bencher)32 fn bench_usize_small(b: &mut Bencher) {
33 let mut r = small_rng();
34 let mut bit_vec = 0 as usize;
35 b.iter(|| {
36 for _ in 0..100 {
37 bit_vec |= 1 << ((r.next_u32() as usize) % U32_BITS);
38 }
39 black_box(&bit_vec);
40 });
41 }
42
43 #[bench]
bench_bit_set_big_fixed(b: &mut Bencher)44 fn bench_bit_set_big_fixed(b: &mut Bencher) {
45 let mut r = small_rng();
46 let mut bit_vec = BitVec::from_elem(BENCH_BITS, false);
47 b.iter(|| {
48 for _ in 0..100 {
49 bit_vec.set((r.next_u32() as usize) % BENCH_BITS, true);
50 }
51 black_box(&bit_vec);
52 });
53 }
54
55 #[bench]
bench_bit_set_big_variable(b: &mut Bencher)56 fn bench_bit_set_big_variable(b: &mut Bencher) {
57 let mut r = small_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_u32() as usize) % BENCH_BITS, r.gen());
62 }
63 black_box(&bit_vec);
64 });
65 }
66
67 #[bench]
bench_bit_set_small(b: &mut Bencher)68 fn bench_bit_set_small(b: &mut Bencher) {
69 let mut r = small_rng();
70 let mut bit_vec = BitVec::from_elem(U32_BITS, false);
71 b.iter(|| {
72 for _ in 0..100 {
73 bit_vec.set((r.next_u32() as usize) % U32_BITS, true);
74 }
75 black_box(&bit_vec);
76 });
77 }
78
79 #[bench]
bench_bit_vec_big_or(b: &mut Bencher)80 fn bench_bit_vec_big_or(b: &mut Bencher) {
81 let mut b1 = BitVec::from_elem(BENCH_BITS, false);
82 let b2 = BitVec::from_elem(BENCH_BITS, false);
83 b.iter(|| {
84 b1.or(&b2)
85 })
86 }
87
88 #[bench]
bench_bit_vec_big_xnor(b: &mut Bencher)89 fn bench_bit_vec_big_xnor(b: &mut Bencher) {
90 let mut b1 = BitVec::from_elem(BENCH_BITS, false);
91 let b2 = BitVec::from_elem(BENCH_BITS, false);
92 b.iter(|| {
93 b1.xnor(&b2)
94 })
95 }
96
97 #[bench]
bench_bit_vec_big_negate_xor(b: &mut Bencher)98 fn bench_bit_vec_big_negate_xor(b: &mut Bencher) {
99 let mut b1 = BitVec::from_elem(BENCH_BITS, false);
100 let b2 = BitVec::from_elem(BENCH_BITS, false);
101 b.iter(|| {
102 let res = b1.xor(&b2);
103 b1.negate();
104 res
105 })
106 }
107
108 #[bench]
bench_bit_vec_huge_xnor(b: &mut Bencher)109 fn bench_bit_vec_huge_xnor(b: &mut Bencher) {
110 let mut b1 = BitVec::from_elem(HUGE_BENCH_BITS, false);
111 let b2 = BitVec::from_elem(HUGE_BENCH_BITS, false);
112 b.iter(|| {
113 b1.xnor(&b2)
114 })
115 }
116
117 #[bench]
bench_bit_vec_huge_negate_xor(b: &mut Bencher)118 fn bench_bit_vec_huge_negate_xor(b: &mut Bencher) {
119 let mut b1 = BitVec::from_elem(HUGE_BENCH_BITS, false);
120 let b2 = BitVec::from_elem(HUGE_BENCH_BITS, false);
121 b.iter(|| {
122 let res = b1.xor(&b2);
123 b1.negate();
124 res
125 })
126 }
127
128 #[bench]
bench_bit_vec_small_iter(b: &mut Bencher)129 fn bench_bit_vec_small_iter(b: &mut Bencher) {
130 let bit_vec = BitVec::from_elem(U32_BITS, false);
131 b.iter(|| {
132 let mut sum = 0;
133 for _ in 0..10 {
134 for pres in &bit_vec {
135 sum += pres as usize;
136 }
137 }
138 sum
139 })
140 }
141
142 #[bench]
bench_bit_vec_big_iter(b: &mut Bencher)143 fn bench_bit_vec_big_iter(b: &mut Bencher) {
144 let bit_vec = BitVec::from_elem(BENCH_BITS, false);
145 b.iter(|| {
146 let mut sum = 0;
147 for pres in &bit_vec {
148 sum += pres as usize;
149 }
150 sum
151 })
152 }
153
154 #[bench]
bench_from_elem(b: &mut Bencher)155 fn bench_from_elem(b: &mut Bencher) {
156 let cap = black_box(BENCH_BITS);
157 let bit = black_box(true);
158 b.iter(|| {
159 // create a BitVec and popcount it
160 BitVec::from_elem(cap, bit).blocks()
161 .fold(0, |acc, b| acc + b.count_ones())
162 });
163 b.bytes = cap as u64 / 8;
164 }
165
166 #[bench]
bench_erathostenes(b: &mut test::Bencher)167 fn bench_erathostenes(b: &mut test::Bencher) {
168 let mut primes = vec![];
169 b.iter(|| {
170 primes.clear();
171 let mut sieve = BitVec::from_elem(1 << 16, true);
172 black_box(&mut sieve);
173 let mut i = 2;
174 while i < sieve.len() {
175 if sieve[i] == true {
176 primes.push(i);
177 }
178 let mut j = i;
179 while j < sieve.len() {
180 sieve.set(j, false);
181 j += i;
182 }
183 i += 1;
184 }
185 black_box(&mut sieve);
186 });
187 }
188
189 #[bench]
bench_erathostenes_set_all(b: &mut test::Bencher)190 fn bench_erathostenes_set_all(b: &mut test::Bencher) {
191 let mut primes = vec![];
192 let mut sieve = BitVec::from_elem(1 << 16, true);
193 b.iter(|| {
194 primes.clear();
195 black_box(&mut sieve);
196 sieve.set_all();
197 black_box(&mut sieve);
198 let mut i = 2;
199 while i < sieve.len() {
200 if sieve[i] == true {
201 primes.push(i);
202 }
203 let mut j = i;
204 while j < sieve.len() {
205 sieve.set(j, false);
206 j += i;
207 }
208 i += 1;
209 }
210 black_box(&mut sieve);
211 });
212 }
213