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