Advertisement
aaronhma

"Reverse Bits" Benchmark Runner

Jun 29th, 2022 (edited)
853
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.68 KB | None
  1. // new benchmark runner (https://quick-bench.com/q/Dy6YZLWuJyZjDmN59OpcwmvwhLg)
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
  7.  
  8. static void slow(benchmark::State &state)
  9. {
  10.   uint32_t n = rng();
  11.  
  12.   for (auto _ : state)
  13.   {
  14.     uint32_t ans = 0;
  15.  
  16.     for (int i = 1; i <= 32; i++) // 32 bits
  17.     {
  18.       ans <<= 1; // make space for this bit
  19.       ans += n & 1; // add 1 to our answer if this bit is 1
  20.       n >>= 1; // remove last bit
  21.     }
  22.  
  23.     benchmark::DoNotOptimize(ans);
  24.   }
  25. }
  26.  
  27. BENCHMARK(slow);
  28.  
  29. void update(uint32_t &n, uint32_t first, uint32_t last, int shift)
  30. {
  31.   first = n & first;
  32.   last = n & last;
  33.   last <<= shift;
  34.   first >>= shift;
  35.   last |= first;
  36.   n = last;
  37. }
  38.  
  39. static void fast(benchmark::State &state)
  40. {
  41.   uint32_t n = rng();
  42.  
  43.   for (auto _ : state)
  44.   {
  45.     update(n, 0b11111111111111110000000000000000, 0b00000000000000001111111111111111, 16);
  46.     update(n, 0b11111111000000001111111100000000, 0b00000000111111110000000011111111, 8);
  47.     update(n, 0b11110000111100001111000011110000, 0b00001111000011110000111100001111, 4);
  48.     update(n, 0b11001100110011001100110011001100, 0b00110011001100110011001100110011, 2);
  49.     update(n, 0b10101010101010101010101010101010, 0b01010101010101010101010101010101, 1);
  50.  
  51.     benchmark::DoNotOptimize(n);
  52.   }
  53. }
  54. BENCHMARK(fast);
  55.  
  56.  
  57.  
  58. /*
  59. * old benchmark:
  60. // Benchmark runner for https://pastebin.com/9M6ipqs0
  61. #include <bits/stdc++.h>
  62.  
  63. using namespace std;
  64.  
  65. #define FORI(i, a, b) for (int i = a; i <= b; i++)
  66.  
  67. // see https://codeforces.com/blog/entry/61587
  68. mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
  69.  
  70. // adapted from https://pastebin.com/9M6ipqs0
  71. class Solution
  72. {
  73. public:
  74.   Solution() {}
  75.   ~Solution() = default;
  76.  
  77.   uint32_t slow(uint32_t &n)
  78.   {
  79.     uint32_t ans = 0;
  80.  
  81.     // 32 bits
  82.     for (int i = 1; i <= 32; i++)
  83.     {
  84.       // make space for this bit
  85.       ans <<= 1;
  86.  
  87.       // add 1 to our answer if this bit is 1
  88.       ans += n & 1;
  89.  
  90.       // remove last bit
  91.       n >>= 1;
  92.     }
  93.  
  94.     return ans;
  95.   }
  96.  
  97.   uint32_t fast(uint32_t &n)
  98.   {
  99.     update(n, 0b11111111111111110000000000000000, 0b00000000000000001111111111111111, 16);
  100.     update(n, 0b11111111000000001111111100000000, 0b00000000111111110000000011111111, 8);
  101.     update(n, 0b11110000111100001111000011110000, 0b00001111000011110000111100001111, 4);
  102.     update(n, 0b11001100110011001100110011001100, 0b00110011001100110011001100110011, 2);
  103.     update(n, 0b10101010101010101010101010101010, 0b01010101010101010101010101010101, 1);
  104.  
  105.     return n;
  106.   }
  107.  
  108. private:
  109.   void update(uint32_t &n, uint32_t first, uint32_t last, int shift)
  110.   {
  111.     first = n & first;
  112.     last = n & last;
  113.     last <<= shift;
  114.     first >>= shift;
  115.     last |= first;
  116.     n = last;
  117.   }
  118. };
  119.  
  120. double time_taken(Solution *&sol, uint32_t &n, bool speed)
  121. {
  122.   // adapted from https://stackoverflow.com/a/728070
  123.   const clock_t begin_time = clock();
  124.   if (speed) sol->fast(n);
  125.   else sol->slow(n);
  126.  
  127.   return float(clock() - begin_time) / CLOCKS_PER_SEC;
  128. }
  129.  
  130. void benchmark()
  131. {
  132.   // Run for 1 million tries
  133.   Solution *sol = new Solution();
  134.   double slow = 0.0, fast = 0.0;
  135.  
  136.   FORI(i, 1, 1e6)
  137.   {
  138.     uint32_t n = rng();
  139.  
  140.     slow += time_taken(sol, n, 0); // sol->slow(n)
  141.     fast += time_taken(sol, n, 1); // sol->fast(n)
  142.   }
  143.  
  144.   delete sol;
  145.  
  146.   // Results
  147.   FORI(i, 1, 1e2) cout << "=";
  148.   cout << "\nRESULTS:\n";
  149.   FORI(i, 1, 1e2) cout << "=";
  150.   cout << "\n";
  151.  
  152.   cout << "Solution->slow(): " << slow << " seconds\n";
  153.   cout << "Solution->fast(): " << fast << " seconds\n";
  154. }
  155.  
  156. int main()
  157. {
  158.   benchmark();
  159.  
  160.   return 0;
  161. }
  162. */
Advertisement
RAW Paste Data Copied
Advertisement