libstdc++-v3/testsuite/performance/25_algorithms/stable_sort.cc

   1 // Copyright (C) 2013-2024 Free Software Foundation, Inc.
   2 //
   3 // This file is part of the GNU ISO C++ Library.  This library is free
   4 // software; you can redistribute it and/or modify it under the
   5 // terms of the GNU General Public License as published by the
   6 // Free Software Foundation; either version 3, or (at your option)
   7 // any later version.
   8
   9 // This library is distributed in the hope that it will be useful,
  10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 // GNU General Public License for more details.
  13
  14 // You should have received a copy of the GNU General Public License along
  15 // with this library; see the file COPYING3.  If not see
  16 // <http://www.gnu.org/licenses/>.
  17
  18 #include <vector>
  19 #include <algorithm>
  20
  21 #include <testsuite_new_operators.h>
  22 #include <testsuite_performance.h>
  23
  24 const int max_size = 10000000;
  25 const int small_size = 200000;
  26
  27 void bench(size_t mem_threshold,
  28            std::vector<int> revv,
  29            std::vector<int> fwdv,
  30            std::vector<int> rndv)
  31 {
  32   using namespace __gnu_test;
  33
  34   time_counter time;
  35   resource_counter resource;
  36
  37   set_new_limit(mem_threshold);
  38
  39   start_counters(time, resource);
  40   std::stable_sort(revv.begin(), revv.end());
  41   stop_counters(time, resource);
  42
  43   set_new_limit(~size_t(0));
  44   report_performance(__FILE__, "reverse", time, resource);
  45   clear_counters(time, resource);
  46
  47   set_new_limit(mem_threshold);
  48
  49   start_counters(time, resource);
  50   std::stable_sort(fwdv.begin(), fwdv.end());
  51   stop_counters(time, resource);
  52
  53   set_new_limit(~size_t(0));
  54   report_performance(__FILE__, "forwards", time, resource);
  55   clear_counters(time, resource);
  56
  57   start_counters(time, resource);
  58   std::stable_sort(rndv.begin(), rndv.end());
  59   stop_counters(time, resource);
  60
  61   set_new_limit(~size_t(0));
  62   report_performance(__FILE__, "random", time, resource);
  63 }
  64
  65 int main()
  66 {
  67   using namespace __gnu_test;
  68
  69   // No memory constraint.
  70   set_new_limit(~size_t(0));
  71
  72   std::vector<int> revv(max_size);
  73   for (int i = 0; i < max_size; ++i)
  74     revv[i] = -i;
  75
  76   std::vector<int> fwdv(max_size);
  77   for (int i = 0; i < max_size; ++i)
  78     fwdv[i] = i;
  79
  80   // a simple pseudo-random series which does not rely on rand() and friends
  81   std::vector<int> rndv(max_size);
  82   rndv[0] = 0;
  83   for (int i = 1; i < max_size; ++i)
  84     rndv[i] = (rndv[i-1] + 110211473) * 745988807;
  85
  86   time_counter time;
  87   resource_counter resource;
  88
  89   start_counters(time, resource);
  90   bench(~size_t(0), revv, fwdv, rndv);
  91   stop_counters(time, resource);
  92
  93   report_performance(__FILE__, "bench 1 / 1 memory", time, resource);
  94   clear_counters(time, resource);
  95
  96   start_counters(time, resource);
  97   // Limit to fourth the expected size of the sorted array.
  98   bench(max_size * sizeof(int) / 4, revv, fwdv, rndv);
  99   stop_counters(time, resource);
 100
 101   report_performance(__FILE__, "bench 1 / 4 memory", time, resource);
 102   clear_counters(time, resource);
 103
 104   start_counters(time, resource);
 105   // Limit to 1/64 of range size.
 106   bench(max_size * sizeof(int) / 64, revv, fwdv, rndv);
 107   stop_counters(time, resource);
 108
 109   report_performance(__FILE__, "bench 1 /64 memory", time, resource);
 110   clear_counters(time, resource);
 111
 112   revv.resize(small_size);
 113   fwdv.resize(small_size);
 114   rndv.resize(small_size);
 115
 116   start_counters(time, resource);
 117   // Forbid any allocation.
 118   bench(0, revv, fwdv, rndv);
 119   stop_counters(time, resource);
 120
 121   report_performance(__FILE__, "bench 0 / 1 memory", time, resource);
 122   return 0;
 123 }