fork(1) download
  1. //
  2. // compare linear insert with different POD sizes. std::list vs std::vector
  3. //
  4.  
  5. #include <list>
  6. #include <vector>
  7. #include <deque>
  8. #include <iostream>
  9. #include <iomanip>
  10. #include <random>
  11. #include <functional>
  12. #include <iostream>
  13. #include <chrono>
  14. #include <string>
  15. #include <numeric>
  16. #include <algorithm>
  17. #include <cassert>
  18.  
  19.  
  20. namespace g2
  21. {
  22. typedef std::chrono::high_resolution_clock clock;
  23. typedef std::chrono::microseconds microseconds;
  24. typedef std::chrono::milliseconds milliseconds;
  25.  
  26. clock::time_point now(){return clock::now();}
  27.  
  28. microseconds intervalUs(const clock::time_point& t1, const clock::time_point& t0)
  29. {return std::chrono::duration_cast<microseconds>(t1 - t0);}
  30.  
  31. milliseconds intervalMs(const clock::time_point& t1,const clock::time_point& t0)
  32. {return std::chrono::duration_cast<milliseconds>(t1 - t0);}
  33.  
  34.  
  35. class StopWatch
  36. {
  37. clock::time_point start_;
  38. public:
  39. StopWatch() : start_(clock::now()){}
  40. clock::time_point restart() { start_ = clock::now(); return start_;}
  41. microseconds elapsedUs() { return intervalUs(now(), start_);}
  42. milliseconds elapsedMs() {return intervalMs(now(), start_);}
  43. };
  44. } // g2
  45.  
  46. typedef unsigned int Number;
  47. typedef long long int TimeValue;
  48. const std::string rows_explained = "elements list_time vector_time deque_time ";
  49.  
  50.  
  51. // Silly POD to test with variadic POD size
  52. template<Number Size>
  53. struct POD
  54. {
  55. Number a[Size];
  56.  
  57. bool operator>=(const POD& b) const
  58. {
  59. return (this->a[0] >= b.a[0]);
  60. }
  61. };
  62.  
  63.  
  64. // Random integer function from http://www2.research.att.com/~bs/C++0xFAQ.html#std-random
  65. int random_int(int low, int high)
  66. {
  67. using namespace std;
  68. static default_random_engine engine {};
  69. typedef uniform_int_distribution<int> Distribution;
  70. static Distribution distribution {};
  71. return distribution(engine, Distribution::param_type{low, high});
  72. }
  73.  
  74.  
  75.  
  76. // Use a template approach to use functor, function pointer or lambda to insert an
  77. // element in the input container and return the "time result".
  78. // Search is LINEAR. Elements are insert in SORTED order
  79. template<typename ValueType, typename Container>
  80. void linearInsertion(const std::vector<ValueType>& numbers, Container& container)
  81. {
  82. std::for_each(numbers.begin(), numbers.end(),
  83. [&](const ValueType& n)
  84. {
  85. auto itr = container.begin();
  86. for (; itr!= container.end(); ++itr)
  87. {
  88. if ((*itr) >= n) {
  89. break;
  90. }
  91. }
  92. container.insert(itr, n);
  93. });
  94. }
  95.  
  96. // Measure time in microseconds (us) for linear insert in a std container
  97. template<typename Container, typename ValueType>
  98. TimeValue linearInsertPerformance(const std::vector<ValueType>& randoms, Container& container)
  99. {
  100. g2::StopWatch watch;
  101. linearInsertion<ValueType, Container>(std::cref(randoms), container);
  102. auto time = watch.elapsedUs().count();
  103. return time;
  104. }
  105.  
  106. template<Number SizeOfPod>
  107. void listVsVectorLinearPerformance(const size_t nbr_of_randoms)
  108. {
  109. // Generate n random values and push to storage
  110. typedef POD<SizeOfPod> POD_value;
  111. std::vector<POD_value> values(nbr_of_randoms);
  112. const auto lower_limit = 0;
  113. const auto upper_limit = nbr_of_randoms -1;
  114. std::for_each(values.begin(), values.end(), [&](POD_value& n) { n.a[0] = random_int(lower_limit, upper_limit);});
  115.  
  116. TimeValue list_time;
  117. TimeValue vector_time;
  118. TimeValue deque_time;
  119. std::cout << nbr_of_randoms << ",\t" << std::flush;
  120. { // force local scope - to clear up the containers at exit
  121. std::list<POD_value> list;
  122. list_time = linearInsertPerformance<std::list<POD_value>, POD_value>(values, list);
  123. }
  124. {
  125. std::vector<POD_value> vector;
  126. vector_time = linearInsertPerformance<std::vector<POD_value>, POD_value>(values, vector);
  127. }
  128.  
  129. {
  130. std::deque<POD_value> deque;
  131. deque_time = linearInsertPerformance<std::deque<POD_value>, POD_value>(values, deque);
  132. }
  133.  
  134.  
  135. std::cout << "\t" << list_time << ",\t" << vector_time << ",\t" << deque_time;
  136. std::cout << ",\tsizeof(POD): " << sizeof(POD_value) << " bytes" << std::endl << std::flush;
  137.  
  138. }
  139.  
  140. template<Number PodSizeIn4ByteIncrements>
  141. void measure()
  142. {
  143. g2::StopWatch watch;
  144. std::cout << "Measuring In Microseconds (us)" << std::endl;
  145. std::cout << rows_explained << std::endl;
  146.  
  147. // small increments for measuring up to 4000
  148. listVsVectorLinearPerformance<PodSizeIn4ByteIncrements>(100);
  149. listVsVectorLinearPerformance<PodSizeIn4ByteIncrements>(200);
  150. listVsVectorLinearPerformance<PodSizeIn4ByteIncrements>(400);
  151. listVsVectorLinearPerformance<PodSizeIn4ByteIncrements>(800);
  152. listVsVectorLinearPerformance<PodSizeIn4ByteIncrements>(1000);
  153. listVsVectorLinearPerformance<PodSizeIn4ByteIncrements>(2000);
  154. listVsVectorLinearPerformance<PodSizeIn4ByteIncrements>(3000);
  155. listVsVectorLinearPerformance<PodSizeIn4ByteIncrements>(4000);
  156. listVsVectorLinearPerformance<PodSizeIn4ByteIncrements>(5000);
  157.  
  158. for(auto cnt = 5000; cnt <= 11000; cnt+=2000)
  159. {
  160. listVsVectorLinearPerformance<PodSizeIn4ByteIncrements>(cnt);
  161. }
  162. auto total_time_ms = watch.elapsedMs().count();
  163. std::cout << "[" << rows_explained << "]" << std::endl;
  164.  
  165. typedef POD<PodSizeIn4ByteIncrements> POD_value;
  166. std::cout << "Test finished for " << sizeof(POD_value) << " bytes POD" << std::endl;
  167. std::cout << "The POD sized test took " << total_time_ms << " milliseconds (or " << total_time_ms/1000 << " seconds)\n\n" << std::endl;
  168. }
  169.  
  170.  
  171.  
  172. int main(int argc, char** argv)
  173. {
  174. g2::StopWatch watch;
  175. measure<1>(); // measure 4 bytes
  176. measure<2>(); // measure 8 bytes
  177. measure<4>(); // measure 16 bytes
  178. measure<8>(); // 32 bytes
  179. measure<16>(); // 64 bytes
  180. measure<32>(); // 128 bytes*/
  181. measure<64>(); // 256 bytes
  182. auto total_time_s = watch.elapsedMs().count()/1000;
  183. std::cout << "\n\n**********************************************\n" << std::endl;
  184. std::cout << "Exiting test: the whole measuring took " << total_time_s << " seconds";
  185. std::cout << " (or " << total_time_s/(60) << " minutes)" << std::endl;
  186.  
  187. return 0;
  188. }
  189.  
  190.  
  191.  
