This week only. Pastebin PRO Accounts Christmas Special! Don't miss out!Want more features on Pastebin? Sign Up, it's FREE!
Guest

Container time test

By: a guest on Mar 5th, 2012  |  syntax: C++  |  size: 5.49 KB  |  views: 29  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. # Run
  2. #  csplit -k <this file> "/FILE/" "{4}"
  3. #  source xx01
  4.  
  5. mv xx02 anti-optimization.cc
  6. mv xx03 perf.cc
  7. mv xx04 SConstruct
  8. mv xx05 timer.hpp
  9. rm xx00
  10. rm xx01
  11.  
  12.  
  13. //// FILE anti-optimization.cc
  14.  
  15. #include <vector>
  16. #include <list>
  17. using namespace std;
  18.  
  19. typedef vector<int> Vector;
  20. typedef list<int>   List;
  21.  
  22. void anti_optimization(Vector & v) {}
  23. void anti_optimization(List & l)   {}
  24.  
  25. void anti_optimization(Vector::iterator & v) {}
  26. void anti_optimization(List::iterator & l)   {}
  27.  
  28.  
  29. //// FILE perf.cc
  30.  
  31. #include <vector>
  32. #include <list>
  33. #include <cerrno>
  34. #include <cassert>
  35. #include <cstdlib>
  36. #include <iostream>
  37. #include <algorithm>
  38. #include <functional>
  39.  
  40.  
  41. #include "timer.hpp"
  42.  
  43. using namespace std;
  44.  
  45. typedef vector<int> Vector;
  46. typedef list<int>   List;
  47.  
  48. extern void anti_optimization(Vector & v);
  49. extern void anti_optimization(List & l);
  50. extern void anti_optimization(Vector::iterator & v);
  51. extern void anti_optimization(List::iterator & l);
  52.  
  53.  
  54. template<typename T>
  55. typename T::iterator
  56. get_random_removal_point(T & container)
  57. {
  58.     assert(container.size() < RAND_MAX);
  59.  
  60.     typename T::iterator place = container.begin();
  61.     int index = rand() % container.size();
  62.    
  63.     for(int i=0; i<index; ++i) {
  64.         ++place;
  65.         anti_optimization(place);
  66.     }
  67.  
  68.     return place;
  69. }
  70.  
  71.  
  72. template<typename T>
  73. void
  74. remove_n_random_elements(T & container, int n)
  75. {
  76.     for(int i=0; i<n; ++i) {
  77.         container.erase(get_random_removal_point(container));
  78.     }
  79. }
  80.  
  81.  
  82. template<typename T>
  83. void
  84. setup_container(T & container, int size, bool random_order)
  85. {
  86.     typedef typename T::iterator iterator;
  87.     for(int i=0; i<size; ++i) {
  88.         if (random_order) {
  89.             int number_to_insert = rand();
  90.             iterator place = lower_bound(container.begin(), container.end(), number_to_insert);
  91.             container.insert(place, number_to_insert);
  92.         }
  93.         else {
  94.             container.push_back(i);
  95.         }
  96.     }
  97. }
  98.  
  99.  
  100. template<typename T>
  101. void
  102. run_tests(int container_size, int number_of_removals, bool random_order)
  103. {
  104.     T container;
  105.  
  106.     number_of_removals = min(number_of_removals, container_size);
  107.  
  108.     {
  109.         srand(0);
  110.         BlockTimer timer("container setup time");
  111.         setup_container(container, container_size, random_order);
  112.     }
  113.  
  114.     assert(adjacent_find(container.begin(), container.end(), greater<int>())
  115.            == container.end());
  116.  
  117.     {
  118.         srand(1);
  119.         BlockTimer timer("removal time");
  120.         remove_n_random_elements(container, number_of_removals);
  121.     }
  122.  
  123.     anti_optimization(container);
  124. }
  125.  
  126.  
  127. int main(int argc, char** argv)
  128. {
  129.     if (argc != 4) {
  130.         cout << "usage: " << argv[0] << " <container size> <number of removals> <random order? (0 or 1)>\n";
  131.         exit(1);
  132.     }
  133.  
  134.     errno = 0;
  135.    
  136.     int container_size = strtol(argv[1], NULL, 10);
  137.     int number_of_removals = strtol(argv[2], NULL, 10);
  138.     bool random_order = strtol(argv[3], NULL, 10) != 0;
  139.  
  140.     if (errno != 0) {
  141.         cout << "All arguments must be numbers\n";
  142.         exit(1);
  143.     }
  144.  
  145.     {
  146.         cout << "Vector:\n";
  147.         BlockTimer timer("total vector time");
  148.         run_tests<Vector>(container_size, number_of_removals, random_order);
  149.     }
  150.  
  151.     {
  152.         cout << "List:\n";
  153.         BlockTimer timer("total list time");
  154.         run_tests<List>(container_size, number_of_removals, random_order);
  155.     }
  156.    
  157. }
  158.  
  159. # FILE SConstruct
  160. Program("time-removals", ["anti-optimization.cc", "perf.cc"], CCFLAGS="-O2")
  161.  
  162. //// FILE timer.hpp
  163.  
  164. #ifndef TIMER_HPP
  165. #define TIMER_HPP
  166.  
  167. #include <iostream>
  168.  
  169. #if defined(__WIN32) || defined(_MSC_VER)
  170. #  define WIN32_LEAN_AND_MEAN
  171. #  include <windows.h>
  172.  
  173. class BlockTimer
  174. {
  175.     unsigned long long start_time;
  176.     std::string description;
  177.    
  178. public:
  179.     BlockTimer() {}
  180.    
  181.     BlockTimer(std::string const & desc)
  182.     {
  183.         start(desc);
  184.     }
  185.  
  186.     void start(std::string const & desc)
  187.     {
  188.         description = desc;
  189.         start_time = GetTickCount();
  190.     }
  191.  
  192.     void finish() {
  193.         unsigned long long ms = GetTickCount() - start_time;
  194.         std::cout << "> Timer " << description << ": " << ms/1000 << "." << ms % 1000 << "\n";
  195.         start_time = 0;
  196.     }
  197.  
  198.     ~BlockTimer() {
  199.         if (start_time != 0) finish();
  200.     }
  201. };
  202.  
  203. #else // Unix version
  204.  
  205. #include <sys/time.h>
  206.  
  207. inline unsigned long long timevaldiff(struct timeval *starttime, struct timeval *finishtime)
  208. {
  209.   unsigned long long msec;
  210.   msec=(finishtime->tv_sec-starttime->tv_sec)*1000;
  211.   msec+=(finishtime->tv_usec-starttime->tv_usec)/1000;
  212.   return msec;
  213. }
  214.  
  215. class BlockTimer
  216. {
  217.     timeval start_time;
  218.     std::string description;
  219.    
  220. public:
  221.     BlockTimer() {}
  222.    
  223.     BlockTimer(std::string const & desc)
  224.     {
  225.         start(desc);
  226.     }
  227.  
  228.     void start(std::string const & desc)
  229.     {
  230.         description = desc;
  231.         gettimeofday(&start_time, NULL);
  232.         // start_time = GetTickCount();
  233.     }
  234.  
  235.     void finish() {
  236.         //unsigned long long ms = GetTickCount() - start_time;
  237.         timeval end_time;
  238.         gettimeofday(&end_time, NULL);
  239.         unsigned long long ms = timevaldiff(&start_time, &end_time);
  240.         std::cout << "> Timer " << description << ": " << ms/1000 << "." << ms % 1000 << "\n";
  241.         start_time.tv_sec = 0;
  242.     }
  243.  
  244.     ~BlockTimer() {
  245.         if (start_time.tv_sec != 0) finish();
  246.     }
  247. };
  248.  
  249. #endif
  250.  
  251.  
  252. // Yo emacs!
  253. // Local Variables:
  254. //     c-basic-offset: 4
  255. //     indent-tabs-mode: nil
  256. // End:
  257.  
  258. #endif
clone this paste RAW Paste Data