Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

bench paperplane code

By: sehe on Nov 17th, 2011  |  syntax: C++  |  size: 5.50 KB  |  views: 24  |  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. #define MAGNITUDE     20
  2. #define ITERATIONS    1024
  3. #define VERIFICATION  1
  4. #define VERBOSE       0
  5.  
  6. #define LIMITED_RANGE 0    // hide difference in output due to absense of overflows
  7.  
  8. /////////////////////////////
  9. #if VERIFICATION
  10. #   include <boost/functional/hash.hpp>
  11. #endif
  12. #include <cassert>
  13. #include <vector>
  14. #include <algorithm>
  15. #include <numeric>
  16. #include <iterator>
  17. #include <cstdint>
  18. #include <random>
  19. #include <iostream>
  20. #include <chrono>
  21.  
  22. #if VERBOSE
  23. #   include <boost/spirit/include/karma.hpp>
  24.  
  25. namespace
  26. {
  27.     template <typename T>
  28.         std::ostream& operator<<(std::ostream& os, const std::vector<T>& v)
  29.     {
  30.         using namespace boost::spirit::karma;
  31.         return os << format("v(" << auto_ % ",\t" << ")", v);
  32.     }
  33. }
  34. #endif
  35.  
  36. namespace stackoverflow // the code from the Original Post
  37. {
  38.     void theloop(const int64_t in[], int64_t out[], size_t N)
  39.     {
  40.         int64_t max = in[0];
  41.         out[0] = max;
  42.  
  43.         for(uint32_t i = 1; i < N; i++) {
  44.             int64_t v = in[i];
  45.             max += v;
  46.             if (v > max) max = v;
  47.             out[i] = max;
  48.         }
  49.     }
  50.  
  51.     void paper_plane(const int64_t in[], int64_t out[], size_t N)
  52.     {
  53.         int64_t max = 0;
  54.         int64_t i;
  55.         for(i=N-1; i > 0; --i) /* Comparing with 0 is faster */  
  56.         {  
  57.             max = in[i] > 0 ? max+in[i] : in[i]; /* Reduce operations v=in[i], max+=v by N times */  
  58.             out[i] = max;
  59.  
  60.             --i;  /* Will reduce checking of i>=0 by N/2 times */  
  61.  
  62.             max = in[i] > 0 ? max+in[i] : in[i]; /* Reduce operations v=in[i], max+=v by N times */  
  63.             out[i] = max;        
  64.         }
  65.  
  66.         if(0 == i) /* When N is odd */
  67.         {
  68.             max = in[i] > 0 ? max+in[i] : in[i];
  69.             out[i] = max;
  70.         }
  71.     }
  72. }
  73.  
  74. template <typename C> void paper_plane(const C& data, C& output)
  75. {
  76.     stackoverflow::paper_plane(&data[0], &output[0], data.size());
  77. }
  78.  
  79. template <typename C> void run_original_code(const C& data, C& output)
  80. {
  81.     stackoverflow::theloop(&data[0], &output[0], data.size());
  82. }
  83.  
  84. namespace measuring
  85. {
  86.     auto ts = std::chrono::system_clock::now();
  87.  
  88.     auto stopwatch_split() -> decltype(ts)
  89.     {
  90.         auto split = ts;
  91.         ts = std::chrono::system_clock::now();
  92.         return split;
  93.     }
  94.  
  95.     size_t report(const std::string& msg, bool newline=true)
  96.     {
  97.         auto split = stopwatch_split();
  98.         auto elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(ts - split);
  99.  
  100.         std::cout << msg << elapsed.count() << " msecs.";
  101.         if (newline)
  102.             std::cout << std::endl;
  103.  
  104.         return elapsed.count();
  105.     }
  106.  
  107.     template <typename C>
  108.     size_t run_benchmark(const C& data, C& output,
  109.             const std::string& label,
  110.             void(implementation)(const C&,C&),
  111.             size_t& reference_hash)
  112.     {
  113.         for (int i=0; i<ITERATIONS; ++i)
  114.         {
  115.             implementation(data, output);
  116.         }
  117.  
  118. #if VERIFICATION
  119.         size_t hash = boost::hash_range(output.begin(), output.end());
  120.  
  121.         if (!reference_hash)
  122.         {
  123.             reference_hash = hash;
  124.         }
  125.         else
  126.         {
  127. #   if VERBOSE
  128.             if (reference_hash!=hash)
  129.             {
  130.                 std::cerr << label << " hash mismatch! " << std::hex << hash << " (reference implementation: " << reference_hash << ")" << std::dec << std::endl;
  131.                 std::cerr << "data:       " << data << std::endl;
  132.                 std::cerr << "output:     " << output << std::endl;
  133.                 run_original_code(data, output);
  134.                 std::cerr << "ref output: " << output << std::endl;
  135.             }
  136.             else
  137.             {
  138.                 std::cerr << "data:       " << data << std::endl;
  139.                 std::cerr << "output:     " << output << std::endl;
  140.                 run_original_code(data, output);
  141.                 std::cerr << "ref output: " << output << std::endl;
  142.             }
  143. #   endif
  144. #endif
  145.         }
  146.  
  147.         size_t elapsed = report(label + " elapsed: ", false);
  148.         std::cout << " Hash " << std::hex << hash << std::dec << (hash==reference_hash? " ok" : " FAILED!") << std::endl;
  149.         return elapsed;
  150.     }
  151.  
  152. }
  153.  
  154. int main()
  155. {
  156.     typedef std::vector<int64_t> data_t;
  157.     data_t data(1ul << MAGNITUDE);
  158.     data_t output(data.size());
  159.  
  160.     size_t total_op = 0ul,
  161.            total_pp = 0ul;
  162.  
  163.     std::cout << "Benchmarking 20 x " << ITERATIONS << " iterations for data length " << data.size() << " (i.e. 20 different random seeds)" << std::endl;
  164.     for (size_t seed = 0; seed < 20; seed++)
  165.     {
  166.         std::mt19937 rng(seed);
  167. #if LIMITED_RANGE
  168.         std::uniform_int_distribution<int64_t> gen(-3,3);
  169. #else
  170.         std::uniform_int_distribution<int64_t> gen;
  171. #endif
  172.         std::generate(data.begin(), data.end(), std::bind(gen, rng));
  173.         measuring::report(" --- randomized from new seed --- ");
  174.  
  175.         size_t reference_hash = 0ul;
  176.         total_op += measuring::run_benchmark(data, output, "OP's code   ", run_original_code <data_t>    , reference_hash);
  177.         total_pp += measuring::run_benchmark(data, output, "paper.plane ", paper_plane <data_t>          , reference_hash);
  178.     }
  179.  
  180.     std::cout << "total time in OP algorithm: " << total_op << " msecs" << std::endl;
  181.     std::cout << "total time in Heuristic algorithm: " << total_pp << " msecs" << std::endl;
  182.     std::cout << "speedup factor: " << (1.0*total_op)/(1.0*total_pp) << " x" << std::endl;
  183. }