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