Time limit exceeded #stdin #stdout 15s 5312KB
stdin
Standard input is empty
stdout
Measuring In Microseconds (us)
elements         list_time   vector_time   deque_time 
100,		18,	18,	21,	sizeof(POD): 4 bytes
200,		30,	31,	46,	sizeof(POD): 4 bytes
400,		83,	83,	136,	sizeof(POD): 4 bytes
800,		290,	275,	449,	sizeof(POD): 4 bytes
1000,		403,	393,	685,	sizeof(POD): 4 bytes
2000,		1497,	1470,	2573,	sizeof(POD): 4 bytes
3000,		3235,	3179,	5536,	sizeof(POD): 4 bytes
4000,		5637,	5542,	9633,	sizeof(POD): 4 bytes
5000,		10446,	8625,	15253,	sizeof(POD): 4 bytes
5000,		10594,	8662,	15306,	sizeof(POD): 4 bytes
7000,		33073,	16752,	29667,	sizeof(POD): 4 bytes
9000,		71371,	27394,	48053,	sizeof(POD): 4 bytes
11000,		127991,	40922,	72330,	sizeof(POD): 4 bytes
[elements         list_time   vector_time   deque_time ]
Test finished for 4 bytes POD
The POD sized test took 582 milliseconds (or 0 seconds)


