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 
Compressed bit-vector bvector<> container, set algebraic methods, traversal iterators.
bvector< Alloc > & reset()
Clears every bit in the bitvector.
Definition: bm.h:1623
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
void swap(bvector< Alloc > &bvect) BMNOEXEPT
Exchanges content of bv and this bvector.
Definition: bm.h:3342
bm::id_t size_type
Definition: bm.h:117
Timing utilities for benchmarking (internal)
bm_size_type vector_max
Definition: sample12.cpp:56
void combine_or(BV &bv, It first, It last)
OR Combine bitvector and the iterable sequence.
Definition: bmalgo_impl.h:1148
Algorithms for bvector<> (main include)
static void bv_set_bit_test()
Definition: sample12.cpp:95
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:3539
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
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
int main(void)
Definition: sample12.cpp:186
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:60
void init()
Explicit post-construction initialization.
Definition: bm.h:2427
const unsigned benchmark_count
Definition: sample12.cpp:55
static void bv_set_bit_no_check_test()
Definition: sample12.cpp:125
enumerator end() const
Returns enumerator pointing on the next bit after the last.
Definition: bm.h:2128
Utility class to collect performance measurements and statistics.
Definition: bmtimer.h:39
bm::chrono_taker::duration_map_type timing_map
Definition: sample12.cpp:50
bm::bvector ::size_type bm_size_type
Definition: sample12.cpp:53
unsigned int id_t
Definition: bmconst.h:37
void set_bit_no_check(size_type n)
Set bit without checking preconditions (size, etc)
Definition: bm.h:3425
bool set_bit(size_type n, bool val=true)
Sets bit n.
Definition: bm.h:3575