1 //////////////////////////////////////////////////////////////////////////////
2 //
3 // (C) Copyright Ion Gaztanaga 2013-2014. Distributed under the Boost
4 // Software License, Version 1.0. (See accompanying file
5 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6 //
7 // See http://www.boost.org/libs/container for documentation.
8 //
9 //////////////////////////////////////////////////////////////////////////////
10
11 #ifndef BOOST_CONTAINER_BENCH_BENCH_SET_HPP
12 #define BOOST_CONTAINER_BENCH_BENCH_SET_HPP
13
14 #include <iostream>
15 #include <boost/move/detail/nsec_clock.hpp>
16 #include <algorithm> //sort
17 #include <exception>
18 #include <sstream>
19 #include <iomanip>
20 #include <boost/container/vector.hpp>
21 #include <boost/container/string.hpp>
22 #include <boost/core/no_exceptions_support.hpp>
23
24 using boost::move_detail::cpu_timer;
25 using boost::move_detail::cpu_times;
26 using boost::move_detail::nanosecond_type;
27
28 #define SIMPLE_IT
29 #ifdef SIMPLE_IT
30 static const std::size_t NIter = 3;
31 #else
32 #ifdef NDEBUG
33 static const std::size_t NIter = 250;
34 #else
35 static const std::size_t NIter = 25;
36 #endif
37 #endif
38
39 static const std::size_t NElements = 1000;
40
41
compare_times(cpu_times time_numerator,cpu_times time_denominator)42 void compare_times(cpu_times time_numerator, cpu_times time_denominator)
43 {
44 std::cout << ((double)time_numerator.wall/(double)time_denominator.wall) << '\n' << std::endl;
45 }
46
47 template< class RandomIt >
random_shuffle(RandomIt first,RandomIt last)48 void random_shuffle( RandomIt first, RandomIt last )
49 {
50 typedef typename boost::container::iterator_traits<RandomIt>::difference_type difference_type;
51 difference_type n = last - first;
52 for (difference_type i = n-1; i > 0; --i) {
53 difference_type j = std::rand() % (i+1);
54 if(j != i) {
55 boost::adl_move_swap(first[i], first[j]);
56 }
57 }
58 }
59
60 boost::container::vector<int> sorted_unique_range_int;
61 boost::container::vector<int> sorted_range_int;
62 boost::container::vector<int> random_unique_range_int;
63 boost::container::vector<int> random_range_int;
64
fill_range_ints()65 void fill_range_ints()
66 {
67 //sorted_unique_range_int
68 sorted_unique_range_int.resize(NElements);
69 for(std::size_t i = 0, max = sorted_unique_range_int.size(); i != max; ++i){
70 sorted_unique_range_int[i] = static_cast<int>(i);
71 }
72 //sorted_range_int
73 sorted_range_int = sorted_unique_range_int;
74 sorted_range_int.insert(sorted_range_int.end(), sorted_unique_range_int.begin(), sorted_unique_range_int.end());
75 std::sort(sorted_range_int.begin(), sorted_range_int.end());
76
77 //random_range_int
78 std::srand(0);
79 random_range_int.assign(sorted_range_int.begin(), sorted_range_int.end());
80 ::random_shuffle(random_range_int.begin(), random_range_int.end());
81 //random_unique_range_int
82 std::srand(0);
83 random_unique_range_int.assign(sorted_unique_range_int.begin(), sorted_unique_range_int.end());
84 ::random_shuffle(random_unique_range_int.begin(), random_unique_range_int.end());
85 }
86
87 boost::container::vector<boost::container::string> sorted_unique_range_string;
88 boost::container::vector<boost::container::string> sorted_range_string;
89 boost::container::vector<boost::container::string> random_unique_range_string;
90 boost::container::vector<boost::container::string> random_range_string;
91
fill_range_strings()92 void fill_range_strings()
93 {
94 boost::container::string model_s;
95 model_s.append(sizeof(boost::container::string), '*');
96
97 //sorted_unique_range_int
98 sorted_unique_range_string.resize(NElements);
99 std::stringstream sstr;
100
101 for(std::size_t i = 0, max = sorted_unique_range_string.size(); i != max; ++i){
102 sstr.str(std::string());
103 sstr << std::setfill('0') << std::setw(10) << i;
104 sorted_unique_range_string[i] = model_s;
105 const std::string &s = sstr.str();
106 sorted_unique_range_string[i].append(s.begin(), s.end());
107 }
108 //sorted_range_string
109 sorted_range_string = sorted_unique_range_string;
110 sorted_range_string.insert(sorted_range_string.end(), sorted_unique_range_string.begin(), sorted_unique_range_string.end());
111 std::sort(sorted_range_string.begin(), sorted_range_string.end());
112
113 //random_range_string
114 std::srand(0);
115 random_range_string.assign(sorted_range_string.begin(), sorted_range_string.end());
116 ::random_shuffle(random_range_string.begin(), random_range_string.end());
117 //random_unique_range_string
118 std::srand(0);
119 random_unique_range_string.assign(sorted_unique_range_string.begin(), sorted_unique_range_string.end());
120 ::random_shuffle(random_unique_range_string.begin(), random_unique_range_string.end());
121 }
122
123 template<class T>
124 struct range_provider;
125
126 template<>
127 struct range_provider<int>
128 {
129 typedef boost::container::vector<int> type;
130
sorted_uniquerange_provider131 static type &sorted_unique()
132 { return sorted_unique_range_int; }
133
sortedrange_provider134 static type &sorted()
135 { return sorted_range_int; }
136
random_uniquerange_provider137 static type &random_unique()
138 { return random_unique_range_int; }
139
randomrange_provider140 static type &random()
141 { return random_range_int; }
142 };
143
144 template<>
145 struct range_provider<boost::container::string>
146 {
147 typedef boost::container::vector<boost::container::string> type;
148
sorted_uniquerange_provider149 static type &sorted_unique()
150 { return sorted_unique_range_string; }
151
sortedrange_provider152 static type &sorted()
153 { return sorted_range_string; }
154
random_uniquerange_provider155 static type &random_unique()
156 { return random_unique_range_string; }
157
randomrange_provider158 static type &random()
159 { return random_range_string; }
160 };
161
162 template<typename C>
copy_destroy_time(boost::container::vector<typename C::value_type> & unique_range)163 cpu_times copy_destroy_time(boost::container::vector<typename C::value_type> &unique_range)
164 {
165 cpu_timer copy_timer, assign_timer, destroy_timer;
166
167 cpu_timer total_time;
168
169 for(std::size_t i = 0; i != NIter; ++i){
170 {
171 C c(unique_range.begin(), unique_range.end());
172 total_time.resume();
173 copy_timer.resume();
174 C caux(c);
175 copy_timer.stop();
176 assign_timer.resume();
177 c = caux;
178 assign_timer.stop();
179 destroy_timer.resume();
180 }
181 destroy_timer.stop();
182 total_time.stop();
183 }
184 total_time.stop();
185
186 std::cout << " Copy sorted range " << double(copy_timer.elapsed().wall)/double(1000000000) << "s\n";
187 std::cout << " Assign sorted range " << double(assign_timer.elapsed().wall)/double(1000000000) << "s\n";
188 std::cout << " Destroy " << double(destroy_timer.elapsed().wall)/double(1000000000) << "s\n";
189 std::cout << " Total time = " << double(total_time.elapsed().wall)/double(1000000000) << "s\n";
190 return total_time.elapsed();
191 }
192
193 template<typename C>
construct_time(boost::container::vector<typename C::value_type> & unique_range,boost::container::vector<typename C::value_type> & range,const char * RangeType)194 cpu_times construct_time( boost::container::vector<typename C::value_type> &unique_range
195 , boost::container::vector<typename C::value_type> &range
196 , const char *RangeType)
197 {
198 cpu_timer sur_timer, sr_timer;
199
200 cpu_timer total_time;
201
202 for(std::size_t i = 0; i != NIter; ++i){
203 {
204 sur_timer.resume();
205 total_time.resume();
206 C c(unique_range.begin(), unique_range.end());
207 sur_timer.stop();
208 total_time.stop();
209 }
210 {
211 total_time.resume();
212 sr_timer.resume();
213 C c(range.begin(), range.end());
214 sr_timer.stop();
215 total_time.stop();
216 }
217 }
218
219 std::cout << " Construct " << RangeType << " unique_range " << double(sur_timer.elapsed().wall)/double(1000000000) << "s\n";
220 std::cout << " Construct " << RangeType << " range " << double(sr_timer.elapsed().wall)/double(1000000000) << "s\n";
221 std::cout << " Total time = " << double(total_time.elapsed().wall)/double(1000000000) << "s\n";
222 return total_time.elapsed();
223 }
224
225 template<typename C>
insert_time(boost::container::vector<typename C::value_type> & unique_range,boost::container::vector<typename C::value_type> & range,const char * RangeType)226 cpu_times insert_time( boost::container::vector<typename C::value_type> &unique_range
227 , boost::container::vector<typename C::value_type> &range
228 , const char *RangeType)
229 {
230 cpu_timer ur_timer,r_timer;
231 ur_timer.stop();r_timer.stop();
232
233 cpu_timer total_time;
234 total_time.resume();
235
236 for(std::size_t i = 0; i != NIter; ++i){
237 {
238 total_time.resume();
239 ur_timer.resume();
240 C c;
241 c.insert(unique_range.begin(), unique_range.end());
242 ur_timer.stop();
243 total_time.stop();
244 }
245 {
246 total_time.resume();
247 r_timer.resume();
248 C c;
249 c.insert(range.begin(), range.end());
250 r_timer.stop();
251 total_time.stop();
252 }
253 }
254
255 std::cout << " Insert " << RangeType << " unique_range " << double(ur_timer.elapsed().wall)/double(1000000000) << "s\n";
256 std::cout << " Insert " << RangeType << " range " << double(r_timer.elapsed().wall)/double(1000000000) << "s\n";
257 std::cout << " Total time = " << double(total_time.elapsed().wall)/double(1000000000) << "s\n";
258 return total_time.elapsed();
259 }
260
261 template<typename Iterator>
check_not_end(boost::container::vector<Iterator> & iterators,Iterator itend,std::size_t number_of_ends=0)262 bool check_not_end(boost::container::vector<Iterator> &iterators, Iterator itend, std::size_t number_of_ends = 0)
263 {
264 std::size_t end_count = 0;
265 for(std::size_t i = 0, max = iterators.size(); i != max; ++i){
266 if(iterators[i] == itend && (++end_count > number_of_ends) )
267 return false;
268 }
269 return true;
270 }
271
272 template<typename Iterator>
check_all_not_empty(boost::container::vector<std::pair<Iterator,Iterator>> & iterator_pairs)273 bool check_all_not_empty(boost::container::vector< std::pair<Iterator, Iterator > > &iterator_pairs)
274 {
275 for(std::size_t i = 0, max = iterator_pairs.size(); i != max; ++i){
276 if(iterator_pairs[i].first == iterator_pairs[i].second)
277 return false;
278 }
279 return true;
280 }
281
282 template<typename C>
search_time(boost::container::vector<typename C::value_type> & unique_range,const char * RangeType)283 cpu_times search_time(boost::container::vector<typename C::value_type> &unique_range, const char *RangeType)
284 {
285 cpu_timer find_timer, lower_timer, upper_timer, equal_range_timer, count_timer;
286
287 C c(unique_range.begin(), unique_range.end());
288
289 cpu_timer total_time;
290 total_time.resume();
291
292 boost::container::vector<typename C::iterator> v_it(NElements);
293 boost::container::vector< std::pair<typename C::iterator, typename C::iterator> > v_itp(NElements);
294
295 for(std::size_t i = 0; i != NIter; ++i){
296 //Find
297 {
298 find_timer.resume();
299 for(std::size_t rep = 0; rep != 2; ++rep)
300 for(std::size_t j = 0, max = unique_range.size(); j != max; ++j){
301 v_it[j] = c.find(unique_range[j]);
302 }
303 find_timer.stop();
304 if(!check_not_end(v_it, c.end())){
305 std::cout << "ERROR! find all elements not found" << std::endl;
306 }
307 }
308 //Lower
309 {
310 lower_timer.resume();
311 for(std::size_t rep = 0; rep != 2; ++rep)
312 for(std::size_t j = 0, max = unique_range.size(); j != max; ++j){
313 v_it[j] = c.lower_bound(unique_range[j]);
314 }
315 lower_timer.stop();
316 if(!check_not_end(v_it, c.end())){
317 std::cout << "ERROR! lower_bound all elements not found" << std::endl;
318 }
319 }
320 //Upper
321 {
322 upper_timer.resume();
323 for(std::size_t rep = 0; rep != 2; ++rep)
324 for(std::size_t j = 0, max = unique_range.size(); j != max; ++j){
325 v_it[j] = c.upper_bound(unique_range[j]);
326 }
327 upper_timer.stop();
328 if(!check_not_end(v_it, c.end(), 1u)){
329 std::cout << "ERROR! upper_bound all elements not found" << std::endl;
330 }
331 }
332 //Equal
333 {
334 equal_range_timer.resume();
335 for(std::size_t rep = 0; rep != 2; ++rep)
336 for(std::size_t j = 0, max = unique_range.size(); j != max; ++j){
337 v_itp[j] = c.equal_range(unique_range[j]);
338 }
339 equal_range_timer.stop();
340 if(!check_all_not_empty(v_itp)){
341 std::cout << "ERROR! equal_range all elements not found" << std::endl;
342 }
343 }
344 //Count
345 {
346 std::size_t count = 0;
347 count_timer.resume();
348 for(std::size_t rep = 0; rep != 2; ++rep)
349 for(std::size_t j = 0, max = unique_range.size(); j != max; ++j){
350 count += c.count(unique_range[j]);
351 }
352 count_timer.stop();
353 if(count/2 != c.size()){
354 std::cout << "ERROR! count all elements not found" << std::endl;
355 }
356 }
357 }
358 total_time.stop();
359
360 std::cout << " Find " << RangeType << " " << double(find_timer.elapsed().wall)/double(1000000000) << "s\n";
361 std::cout << " Lower Bound " << RangeType << " " << double(lower_timer.elapsed().wall)/double(1000000000) << "s\n";
362 std::cout << " Upper Bound " << RangeType << " " << double(upper_timer.elapsed().wall)/double(1000000000) << "s\n";
363 std::cout << " Equal Range " << RangeType << " " << double(equal_range_timer.elapsed().wall)/double(1000000000) << "s\n";
364 std::cout << " Count " << RangeType << " " << double(count_timer.elapsed().wall)/double(1000000000) << "s\n";
365 std::cout << " Total time = " << double(total_time.elapsed().wall)/double(1000000000) << "s\n";
366 return total_time.elapsed();
367 }
368
369 template<typename C>
extensions_time(boost::container::vector<typename C::value_type> & sorted_unique_range)370 void extensions_time(boost::container::vector<typename C::value_type> &sorted_unique_range)
371 {
372 cpu_timer sur_timer,sur_opt_timer;
373 sur_timer.stop();sur_opt_timer.stop();
374
375 for(std::size_t i = 0; i != NIter; ++i){
376 {
377 sur_timer.resume();
378 C c(sorted_unique_range.begin(), sorted_unique_range.end());
379 sur_timer.stop();
380 }
381 {
382 sur_opt_timer.resume();
383 C c(boost::container::ordered_unique_range, sorted_unique_range.begin(), sorted_unique_range.end());
384 sur_opt_timer.stop();
385 }
386
387 }
388 std::cout << " Construct sorted_unique_range " << double(sur_timer.elapsed().wall)/double(1000000000) << "s\n";
389 std::cout << " Construct sorted_unique_range (extension) " << double(sur_opt_timer.elapsed().wall)/double(1000000000) << "s\n";
390 std::cout << "Extension/Standard: ";
391 compare_times(sur_opt_timer.elapsed(), sur_timer.elapsed());
392 }
393
394 template<class BoostClass, class StdClass>
launch_tests(const char * BoostContName,const char * StdContName)395 void launch_tests(const char *BoostContName, const char *StdContName)
396 {
397 typedef range_provider<typename BoostClass::value_type> get_range_t;
398
399 std::cout << std::fixed << std::setw( 11 );
400 std::cout << "**********************************************" << '\n';
401 std::cout << "**********************************************" << '\n';
402 std::cout << '\n';
403 std::cout << BoostContName << " .VS " << StdContName << '\n';
404 std::cout << '\n';
405 std::cout << "**********************************************" << '\n';
406 std::cout << "**********************************************" << '\n' << std::endl;
407 {
408 std::cout << "Copy/Assign/Destroy benchmark:" << BoostContName << std::endl;
409 cpu_times boost_set_time = copy_destroy_time< BoostClass >(get_range_t::sorted_unique());
410
411 std::cout << "Copy/Assign/Destroy benchmark:" << StdContName << std::endl;
412 cpu_times std_set_time = copy_destroy_time< StdClass >(get_range_t::sorted_unique());
413
414 std::cout << BoostContName << "/" << StdContName << ": ";
415 compare_times(boost_set_time, std_set_time);
416 }
417 {
418 std::cout << "Ordered construct benchmark:" << BoostContName << std::endl;
419 cpu_times boost_set_time = construct_time< BoostClass >(get_range_t::sorted_unique(), get_range_t::sorted(), "(ord)");
420
421 std::cout << "Ordered construct benchmark:" << StdContName << std::endl;
422 cpu_times std_set_time = construct_time< StdClass >(get_range_t::sorted_unique(), get_range_t::sorted(), "(ord)");;
423
424 std::cout << BoostContName << "/" << StdContName << ": ";
425 compare_times(boost_set_time, std_set_time);
426 }
427 {
428 std::cout << "Random construct benchmark:" << BoostContName << std::endl;
429 cpu_times boost_set_time = construct_time< BoostClass >(get_range_t::random_unique(), get_range_t::random(), "(rnd)");
430
431 std::cout << "Random construct benchmark:" << StdContName << std::endl;
432 cpu_times std_set_time = construct_time< StdClass >(get_range_t::random_unique(), get_range_t::random(), "(rnd)");;
433
434 std::cout << BoostContName << "/" << StdContName << ": ";
435 compare_times(boost_set_time, std_set_time);
436 }
437 {
438 std::cout << "Ordered Insert benchmark:" << BoostContName << std::endl;
439 cpu_times boost_set_time = insert_time< BoostClass >(get_range_t::sorted_unique(), get_range_t::sorted(), "(ord)");
440
441 std::cout << "Ordered Insert benchmark:" << StdContName << std::endl;
442 cpu_times std_set_time = insert_time< StdClass >(get_range_t::sorted_unique(), get_range_t::sorted(), "(ord)");
443
444 std::cout << BoostContName << "/" << StdContName << ": ";
445 compare_times(boost_set_time, std_set_time);
446 }
447 {
448 std::cout << "Random Insert benchmark:" << BoostContName << std::endl;
449 cpu_times boost_set_time = insert_time< BoostClass >(get_range_t::random_unique(), get_range_t::random(), "(rnd)");
450
451 std::cout << "Random Insert benchmark:" << StdContName << std::endl;
452 cpu_times std_set_time = insert_time< StdClass >(get_range_t::random_unique(), get_range_t::random(), "(rnd)");
453
454 std::cout << BoostContName << "/" << StdContName << ": ";
455 compare_times(boost_set_time, std_set_time);
456 }
457 {
458 std::cout << "Ordered Search benchmark:" << BoostContName << std::endl;
459 cpu_times boost_set_time = search_time< BoostClass >(get_range_t::sorted_unique(), "(ord)");
460
461 std::cout << "Ordered Search benchmark:" << StdContName << std::endl;
462 cpu_times std_set_time = search_time< StdClass >(get_range_t::sorted_unique(), "(ord)");
463
464 std::cout << BoostContName << "/" << StdContName << ": ";
465 compare_times(boost_set_time, std_set_time);
466 }
467 {
468 std::cout << "Random Search benchmark:" << BoostContName << std::endl;
469 cpu_times boost_set_time = search_time< BoostClass >(get_range_t::random_unique(), "(rnd)");
470
471 std::cout << "Random Search benchmark:" << StdContName << std::endl;
472 cpu_times std_set_time = search_time< StdClass >(get_range_t::random_unique(), "(rnd)");
473
474 std::cout << BoostContName << "/" << StdContName << ": ";
475 compare_times(boost_set_time, std_set_time);
476 }
477 {
478 std::cout << "Extensions benchmark:" << BoostContName << std::endl;
479 extensions_time< BoostClass >(get_range_t::sorted_unique());
480 }
481 }
482
483 #endif //#ifndef BOOST_CONTAINER_BENCH_BENCH_SET_HPP
484