Measuring In Microseconds (us)
elements         list_time   vector_time   deque_time 
100,		16,	15,	22,	sizeof(POD): 8 bytes
200,		29,	37,	54,	sizeof(POD): 8 bytes
400,		80,	115,	167,	sizeof(POD): 8 bytes
800,		262,	419,	600,	sizeof(POD): 8 bytes
1000,		413,	617,	935,	sizeof(POD): 8 bytes
2000,		1512,	2355,	3611,	sizeof(POD): 8 bytes
3000,		3548,	5511,	7926,	sizeof(POD): 8 bytes
4000,		9322,	9041,	13632,	sizeof(POD): 8 bytes
5000,		19051,	14150,	21541,	sizeof(POD): 8 bytes
5000,		19035,	14174,	21401,	sizeof(POD): 8 bytes
7000,		50541,	27541,	41525,	sizeof(POD): 8 bytes
9000,		98414,	45873,	68926,	sizeof(POD): 8 bytes
11000,		165153,	70999,	103739,	sizeof(POD): 8 bytes
[elements         list_time   vector_time   deque_time ]
Test finished for 8 bytes POD
The POD sized test took 847 milliseconds (or 0 seconds)


Measuring In Microseconds (us)
elements         list_time   vector_time   deque_time 
100,		13,	19,	32,	sizeof(POD): 16 bytes
200,		30,	48,	66,	sizeof(POD): 16 bytes
400,		97,	137,	203,	sizeof(POD): 16 bytes
800,		278,	484,	742,	sizeof(POD): 16 bytes
1000,		405,	743,	1117,	sizeof(POD): 16 bytes
2000,		1549,	2806,	4296,	sizeof(POD): 16 bytes
3000,		5326,	6231,	9918,	sizeof(POD): 16 bytes
4000,		13891,	11109,	18281,	sizeof(POD): 16 bytes
5000,		27564,	17827,	30167,	sizeof(POD): 16 bytes
5000,		28079,	18142,	29430,	sizeof(POD): 16 bytes
7000,		69680,	39270,	61577,	sizeof(POD): 16 bytes
9000,		133828,	70351,	109575,	sizeof(POD): 16 bytes
11000,		217309,	112564,	167331,	sizeof(POD): 16 bytes
[elements         list_time   vector_time   deque_time ]
Test finished for 16 bytes POD
The POD sized test took 1215 milliseconds (or 1 seconds)


