BitMagic-C++
sample11.cpp
Go to the documentation of this file.
1 /*
2 Copyright(c) 2002-2017 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
3 
4 Licensed under the Apache License, Version 2.0 (the "License");
5 you may not use this file except in compliance with the License.
6 You may obtain a copy of the License at
7 
8  http://www.apache.org/licenses/LICENSE-2.0
9 
10 Unless required by applicable law or agreed to in writing, software
11 distributed under the License is distributed on an "AS IS" BASIS,
12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 See the License for the specific language governing permissions and
14 limitations under the License.
15 
16 For more information please visit: http://bitmagic.io
17 */
18 
19 /** \example sample11.cpp
20  Example of how to use various bit counting techniques
21 
22  \sa bm::bvector<>::count()
23  \sa bm::bvector<>::count_range()
24  \sa bm::bvector<>::count_to()
25  \sa bm::count_and()
26  \sa bm::bvector<>::counted_enumerator
27  */
28 
29 /*! \file sample11.cpp
30  \brief Example: bvector<> bit-counting techniques analysis
31 */
32 
33 #include <iostream>
34 #include <random>
35 #include <memory>
36 
37 #include "bm.h"
38 #include "bmalgo.h"
39 #include "bmtimer.h"
40 
41 using namespace std;
42 
43 // timing storage for benchmarking
45 
46 const unsigned benchmark_count = 10000;
47 unsigned vector_max = 400000000;
48 
49 std::random_device rand_dev;
50 std::mt19937 gen(rand_dev()); // mersenne_twister_engine
51 std::uniform_int_distribution<> rand_dis(1, int(vector_max)); // generate uniform numebrs for [1, vector_max]
52 
53 
54 /// generate pseudo-random bit-vector, mix of blocks
55 ///
56 static
58 {
59  unsigned i, j;
60  for (i = 0; i < vector_max;)
61  {
62  // generate bit-blocks
63  for (j = 0; j < 65535*8; i += 10, j++)
64  {
65  bv.set(i);
66  }
67  if (i > vector_max)
68  break;
69  // generate GAP (compressed) blocks
70  for (j = 0; j < 65535; i += 120, j++)
71  {
72  unsigned len = rand() % 64;
73  bv.set_range(i, i + len);
74  i += len;
75  if (i > vector_max)
76  break;
77  }
78  }
79 
80  // compress vector
82  bv.optimize(tb);
83 
84  // compute bit-vector statistics
86  bv.calc_stat(&st);
87 
88  std::cout << "Bit-vector statistics: GAP (compressed blocks)=" << st.gap_blocks
89  << ", BIT (uncompressed blocks)=" << st.bit_blocks
90  << std::endl << std::endl;
91 }
92 
93 /// "pre-heat" CPU to minimize dynamic overclocking effects
94 ///
95 static
96 unsigned pre_heat(const bm::bvector<>& bv)
97 {
98  unsigned cnt = 0;
99  unsigned m = 1;
100  for (unsigned i = 0; i < benchmark_count; ++i)
101  {
102  cnt += bv.count();
103  m+=cnt*cnt;
104  }
105  return m;
106 }
107 
108 
109 
110 /// simple population count for the whole vector
111 ///
112 static
114 {
115  unsigned cnt = 0;
116 
117  {
118  bm::chrono_taker tt1("1. bvector<>::count()", benchmark_count / 2, &timing_map);
119  for (unsigned i = 0; i < benchmark_count / 2; ++i)
120  {
121  cnt += bv.count();
122  }
123  }
124  // this is mostly to prevent compiler to optimize loop away
125  std::cout << "Count test finished." << cnt << "\r";
126 }
127 
128 /// count_range() test
129 ///
130 static
132 {
133  unsigned cnt = 0;
134  {
135  bm::chrono_taker tt1("2. bvector<>::count_range()", benchmark_count, &timing_map);
136  for (unsigned i = 0; i < benchmark_count; ++i)
137  {
138  unsigned from = unsigned(rand_dis(gen));
139  unsigned to = unsigned(rand_dis(gen));
140  if (from > to)
141  swap(from, to);
142  cnt += bv.count_range(from, to);
143  }
144  }
145  // this is mostly to prevent compiler to optimize loop away
146  std::cout << "Count range test finished." << cnt << "\r";
147 }
148 
149 /// count_range() test using pre-calculated blocks bit count
150 ///
151 static
153 {
154  unsigned cnt = 0;
155 
156  // build a block population count list, used for count_range() acceleration
157  // for this test it is intentionally excluded from the timing measurements
158 
159  unsigned blocks_cnt[bm::set_total_blocks];
160  bv.count_blocks(blocks_cnt);
161 
162  {
163  bm::chrono_taker tt1("3. bvector<>::count_range() with blocks list", benchmark_count, &timing_map);
164  cnt = 0;
165  for (unsigned i = 0; i < benchmark_count; ++i)
166  {
167  unsigned from = unsigned(rand_dis(gen));
168  unsigned to = unsigned(rand_dis(gen));
169  if (from > to)
170  swap(from, to);
171  cnt += bv.count_range(from, to, blocks_cnt); // use blocks count for acceleration
172  }
173  }
174  // this is mostly to prevent compiler to optimize loop away
175  std::cout << "Count range with blocks test finished." << cnt << "\r";
176 }
177 
178 /// count_to() test using pre-calculated rank-select index
179 ///
180 static
182 {
183  unsigned cnt = 0;
184 
185  // build a block population count list, used for count_to() acceleration
186  std::unique_ptr<bm::bvector<>::rs_index_type> rs(new bm::bvector<>::rs_index_type());
187  bv.build_rs_index(rs.get());
188 
189  {
190  bm::chrono_taker tt1("4. bvector<>::count_to() with rs_index", benchmark_count, &timing_map);
191 
192  for (unsigned i = 0; i < benchmark_count; ++i)
193  {
194  unsigned to = unsigned(rand_dis(gen));
195  cnt += bv.count_to(to, *rs); // use rank-select index for acceleration
196  }
197  }
198  // this is mostly to prevent compiler to optimize loop away
199  std::cout << "Count to with blocks test finished." << cnt << "\r";
200 }
201 
202 
203 /// count_range implemented via two count_to() calls using pre-calculated
204 /// rank-select index
205 ///
206 static
208 {
209  unsigned cnt = 0;
210 
211  // build a block population count list, used for count_to() acceleration
212  std::unique_ptr<bm::bvector<>::rs_index_type> rs(new bm::bvector<>::rs_index_type());
213  bv.build_rs_index(rs.get());
214 
215  {
216  bm::chrono_taker tt1("5. bvector<>::count_to to simulate count_range()", benchmark_count, &timing_map);
217 
218  for (unsigned i = 0; i < benchmark_count; ++i)
219  {
220  unsigned from = unsigned(rand_dis(gen));
221  unsigned to = unsigned(rand_dis(gen));
222  if (from > to)
223  swap(from, to);
224 
225  unsigned cnt_to = bv.count_to(to, *rs);
226  unsigned cnt_from = bv.count_to(from - 1, *rs);
227  unsigned cnt_r = cnt_to - cnt_from;
228  cnt += cnt_r;
229  }
230  }
231  // this is mostly to prevent compiler to optimize loop away
232  std::cout << "Count range via count_to test finished." << cnt << "\r";
233 }
234 
235 /// count_range implemented via bm::count_and
236 ///
237 /// this method can be used, when we need co compute multiple ranges in one call
238 ///
239 static
241 {
242  unsigned cnt = 0;
243  {
244  bm::chrono_taker tt1("6. bm::count_and with mask vector", benchmark_count, &timing_map);
245 
246  bm::bvector<> mask_bv(bm::BM_GAP); // use compressed mask, better seluts on long ranges
247  for (unsigned i = 0; i < benchmark_count; ++i)
248  {
249  unsigned from = unsigned(rand_dis(gen));
250  unsigned to = unsigned(rand_dis(gen));
251  if (from > to)
252  swap(from, to);
253 
254  mask_bv.set_range(from, to, true); // set mask vector
255 
256  cnt += bm::count_and(bv, mask_bv);
257  mask_bv.clear(true); // clear and free memory (faster)
258  }
259  }
260  // this is mostly to prevent compiler to optimize loop away
261  std::cout << "count AND finished." << cnt << "\r";
262 }
263 
264 /// count_to implemented via bm::bvector<>::counted_enumerator
265 ///
266 /// Counted enumerator is an iterator automata, which counts the running population count
267 /// along the iteration sequence
268 ///
269 static
271 {
272  unsigned cnt = 0;
273  {
274  // This is a slow method so we use less iterators
275  bm::chrono_taker tt1("7. bm::bvector<>::counted_enumerator", benchmark_count/20, &timing_map);
276 
277  for (unsigned i = 0; i < benchmark_count/20; ++i)
278  {
279  unsigned to = unsigned(rand_dis(gen));
281  for (; en.valid(); ++en)
282  {
283  if (*en > to)
284  break;
285  }
286  cnt += en.count();
287  }
288  }
289  std::cout << "counted_enumerator finished." << cnt << "\r";
290 }
291 
292 
293 
294 
295 int main(void)
296 {
297  try
298  {
299  bm::bvector<> bv;
300  generate_bvector(bv);
301 
302  /// pre-heat CPU to minimize dynamic overclocking
303  unsigned s = pre_heat(bv);
304  std::cout << s << "\r";
305 
306 
307  // Test 1.
308  // Uses plain bvector<>::count() to compute global population count
309  // This function would benefit from SIMD (SSE42 / AVX2) acceleration
310  //
311  bv_count_test(bv);
312 
313  // Test 2.
314  // Uses bvector<>::count_range() to compute population count in a randomly generated
315  // region of a bit-vector.
316  // This is should be naturally faster than Test 1, because it range is less than the whole
317  //
318  bv_count_range(bv);
319 
320  // Test 3.
321  // Uses bvector<>::count_range() together with bvector<>::count_blocks()
322  // (pre-calculated bit-count for each block).
323  // It make sense to use this method if bit-vector is constant (or chnages infrequently)
324  // and we need to do many range counting calculations
325  //
326  bv_count_range_acc(bv);
327 
328  // Test 4.
329  // Uses bvector<>::count_to() to compute population count to a specified element.
330  // Equivalent of count_range(0, to);
331  // This method uses acceleration structure using bvector<>::running_count_blocks()
332  // It is similar to count_range acceleration, but uses a different (faster) algorithm
333  //
334  bv_count_to_acc(bv);
335 
336  // Test 5.
337  // Uses bvector<>::count_to() twice to simulate count_range()
338  // using counting difference:
339  // count_r = count_to(0, from) - count_to(0, to-1)
340  // This method can actually be faster than count_range()
341  //
343 
344  // Test 6.
345  // Compute range population count via a mask vector and logical AND operation.
346  // Not the fastest method, but can be useful, when multiple ranges needs to be computed
347  //
348  bv_count_and(bv);
349 
350  // Test 7.
351  // Compute cout using counted_enumerator iterator
352  // method combines iteratrion over bit vector and sliding population count
354 
355 
356  // print all test timing results
357  //
358  std::cout << " "
359  << std::endl;
360 
362  }
363  catch(std::exception& ex)
364  {
365  std::cerr << ex.what() << std::endl;
366  return 1;
367  }
368 
369  return 0;
370 }
371 
Compressed bit-vector bvector<> container, set algebraic methods, traversal iterators.
int main(void)
Definition: sample11.cpp:295
bm::id_t count_range(bm::id_t left, bm::id_t right, const unsigned *block_count_arr=0) const
Returns count of 1 bits in the given range.
Definition: bm.h:2902
unsigned gap_blocks
Number of GAP blocks.
Definition: bmfunc.h:59
static void bv_count_range(const bm::bvector<> &bv)
count_range() test
Definition: sample11.cpp:131
void optimize(bm::word_t *temp_block=0, optmode opt_mode=opt_compress, statistics *stat=0)
Optimize memory bitvector&#39;s memory allocation.
Definition: bm.h:3056
static void generate_bvector(bm::bvector<> &bv)
generate pseudo-random bit-vector, mix of blocks
Definition: sample11.cpp:57
Timing utilities for benchmarking (internal)
Rank-Select acceleration index.
Definition: bm.h:101
bm::id_t count() const
Number of bits ON starting from the .
Definition: bm.h:1167
static void bv_count_to_acc(const bm::bvector<> &bv)
count_to() test using pre-calculated rank-select index
Definition: sample11.cpp:181
static void bv_count_test(const bm::bvector<> &bv)
simple population count for the whole vector
Definition: sample11.cpp:113
GAP compression is ON.
Definition: bmconst.h:113
Constant iterator designed to enumerate "ON" bits counted_enumerator keeps bitcount, ie number of ON bits starting from the position 0 in the bit string up to the currently enumerated bit.
Definition: bm.h:1121
#define BM_DECLARE_TEMP_BLOCK(x)
Definition: bm.h:47
Statistical information about bitset&#39;s memory allocation details.
Definition: bm.h:144
Algorithms for bvector<> (main include)
bm::chrono_taker::duration_map_type timing_map
Definition: sample11.cpp:44
std::uniform_int_distribution rand_dis(1, int(vector_max))
enumerator first() const
Returns enumerator pointing on the first non-zero bit.
Definition: bm.h:2122
bvector< Alloc > & set(bm::id_t n, bool val=true)
Sets bit n if val is true, clears bit n if val is false.
Definition: bm.h:1573
bvector< Alloc > & set_range(bm::id_t left, bm::id_t right, bool value=true)
Sets all bits in the specified closed interval [left,right] Interval must be inside the bvector&#39;s siz...
Definition: bm.h:2541
std::map< std::string, statistics > duration_map_type
test name to duration map
Definition: bmtimer.h:65
bm::id_t count() const
population cout (count of ON bits)
Definition: bm.h:2578
static void print_duration_map(const duration_map_type &dmap, format fmt=ct_time)
Definition: bmtimer.h:127
void build_rs_index(rs_index_type *rs_idx) const
compute running total of all blocks in bit vector (rank-select index)
Definition: bm.h:1787
bool valid() const
Checks if iterator is still valid.
Definition: bm.h:286
static void bv_counted_enumerator(const bm::bvector<> &bv)
count_to implemented via bm::bvector<>::counted_enumerator
Definition: sample11.cpp:270
static void bv_count_and(const bm::bvector<> &bv)
count_range implemented via bm::count_and
Definition: sample11.cpp:240
static unsigned pre_heat(const bm::bvector<> &bv)
"pre-heat" CPU to minimize dynamic overclocking effects
Definition: sample11.cpp:96
Utility class to collect performance measurements and statistics.
Definition: bmtimer.h:39
bm::id_t count_to(bm::id_t n, const rs_index_type &blocks_cnt) const
Returns count of 1 bits (population) in [0..right] range.
Definition: bm.h:2804
void calc_stat(struct bm::bvector< Alloc >::statistics *st) const
Calculates bitvector statistics.
Definition: bm.h:3285
static void bv_count_range_acc(const bm::bvector<> &bv)
count_range() test using pre-calculated blocks bit count
Definition: sample11.cpp:152
unsigned vector_max
Definition: sample11.cpp:47
const unsigned benchmark_count
Definition: sample11.cpp:46
unsigned bit_blocks
Number of bit blocks.
Definition: bmfunc.h:57
static void bv_count_to_range_acc(const bm::bvector<> &bv)
count_range implemented via two count_to() calls using pre-calculated rank-select index ...
Definition: sample11.cpp:207
void clear(bool free_mem=false)
Clears every bit in the bitvector.
Definition: bm.h:1661
const unsigned set_total_blocks
Definition: bmconst.h:80
unsigned count_blocks(unsigned *arr) const
Computes bitcount values for all bvector blocks.
Definition: bm.h:1751
std::mt19937 gen(rand_dev())
bm::id_t count_and(const BV &bv1, const BV &bv2)
Computes bitcount of AND operation of two bitsets.
Definition: bmalgo_impl.h:975
std::random_device rand_dev
Definition: sample11.cpp:49