1 ///////////////////////////////////////////////////////////////////////////////
2 // Copyright 2012 John Maddock. Distributed under the Boost
3 // Software License, Version 1.0. (See accompanying file
4 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
5
6 #ifdef _MSC_VER
7 #pragma warning(disable : 4244)
8 #endif
9
10 #include <cstdlib>
11 #include <boost/polygon/detail/voronoi_predicates.hpp>
12 #include <boost/polygon/detail/voronoi_structures.hpp>
13 #include <boost/polygon/detail/voronoi_ctypes.hpp>
14 #include <boost/random/mersenne_twister.hpp>
15 #include <boost/random/uniform_int_distribution.hpp>
16 #include <vector>
17 #include <map>
18 #include <boost/chrono.hpp>
19 #include <boost/multiprecision/cpp_int.hpp>
20
21 #ifdef TEST_GMP
22 #include <boost/multiprecision/gmp.hpp>
23 #endif
24 #ifdef TEST_TOMMATH
25 #include <boost/multiprecision/tommath.hpp>
26 #endif
27
28 #include "arithmetic_backend.hpp"
29
30 typedef boost::polygon::detail::point_2d<boost::int32_t> i_point;
31
32 template <class Clock>
33 struct stopwatch
34 {
35 typedef typename Clock::duration duration;
stopwatchstopwatch36 stopwatch()
37 {
38 m_start = Clock::now();
39 }
elapsedstopwatch40 duration elapsed()
41 {
42 return Clock::now() - m_start;
43 }
resetstopwatch44 void reset()
45 {
46 m_start = Clock::now();
47 }
48
49 private:
50 typename Clock::time_point m_start;
51 };
52
53 std::vector<i_point> points;
54 boost::random::mt19937 gen;
55
56 template <class Big>
57 struct cpp_int_voronoi_traits
58 {
59 typedef boost::int32_t int_type;
60 typedef boost::int64_t int_x2_type;
61 typedef boost::uint64_t uint_x2_type;
62 typedef Big big_int_type;
63 typedef double fpt_type;
64 typedef boost::polygon::detail::extended_exponent_fpt<fpt_type> efpt_type;
65 typedef boost::polygon::detail::ulp_comparison<fpt_type> ulp_cmp_type;
66 struct to_fpt_converter_type
67 {
68 template <class B, boost::multiprecision::expression_template_option ET>
operator ()cpp_int_voronoi_traits::to_fpt_converter_type69 double operator()(const boost::multiprecision::number<B, ET>& val)
70 {
71 return val.template convert_to<double>();
72 }
operator ()cpp_int_voronoi_traits::to_fpt_converter_type73 double operator()(double val)
74 {
75 return val;
76 }
operator ()cpp_int_voronoi_traits::to_fpt_converter_type77 double operator()(const efpt_type& that) const
78 {
79 return that.d();
80 }
81 template <class tag, class Arg1, class Arg2, class Arg3, class Arg4>
operator ()cpp_int_voronoi_traits::to_fpt_converter_type82 double operator()(const boost::multiprecision::detail::expression<tag, Arg1, Arg2, Arg3, Arg4>& e)
83 {
84 typedef typename boost::multiprecision::detail::expression<tag, Arg1, Arg2, Arg3, Arg4>::result_type r_t;
85 r_t r(e);
86 return r.template convert_to<double>();
87 }
88 };
89 struct to_efpt_converter_type
90 {
91 template <class B, boost::multiprecision::expression_template_option ET>
operator ()cpp_int_voronoi_traits::to_efpt_converter_type92 efpt_type operator()(const boost::multiprecision::number<B, ET>& val)
93 {
94 return efpt_type(val.template convert_to<double>(), 0);
95 }
operator ()cpp_int_voronoi_traits::to_efpt_converter_type96 efpt_type operator()(double val)
97 {
98 return efpt_type(val, 0);
99 }
100 template <class tag, class Arg1, class Arg2, class Arg3, class Arg4>
operator ()cpp_int_voronoi_traits::to_efpt_converter_type101 efpt_type operator()(const boost::multiprecision::detail::expression<tag, Arg1, Arg2, Arg3, Arg4>& e)
102 {
103 typedef typename boost::multiprecision::detail::expression<tag, Arg1, Arg2, Arg3, Arg4>::result_type r_t;
104 r_t r(e);
105 return efpt_type(r.template convert_to<double>(), 0);
106 }
107 };
108 };
109
110 template <class Big>
111 struct native_int_voronoi_traits
112 {
113 typedef boost::int32_t int_type;
114 typedef boost::int64_t int_x2_type;
115 typedef boost::uint64_t uint_x2_type;
116 typedef Big big_int_type;
117 typedef double fpt_type;
118 typedef boost::polygon::detail::extended_exponent_fpt<fpt_type> efpt_type;
119 typedef boost::polygon::detail::ulp_comparison<fpt_type> ulp_cmp_type;
120 struct to_fpt_converter_type
121 {
122 template <class T>
operator ()native_int_voronoi_traits::to_fpt_converter_type123 double operator()(const T& val) const
124 {
125 return val;
126 }
operator ()native_int_voronoi_traits::to_fpt_converter_type127 double operator()(const efpt_type& that) const
128 {
129 return that.d();
130 }
131 };
132 struct to_efpt_converter_type
133 {
134 template <class T>
operator ()native_int_voronoi_traits::to_efpt_converter_type135 efpt_type operator()(const T& val) const
136 {
137 return efpt_type(val, 0);
138 }
139 };
140 };
141
142 std::map<std::string, double> results;
143 double min_time = (std::numeric_limits<double>::max)();
144
145 template <class Traits>
test(const char * name)146 double test(const char* name)
147 {
148 typedef boost::polygon::detail::voronoi_predicates<Traits> preds;
149 typedef boost::polygon::detail::circle_event<boost::int32_t> circle_event;
150 typedef boost::polygon::detail::site_event<boost::int32_t> site_event;
151 typedef typename preds::template mp_circle_formation_functor<site_event, circle_event> circle_pred;
152
153 boost::random::uniform_int_distribution<> dist(0, points.size() - 1);
154 circle_pred pc;
155 circle_event event;
156
157 stopwatch<boost::chrono::high_resolution_clock> w;
158
159 for (unsigned i = 0; i < 10000; ++i)
160 {
161 site_event s1(points[dist(gen)]);
162 site_event s2(points[dist(gen)]);
163 site_event s3(points[dist(gen)]);
164 pc.ppp(s1, s2, s3, event);
165 pc.pps(s1, s2, s3, 0, event);
166 pc.pss(s1, s2, s3, 0, event);
167 pc.sss(s1, s2, s3, event);
168 }
169 double d = boost::chrono::duration_cast<boost::chrono::duration<double> >(w.elapsed()).count();
170 if (d < min_time)
171 min_time = d;
172 results[name] = d;
173 std::cout << "Time for " << std::setw(30) << std::left << name << " = " << d << std::endl;
174 return d;
175 }
176
generate_quickbook()177 void generate_quickbook()
178 {
179 std::cout << "[table\n[[Integer Type][Relative Performance (Actual time in parenthesis)]]\n";
180
181 std::map<std::string, double>::const_iterator i(results.begin()), j(results.end());
182
183 while (i != j)
184 {
185 double rel = i->second / min_time;
186 std::cout << "[[" << i->first << "][" << rel << "(" << i->second << "s)]]\n";
187 ++i;
188 }
189
190 std::cout << "]\n";
191 }
192
main()193 int main()
194 {
195 boost::random::uniform_int_distribution<> dist((std::numeric_limits<boost::int32_t>::min)() / 2, (std::numeric_limits<boost::int32_t>::max)() / 2);
196
197 for (unsigned i = 0; i < 100; ++i)
198 {
199 points.push_back(i_point(dist(gen), dist(gen)));
200 }
201
202 test<boost::polygon::detail::voronoi_ctype_traits<boost::int32_t> >("extended_int");
203
204 test<cpp_int_voronoi_traits<boost::multiprecision::int256_t> >("int256_t");
205 test<cpp_int_voronoi_traits<boost::multiprecision::int512_t> >("int512_t");
206 test<cpp_int_voronoi_traits<boost::multiprecision::int1024_t> >("int1024_t");
207
208 test<cpp_int_voronoi_traits<boost::multiprecision::checked_int256_t> >("checked_int256_t");
209 test<cpp_int_voronoi_traits<boost::multiprecision::checked_int512_t> >("checked_int512_t");
210 test<cpp_int_voronoi_traits<boost::multiprecision::checked_int1024_t> >("checked_int1024_t");
211
212 test<cpp_int_voronoi_traits<boost::multiprecision::number<boost::multiprecision::cpp_int_backend<>, boost::multiprecision::et_off> > >("cpp_int");
213
214 #ifdef TEST_GMP
215 test<cpp_int_voronoi_traits<boost::multiprecision::number<boost::multiprecision::gmp_int, boost::multiprecision::et_off> > >("mpz_int");
216 #endif
217 #ifdef TEST_TOMMATH
218 test<cpp_int_voronoi_traits<boost::multiprecision::number<boost::multiprecision::tommath_int, boost::multiprecision::et_off> > >("tom_int");
219 #endif
220
221 generate_quickbook();
222
223 test<native_int_voronoi_traits<boost::int64_t> >("int64_t");
224 test<cpp_int_voronoi_traits<boost::multiprecision::number<boost::multiprecision::arithmetic_backend<boost::int64_t>, boost::multiprecision::et_off> > >("number<arithmetic_backend<boost::int64_t>, et_off>");
225 //test<cpp_int_voronoi_traits<boost::multiprecision::number<boost::multiprecision::arithmetic_backend<boost::int64_t>, boost::multiprecision::et_on> > >("number<arithmetic_backend<boost::int64_t>, et_on>");
226
227 return 0;
228 }
229