Measuring In Microseconds (us)
elements         list_time   vector_time   deque_time 
100,		17,	25,	31,	sizeof(POD): 32 bytes
200,		30,	65,	83,	sizeof(POD): 32 bytes
400,		88,	207,	303,	sizeof(POD): 32 bytes
800,		285,	760,	1084,	sizeof(POD): 32 bytes
1000,		417,	1185,	1669,	sizeof(POD): 32 bytes
2000,		2449,	4630,	6661,	sizeof(POD): 32 bytes
3000,		8737,	12297,	16092,	sizeof(POD): 32 bytes
4000,		19623,	26994,	29460,	sizeof(POD): 32 bytes
5000,		34135,	44987,	47772,	sizeof(POD): 32 bytes
5000,		35326,	53879,	49129,	sizeof(POD): 32 bytes
7000,		80189,	101926,	100646,	sizeof(POD): 32 bytes
9000,		148011,	172254,	170403,	sizeof(POD): 32 bytes
11000,		238875,	265761,	254506,	sizeof(POD): 32 bytes
[elements         list_time   vector_time   deque_time ]
Test finished for 32 bytes POD
The POD sized test took 1936 milliseconds (or 1 seconds)


Measuring In Microseconds (us)
elements         list_time   vector_time   deque_time 
100,		14,	33,	53,	sizeof(POD): 64 bytes
200,		36,	96,	138,	sizeof(POD): 64 bytes
400,		107,	361,	491,	sizeof(POD): 64 bytes
800,		371,	1714,	1882,	sizeof(POD): 64 bytes
1000,		652,	2903,	2882,	sizeof(POD): 64 bytes
2000,		5208,	14625,	13156,	sizeof(POD): 64 bytes
3000,		13885,	36723,	34668,	sizeof(POD): 64 bytes
4000,		29540,	66297,	59874,	sizeof(POD): 64 bytes
5000,		48984,	106224,	97407,	sizeof(POD): 64 bytes
5000,		48851,	106039,	102512,	sizeof(POD): 64 bytes
7000,		98475,	209986,	212567,	sizeof(POD): 64 bytes
9000,		208395,	359029,	347251,	sizeof(POD): 64 bytes
11000,		308337,	561461,	540677,	sizeof(POD): 64 bytes
[elements         list_time   vector_time   deque_time ]
Test finished for 64 bytes POD
The POD sized test took 3651 milliseconds (or 3 seconds)


Measuring In Microseconds (us)
elements         list_time   vector_time   deque_time 
100,		20,	55,	67,	sizeof(POD): 128 bytes
200,		34,	184,	243,	sizeof(POD): 128 bytes
400,		99,	664,	825,	sizeof(POD): 128 bytes
800,		344,	3223,	3373,	sizeof(POD): 128 bytes
1000,		603,	5543,	5436,	sizeof(POD): 128 bytes
2000,		5131,	26725,	22801,	sizeof(POD): 128 bytes
3000,		15589,	62033,	54406,	sizeof(POD): 128 bytes
4000,		29407,	114862,	105530,	sizeof(POD): 128 bytes
5000,		54591,	186082,	167228,	sizeof(POD): 128 bytes
5000,		49293,	188096,	168613,	sizeof(POD): 128 bytes
7000,		116838,	388462,	334585,	sizeof(POD): 128 bytes
9000,		196422,	664962,	582932,	sizeof(POD): 128 bytes
11000,		329338,	1041045,	890064,	sizeof(POD): 128 bytes
[elements         list_time   vector_time   deque_time ]
Test finished for 128 bytes POD
The POD sized test took 5829 milliseconds (or 5 seconds)


Measuring In Microseconds (us)
elements         list_time   vector_time   deque_time 
100,		22,	114,	111,	sizeof(POD): 256 bytes
200,		48,	389,	437,	sizeof(POD): 256 bytes
400,		166,	1703,	1636,	sizeof(POD): 256 bytes
800,		666,	7938,	6714,	sizeof(POD): 256 bytes
1000,		990,	12154,	11316,	sizeof(POD): 256 bytes
2000,		6986,	52560,	51073,	sizeof(POD): 256 bytes
3000,		17463,	130203,	118161,	sizeof(POD): 256 bytes
4000,		35687,	239496,	208851,	sizeof(POD): 256 bytes
5000,