libjmmcg  release_579_6_g8cffd
A C++ library containing an eclectic mix of useful, advanced components.
count_setbits.cpp
Go to the documentation of this file.
1 /******************************************************************************
2 ** Copyright © 2012 by J.M.McGuiness, coder@hussar.me.uk
3 **
4 ** This library is free software; you can redistribute it and/or
5 ** modify it under the terms of the GNU Lesser General Public
6 ** License as published by the Free Software Foundation; either
7 ** version 2.1 of the License, or (at your option) any later version.
8 **
9 ** This library is distributed in the hope that it will be useful,
10 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
11 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 ** Lesser General Public License for more details.
13 **
14 ** You should have received a copy of the GNU Lesser General Public
15 ** License along with this library; if not, write to the Free Software
16 ** Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17 */
18 
19 #include "stdafx.h"
20 
21 #define BOOST_TEST_MODULE libjmmcg_tests
22 #include <boost/test/included/unit_test.hpp>
23 
24 #include <boost/mpl/list.hpp>
25 
26 #include "core/count_setbits.hpp"
27 #include "core/ave_deviation_meter.hpp"
28 #include "core/stats_output.hpp"
29 
30 #include <boost/mpl/int.hpp>
31 
32 #include <chrono>
33 #include <random>
34 
35 using namespace libjmmcg;
36 
37 using timed_results_t=ave_deviation_meter<unsigned long long>;
38 
39 typedef boost::mpl::list<
40  std::pair<mpl::count_setbits<0>, boost::mpl::int_<0>>,
41  std::pair<mpl::count_setbits<1>, boost::mpl::int_<1>>,
42  std::pair<mpl::count_setbits<2>, boost::mpl::int_<1>>,
43  std::pair<mpl::count_setbits<3>, boost::mpl::int_<2>>,
44  std::pair<mpl::count_setbits<4>, boost::mpl::int_<1>>,
45  std::pair<mpl::count_setbits<5>, boost::mpl::int_<2>>,
46  std::pair<mpl::count_setbits<6>, boost::mpl::int_<2>>,
47  std::pair<mpl::count_setbits<7>, boost::mpl::int_<3>>
48 > check_mpl_setbits_tests;
49 
50 typedef boost::mpl::list<
51  dyn::basic::count_setbits,
52  dyn::builtin::count_setbits,
53  dyn::lookup::count_setbits<8>,
54  dyn::lookup::count_setbits<16>,
55  dyn::lookup::count_setbits<32>,
56  dyn::lookup::count_setbits<64>,
57  dyn::unroll::count_setbits
58 > check_dyn_setbits_tests;
59 
60 BOOST_AUTO_TEST_SUITE(count_setbits_tests)
61 
62 BOOST_AUTO_TEST_SUITE(mpl)
63 
64 BOOST_AUTO_TEST_CASE_TEMPLATE(check_value, setbits_t, check_mpl_setbits_tests) {
65  BOOST_CHECK_EQUAL(setbits_t::first_type::value, setbits_t::second_type::value);
66 }
67 
68 BOOST_AUTO_TEST_SUITE_END()
69 
70 BOOST_AUTO_TEST_SUITE(dyn)
71 
72 BOOST_AUTO_TEST_CASE_TEMPLATE(check_value_0, setbits_t, check_dyn_setbits_tests) {
73  BOOST_CHECK_EQUAL(setbits_t::result(0), 0);
74 }
75 
76 BOOST_AUTO_TEST_CASE_TEMPLATE(check_value_1, setbits_t, check_dyn_setbits_tests) {
77  BOOST_CHECK_EQUAL(setbits_t::result(1), 1);
78 }
79 
80 BOOST_AUTO_TEST_CASE_TEMPLATE(check_value_2, setbits_t, check_dyn_setbits_tests) {
81  BOOST_CHECK_EQUAL(setbits_t::result(2), 1);
82 }
83 
84 BOOST_AUTO_TEST_CASE_TEMPLATE(check_value_3, setbits_t, check_dyn_setbits_tests) {
85  BOOST_CHECK_EQUAL(setbits_t::result(3), 2);
86 }
87 
88 BOOST_AUTO_TEST_CASE_TEMPLATE(check_value_4, setbits_t, check_dyn_setbits_tests) {
89  BOOST_CHECK_EQUAL(setbits_t::result(4), 1);
90 }
91 
92 BOOST_AUTO_TEST_CASE_TEMPLATE(check_value_5, setbits_t, check_dyn_setbits_tests) {
93  BOOST_CHECK_EQUAL(setbits_t::result(5), 2);
94 }
95 
96 BOOST_AUTO_TEST_CASE_TEMPLATE(check_value_6, setbits_t, check_dyn_setbits_tests) {
97  BOOST_CHECK_EQUAL(setbits_t::result(6), 2);
98 }
99 
100 BOOST_AUTO_TEST_CASE_TEMPLATE(check_value_7, setbits_t, check_dyn_setbits_tests) {
101  BOOST_CHECK_EQUAL(setbits_t::result(7), 3);
102 }
103 
104 BOOST_AUTO_TEST_CASE_TEMPLATE(check_value_1023, setbits_t, check_dyn_setbits_tests) {
105  std::cout<<"Efficiency="<<setbits_t::efficiency()<<std::endl;
106  BOOST_CHECK_EQUAL(setbits_t::result(1023), 10);
107 }
108 
109 BOOST_AUTO_TEST_SUITE_END()
110 
111 BOOST_AUTO_TEST_SUITE(performance, *stats_to_csv::make_fixture("count_setbits.csv"))
112 
113 /**
114  \test <a href="./examples/count_setbits.svg">Graph</a> of performance results for the various count-setbits functions.
115  ==========================================================================================
116  Computing the number of bits set in 2<<21 randomly-generated numbers:
117  -# Build 1240: g++v4.5.2:
118  - dyn::basic::count_setbits = 1.41313e+07 bit counts/sec
119  - dyn::lookup::count_setbits, 8-bit cache = 6.68295e+07 bit counts/sec
120  - dyn::unroll::count_setbits = 8.12703e+06 bit counts/sec
121  -# Build 1241: g++v4.7.3:
122  - dyn::basic::count_setbits = 3.66071e+07 bit counts/sec
123  - dyn::lookup::count_setbits, 8-bit cache = 8.60793e+07 bit counts/sec.
124  - dyn::lookup::count_setbits, 16-bit cache = 1.09846e+08 bit counts/sec
125  - dyn::lookup::count_setbits, 32-bit cache = 1.09919e+08 bit counts/sec
126  - dyn::lookup::count_setbits, 64-bit cache = 1.49271e+08 bit counts/sec
127  - dyn::unroll::count_setbits = 2.59625e+07 bit counts/sec
128  -# Build 1627: g++v4.8.4:
129  - dyn::basic::count_setbits bit counts/sec = [16572381, 16907215 ~(+/-4%), 16969377], samples=21, total=355051515
130  - dyn::builtin::count_setbits bit counts/sec = [287045168, 291680516 ~(+/-4%), 296752794], samples=22, total=6416971371
131  - dyn::lookup::count_setbits, 8-bit cache bit counts/sec = [25221159, 25260814 ~(+/-4%), 25286541], samples=21, total=530477098
132  - dyn::lookup::count_setbits, 16-bit cache bit counts/sec = [40636574, 40737874 ~(+/-4%), 40812929], samples=21, total=855495365
133  - dyn::lookup::count_setbits, 32-bit cache bit counts/sec = [58788215, 58955639 ~(+/-4%), 59040610], samples=21, total=1238068428
134  - dyn::lookup::count_setbits, 64-bit cache bit counts/sec = [71190047, 71557163 ~(+/-4%), 71684025], samples=21, total=1502700440
135  - dyn::unroll::count_setbits bit counts/sec = [29459347, 29517343 ~(+/-4%), 29552128], samples=21, total=619864204
136 */
137 BOOST_AUTO_TEST_CASE_TEMPLATE(rate, setbits_t, check_dyn_setbits_tests) {
138  typedef std::vector<typename setbits_t::element_type> vtr_colln_t;
139 
140 #ifdef JMMCG_PERFORMANCE_TESTS
141  const unsigned long test_size=2<<21;
142 #else
143  const unsigned long test_size=2<<8;
144 #endif
145  const unsigned short loops_for_conv=50;
146  const double perc_conv_estimate=5.0;
147  typename setbits_t::element_type total=0;
148 
149  const std::pair<timed_results_t, bool> timed_results(compute_average_deviation<timed_results_t::value_type>(
150  perc_conv_estimate,
151  loops_for_conv,
152  [&total]() {
153  vtr_colln_t v;
154  v.reserve(test_size);
155  std::mt19937_64 gen(42);
156  std::uniform_int_distribution<typename vtr_colln_t::value_type> distribution;
157  std::generate_n(std::back_inserter(v), test_size, std::bind(distribution, gen));
158  const auto t1=std::chrono::high_resolution_clock::now();
159  for (auto const &i : v) {
160  total+=setbits_t::result(i);
161  }
162  const auto t2=std::chrono::high_resolution_clock::now();
163  return timed_results_t::value_type(static_cast<double>(test_size)*1000000/std::chrono::duration_cast<std::chrono::microseconds>(t2 - t1).count());
164  }
165  ));
166  std::cout<<typeid(setbits_t).name()<<" counts/sec="<<timed_results.first<<std::endl;
167 #ifdef JMMCG_PERFORMANCE_TESTS
168  stats_to_csv::handle->stats<<timed_results.first.to_csv()<<std::flush;
169  BOOST_CHECK(!timed_results.second);
170 #endif
171 }
172 
173 BOOST_AUTO_TEST_SUITE_END()
174 
175 BOOST_AUTO_TEST_SUITE_END()