BitMagic-C++
sample12.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 sample12.cpp
20  Example of how to use various bit setting techniques.
21  Several techniques benchmarked to better illustrate relative performance.
22 
23  \sa bm::bvector<>::set()
24  \sa bm::bvector<>::set_bit()
25  \sa bm::bvector<>::set_bit_conditional()
26  \sa bm::bvector<>::set_range()
27  \sa bm::bvector<>::clear_bit()
28  \sa bm::bvector<>::reset()
29  \sa bm::bvector<>::flip()
30  \sa bm::bvector<>::swap()
31  \sa bm::bvector<>::extract_next()
32  \sa bm::bvector<>::set_bit_no_check()
33  \sa bm::combine_or()
34  */
35 
36 /*! \file sample12.cpp
37  \brief Example: bvector<> analysis of bit setting methods
38 */
39 
40 #include <iostream>
41 #include <vector>
42 #define BM64ADDR
43 #include "bm.h"
44 #include "bmalgo.h"
45 #include "bmtimer.h"
46 
47 using namespace std;
48 
49 // timing storage for benchmarking
51 
52 // depending of the build it may be "unsigned int" or 64-bit "unsigned long long"
54 
55 const unsigned benchmark_count = 1000;
57 
58 
59 // Utility template function used to print container
60 template<class T> void PrintContainer(T first, T last)
61 {
62  if (first == last)
63  std::cout << "<EMPTY SET>";
64  else
65  for (; first != last; ++first)
66  std::cout << *first << ";";
67  std::cout << std::endl;
68 }
69 
70 
71 static
72 void generate_test_vectors(std::vector<bm_size_type> &v1,
73  std::vector<bm_size_type> &v2,
74  std::vector<bm_size_type> &v3)
75 {
76  bm_size_type j;
77  for (j = 0; j < vector_max; j += 2)
78  {
79  v1.push_back(j);
80  }
81  for (j = 0; j < vector_max; j += 5)
82  {
83  v2.push_back(j);
84  }
85  for (j = 0; j < vector_max; j += 120)
86  {
87  v3.push_back(j);
88  }
89 }
90 
91 
92 // stress test for bm::bvector<>::set_bit()
93 //
94 static
96 {
97  bm::chrono_taker tt1("1. bvector<>::set_bit()", benchmark_count, &timing_map);
98  bm::bvector<> bv1, bv2, bv3;
99 
100  for (unsigned i = 0; i < benchmark_count; ++i)
101  {
102  bm_size_type j;
103  for (j = 0; j < vector_max; j += 2)
104  {
105  bv1.set_bit(j, true);
106  }
107  for (j = 0; j < vector_max; j += 10)
108  {
109  bv2.set_bit(j, true);
110  }
111  for (j = 0; j < vector_max; j += 120)
112  {
113  bv3.set_bit(j, true);
114  }
115  bv1.reset();
116  bv2.reset();
117  bv3.reset();
118  } // for
119 }
120 
121 
122 // stress test for bm::bvector<>::set_bit()
123 //
124 static
126 {
127  bm::chrono_taker tt1("2. bvector<>::set_bit_no_check()", benchmark_count, &timing_map);
128  bm::bvector<> bv1, bv2, bv3;
129 
130  bv1.init();
131  bv2.init();
132  bv3.init();
133 
134  for (unsigned i = 0; i < benchmark_count; ++i)
135  {
136  bm::id_t j;
137  for (j = 0; j < vector_max; j += 2)
138  {
139  bv1.set_bit_no_check(j);
140  }
141  for (j = 0; j < vector_max; j += 10)
142  {
143  bv2.set_bit_no_check(j);
144  }
145  for (j = 0; j < vector_max; j += 120)
146  {
147  bv3.set_bit_no_check(j);
148  }
149  }
150 }
151 
152 static
153 void combine_or_test(std::vector<bm_size_type> &v1,
154  std::vector<bm_size_type> &v2,
155  std::vector<bm_size_type> &v3)
156 {
157  bm::chrono_taker tt1("3. combine_or()", benchmark_count, &timing_map);
158  bm::bvector<> bv1, bv2, bv3;
159 
160  for (unsigned i = 0; i < benchmark_count; ++i)
161  {
162  bm::combine_or(bv1, v1.begin(), v1.end());
163  bm::combine_or(bv2, v2.begin(), v2.end());
164  bm::combine_or(bv3, v3.begin(), v3.end());
165  }
166 }
167 
168 static
169 void bvector_bulk_set_test(std::vector<bm_size_type> &v1,
170  std::vector<bm_size_type> &v2,
171  std::vector<bm_size_type> &v3)
172 {
173  bm::chrono_taker tt1("3. bvector<>::set() array", benchmark_count, &timing_map);
174  bm::bvector<> bv1, bv2, bv3;
175 
176  for (unsigned i = 0; i < benchmark_count; ++i)
177  {
178  bv1.set(&v1[0], bm_size_type(v1.size()));
179  bv2.set(&v2[0], bm_size_type(v2.size()));
180  bv3.set(&v3[0], bm_size_type(v3.size()));
181  }
182 }
183 
184 
185 
186 int main(void)
187 {
188  try
189  {
190  // 0. create bvector, use brace initialization to add some initial data
191  //
192  bm::bvector<> bv1 { 2, 3, 4 };
193 
194  PrintContainer(bv1.first(), bv1.end()); // 2, 3, 4
195  bv1.clear();
196 
197  // 1. Set some bits using regular bvector<>::set() method
198  //
199  bv1.set(10);
200  bv1.set(256);
201  bv1.set(1000000);
202 
203  PrintContainer(bv1.first(), bv1.end()); // 10, 256, 1000000
204 
205  // 2. now use bvector<>::set_bit()
206  // it returns a report if target actually changed
207  //
208 
209  bm::id_t bits[] = { 256, 512, 10 };
210  unsigned cnt = 0;
211 
212  for (unsigned i = 0; i < sizeof(bits) / sizeof(bits[0]); ++i)
213  {
214  bool b = bv1.set_bit(bits[i], true);
215  cnt += b;
216  }
217  std::cout << "Number of bits changed:" << cnt << std::endl;
218  PrintContainer(bv1.first(), bv1.end());
219 
220  // 3. set and clear some bits using bvector<>::set_bit_conditional()
221  // method sets bit n only if current value equals the condition
222  //
223  bool b;
224  b = bv1.set_bit_conditional(5, true, false); // set bit 5 to true if it is false (yes)
225  std::cout << "Bit 5 set:" << (b ? " yes " : " no ") << std::endl; // (yes)
226 
227  b = bv1.set_bit_conditional(256, true, false); // set bit 256 to true if it is false
228  std::cout << "Bit 256 set:" << (b ? " yes " : " no ") << std::endl; // (no)
229 
230  b = bv1.set_bit_conditional(256, true, true); // set bit 256 to true if it is true
231  std::cout << "Bit 256 set:" << (b ? " yes " : " no ") << std::endl; // (no)
232 
233  PrintContainer(bv1.first(), bv1.end());
234 
235  // 4. set or clear multiple bits using bvector::set_range()
236  // This method is faster than calling bvector::set() many times in a row
237  //
238  bv1.set_range(10, 15, true); // set all bits in [10..15] closed interval
239  PrintContainer(bv1.first(), bv1.end());
240 
241  bv1.set_range(10, 12, false); // clear all bits in [10..15] closed interval
242  PrintContainer(bv1.first(), bv1.end());
243 
244  // 5. bvector::clear_bit() - same as set_bit() just a syntax sugar
245  //
246  b = bv1.clear_bit(13);
247  std::cout << "Bit 13 set:" << (b ? " yes " : " no ") << std::endl; // (yes)
248 
249  // 6. bvector<>::reset() - clears all the bits, frees the blocks memory
250  // same as bvector<>::clear(true);
251  //
252  bv1.reset();
253  PrintContainer(bv1.first(), bv1.end()); // <EMPTY>
254 
255  // 7. use bm::combine_or() to set bits
256  //
257  bm::combine_or(bv1, &bits[0], &bits[0] + (sizeof(bits) / sizeof(bits[0])));
258  PrintContainer(bv1.first(), bv1.end()); // 10, 256, 512
259 
260  // 8. use bvector<>::flip( ) to flip a bit
261  //
262  bv1.flip(256);
263  bv1.flip(257);
264  PrintContainer(bv1.first(), bv1.end()); // 10, 257, 512
265 
266  // 9. bvector<>::swap() to flip content of two bit-vectors
267  //
268  bm::bvector<> bv2;
269  bv1.swap(bv2);
270  PrintContainer(bv1.first(), bv1.end()); // <EMPTY>
271  PrintContainer(bv2.first(), bv2.end()); // 10, 257, 512
272 
273  // 10. use bvector<>::extract_next() to find ON bit and turn it to 0
274  // this function is useful for building FIFO queues on bvector
275  //
276  bm_size_type p = 1;
277  for (p = bv2.extract_next(p); p != 0; p = bv2.extract_next(p))
278  {
279  std::cout << "Extracted p = " << p << std::endl;
280  }
281  PrintContainer(bv2.first(), bv2.end()); // <EMPTY>
282 
283  // 11. use bvector<>::set_bit_no_check() to set bits faster
284  //
285  bm::bvector<> bv3;
286  bv3.init(); // the key here you MUST call init() before setting bits this way
287 
288  bv3.set_bit_no_check(10);
289  bv3.set_bit_no_check(100);
290  bv3.set_bit_no_check(1000);
291 
292  PrintContainer(bv3.first(), bv3.end()); // 10, 100, 1000
293 
294 
295  std::vector<bm_size_type> v1, v2, v3;
296  generate_test_vectors(v1, v2, v3);
297 
298  for (unsigned k = 0; k < 1000; ++k)
299  {
300  // run a few CPU "pre-heat" loops to get consistent results
301  bm_size_type s = 0;
302  bm_size_type i;
303  for (i = 0; i < v1.size(); ++i)
304  s = s + s* v1[i] + i;
305  for (i = 0; i < v2.size(); ++i)
306  s = s + s* v2[i] + i;
307  std::cout << s << "\r";
308  }
309 
310  std::cout << std::endl << "Running benchmarks..." << std::endl;
311 
312  bv_set_bit_test();
314  combine_or_test(v1, v2, v3);
315  bvector_bulk_set_test(v1, v2, v3);
316 
317  // print all test timing results
318  //
319  std::cout << std::endl;
321  }
322  catch(std::exception& ex)
323  {
324  std::cerr << ex.what() << std::endl;
325  return 1;
326  }
327 
328  return 0;
329 }
330 
bv_set_bit_no_check_test
static void bv_set_bit_no_check_test()
Definition: sample12.cpp:125
main
int main(void)
Definition: sample12.cpp:186
bm::chrono_taker
Utility class to collect performance measurements and statistics.
Definition: bmtimer.h:39
bm::bvector::reset
bvector< Alloc > & reset()
Clears every bit in the bitvector.
Definition: bm.h:1239
bv_set_bit_test
static void bv_set_bit_test()
Definition: sample12.cpp:95
vector_max
bm_size_type vector_max
Definition: sample12.cpp:56
bm::bvector::set_bit_no_check
void set_bit_no_check(size_type n)
Set bit without checking preconditions (size, etc)
Definition: bm.h:3482
bm_size_type
bm::bvector ::size_type bm_size_type
Definition: sample12.cpp:53
combine_or_test
static void combine_or_test(std::vector< bm_size_type > &v1, std::vector< bm_size_type > &v2, std::vector< bm_size_type > &v3)
Definition: sample12.cpp:153
bmalgo.h
Algorithms for bvector<> (main include)
bm::bvector::swap
void swap(bvector< Alloc > &bvect) BMNOEXCEPT
Exchanges content of bv and this bvector.
Definition: bm.h:3395
bm::bvector<>
bm::bvector::set
bvector< Alloc > & set(size_type n, bool val=true)
Sets bit n if val is true, clears bit n if val is false.
Definition: bm.h:3595
timing_map
bm::chrono_taker::duration_map_type timing_map
Definition: sample12.cpp:50
bm::bvector::init
void init()
Explicit post-construction initialization.
Definition: bm.h:2137
bmtimer.h
Timing utilities for benchmarking (internal)
bm::chrono_taker::ct_all
@ ct_all
Definition: bmtimer.h:60
bm::id_t
unsigned int id_t
Definition: bmconst.h:37
bvector_bulk_set_test
static void bvector_bulk_set_test(std::vector< bm_size_type > &v1, std::vector< bm_size_type > &v2, std::vector< bm_size_type > &v3)
Definition: sample12.cpp:169
bm::combine_or
void combine_or(BV &bv, It first, It last)
OR Combine bitvector and the iterable sequence.
Definition: bmalgo_impl.h:1016
bm::chrono_taker::duration_map_type
std::map< std::string, statistics > duration_map_type
test name to duration map
Definition: bmtimer.h:65
bm::bvector::end
enumerator end() const
Returns enumerator pointing on the next bit after the last.
Definition: bm.h:1790
bm::chrono_taker::print_duration_map
static void print_duration_map(const duration_map_type &dmap, format fmt=ct_time)
Definition: bmtimer.h:127
bm::bvector::first
enumerator first() const
Returns enumerator pointing on the first non-zero bit.
Definition: bm.h:1784
PrintContainer
void PrintContainer(T first, T last)
Definition: sample12.cpp:60
bm::bvector::extract_next
size_type extract_next(size_type prev)
Finds the number of the next bit ON and sets it to 0.
Definition: bm.h:1564
bm::bvector::size_type
bm::id_t size_type
Definition: bm.h:117
benchmark_count
const unsigned benchmark_count
Definition: sample12.cpp:55
bm.h
Compressed bit-vector bvector<> container, set algebraic methods, traversal iterators.
bm::bvector::set_bit
bool set_bit(size_type n, bool val=true)
Sets bit n.
Definition: bm.h:3631
generate_test_vectors
static void generate_test_vectors(std::vector< bm_size_type > &v1, std::vector< bm_size_type > &v2, std::vector< bm_size_type > &v3)
Definition: sample12.cpp:72