libstdc++: Limit memory allocation in stable_sort/inplace_merge (PR 83938)

Reduce memory allocation in stable_sort/inplace_merge algorithms to what is needed
by the implementation.

Co-authored-by: John Chang  <john.chang@samba.tv>

libstdc++-v3/ChangeLog:

	PR libstdc++/83938
	* include/bits/stl_tempbuf.h (get_temporary_buffer): Change __len
	computation in the loop to avoid truncation.
	* include/bits/stl_algo.h:
	(__inplace_merge): Take temporary buffer length from smallest range.
	(__stable_sort): Limit temporary buffer length.
	* testsuite/25_algorithms/inplace_merge/1.cc (test4): New.
	* testsuite/performance/25_algorithms/stable_sort.cc: Test stable_sort
	under different heap memory conditions.
	* testsuite/performance/25_algorithms/inplace_merge.cc: New test.

2 files changed, 364 insertions, 16 deletions

diff --git a/libstdc++-v3/testsuite/performance/25_algorithms/inplace_merge.cc b/libstdc++-v3/testsuite/performance/25_algorithms/inplace_merge.cc
new file mode 100644
index 00000000000..780c21912c7
--- /dev/null
+++ b/libstdc++-v3/testsuite/performance/25_algorithms/inplace_merge.cc
@@ -0,0 +1,290 @@
+// Copyright (C) 2020 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+#include <vector>
+#include <algorithm>
+#include <cmath>
+
+#include <testsuite_new_operators.h>
+#include <testsuite_performance.h>
+
+const int max_size = 10000000;
+const int small_size = 200000;
+const int front_pivot_idx = 10000;
+int middle_pivot_idx = max_size / 2;
+int back_pivot_idx = max_size - front_pivot_idx;
+
+void bench(int mem_threshold, int pivot_index,
+	   std::vector<int> revv,
+	   std::vector<int> fwdv,
+	   std::vector<int> wstv,
+	   std::vector<int> rndv)
+{
+  using namespace __gnu_test;
+
+  time_counter time;
+  resource_counter resource;
+
+  set_new_limit(mem_threshold);
+
+  start_counters(time, resource);
+  std::inplace_merge(revv.begin(), revv.begin() + pivot_index, revv.end());
+  stop_counters(time, resource);
+
+  set_new_limit(~size_t(0));
+
+  report_performance(__FILE__, "reverse", time, resource);
+  clear_counters(time, resource);
+
+  set_new_limit(mem_threshold);
+
+  start_counters(time, resource);
+  std::inplace_merge(fwdv.begin(), fwdv.begin() + pivot_index, fwdv.end());
+  stop_counters(time, resource);
+
+  set_new_limit(~size_t(0));
+
+  report_performance(__FILE__, "forward", time, resource);
+  clear_counters(time, resource);
+
+  set_new_limit(mem_threshold);
+
+  start_counters(time, resource);
+  std::inplace_merge(wstv.begin(), wstv.begin() + pivot_index, wstv.end());
+  stop_counters(time, resource);
+
+  set_new_limit(~size_t(0));
+
+  report_performance(__FILE__, "worst", time, resource);
+  clear_counters(time, resource);
+
+  set_new_limit(mem_threshold);
+
+  start_counters(time, resource);
+  std::inplace_merge(rndv.begin(), rndv.begin() + pivot_index, rndv.end());
+  stop_counters(time, resource);
+
+  set_new_limit(~size_t(0));
+  report_performance(__FILE__, "random", time, resource);
+}
+
+void mem_bench(double mem_ratio,
+	       const std::vector<int>& front_revv,
+	       const std::vector<int>& middle_revv,
+	       const std::vector<int>& back_revv,
+	       const std::vector<int>& fwdv,
+	       const std::vector<int>& front_wstv,
+	       const std::vector<int>& middle_wstv,
+	       const std::vector<int>& back_wstv,
+	       const std::vector<int>& front_rndv,
+	       const std::vector<int>& middle_rndv,
+	       const std::vector<int>& back_rndv)
+{
+  using namespace __gnu_test;
+
+  time_counter time;
+  resource_counter resource;
+
+  int max_mem = (int)std::ceil(front_pivot_idx * mem_ratio) * sizeof(int);
+  start_counters(time, resource);
+  bench(max_mem, front_pivot_idx, front_revv, fwdv, front_wstv, front_rndv);
+  stop_counters(time, resource);
+  report_performance(__FILE__, "front pivot", time, resource);
+  clear_counters(time, resource);
+
+  max_mem = (int)std::ceil(middle_pivot_idx * mem_ratio) * sizeof(int);
+  start_counters(time, resource);
+  bench(max_mem, middle_pivot_idx, middle_revv, fwdv, middle_wstv, middle_rndv);
+  stop_counters(time, resource);
+  report_performance(__FILE__, "middle pivot", time, resource);
+  clear_counters(time, resource);
+
+  max_mem = (int)std::ceil(front_pivot_idx * mem_ratio) * sizeof(int);
+  start_counters(time, resource);
+  bench(max_mem, back_pivot_idx, back_revv, fwdv, back_wstv, back_rndv);
+  stop_counters(time, resource);
+  report_performance(__FILE__, "back pivot", time, resource);
+}
+
+void init_reverse(std::vector<int>& v, size_t pivot_index)
+{
+  int val = 0;
+  for (size_t i = pivot_index; i != v.size(); ++i)
+    v[i] = val++;
+  for (size_t i = 0; i != pivot_index; ++i)
+    v[i] = val++;
+}
+
+void init_forward(std::vector<int>& v)
+{
+  int val = 0;
+  for (size_t i = 0; i != v.size(); ++i)
+    v[i] = val++;
+}
+
+void init_worst(std::vector<int>& v, size_t pivot_index)
+{
+  int val = 0;
+  if (pivot_index + 1 > v.size() / 2)
+    {
+      for (size_t i = 0; i != pivot_index; val += 2, ++i)
+	v[i] = val;
+      val = 1;
+    }
+  else
+    {
+      for (size_t i = pivot_index; i != v.size(); val += 2, ++i)
+	v[i] = val;
+      val -= pivot_index * 2 + 1;
+    }
+
+  if (pivot_index + 1 > v.size() / 2)
+    for (size_t i = pivot_index; i != v.size(); val += 2, ++i)
+      v[i] = val;
+  else
+    for (size_t i = 0; i != pivot_index; val += 2, ++i)
+      v[i] = val;
+}
+
+void init_random(std::vector<int>& v)
+{
+  // a simple pseudo-random series which does not rely on rand() and friends
+  v[0] = 0;
+  for (size_t i = 1; i != v.size(); ++i)
+    v[i] = (v[i-1] + 110211473) * 745988807;
+}
+
+void reduce_size(std::vector<int>& front_v,
+		 std::vector<int>& middle_v,
+		 std::vector<int>& back_v)
+{
+  front_v.erase(front_v.begin() + front_pivot_idx,
+		front_v.end() - back_pivot_idx);
+  middle_v.erase(middle_v.begin() + small_size / 2,
+		 middle_v.end() - small_size / 2);
+  back_v.erase(back_v.begin() + back_pivot_idx,
+	       back_v.end() - front_pivot_idx);
+}
+
+int main()
+{
+  using namespace __gnu_test;
+
+  // No constraint to build vectors.
+  set_new_limit(~size_t(0));
+
+  std::vector<int> front_revv(max_size);
+  init_reverse(front_revv, front_pivot_idx);
+
+  std::vector<int> middle_revv(max_size);
+  init_reverse(middle_revv, middle_pivot_idx);
+
+  std::vector<int> back_revv(max_size);
+  init_reverse(back_revv, back_pivot_idx);
+
+  std::vector<int> fwdv(max_size);
+  init_forward(fwdv);
+
+  std::vector<int> front_wstv(max_size);
+  init_worst(front_wstv, front_pivot_idx);
+
+  std::vector<int> middle_wstv(max_size);
+  init_worst(middle_wstv, middle_pivot_idx);
+
+  std::vector<int> back_wstv(max_size);
+  init_worst(back_wstv, back_pivot_idx);
+
+  std::vector<int> front_rndv(max_size);
+  init_random(front_rndv);
+  std::vector<int> middle_rndv(front_rndv);
+  std::vector<int> back_rndv(front_rndv);
+
+  sort(front_rndv.begin(), front_rndv.begin() + front_pivot_idx);
+  sort(front_rndv.begin() + front_pivot_idx, front_rndv.end());
+
+  sort(middle_rndv.begin(), middle_rndv.begin() + middle_pivot_idx);
+  sort(middle_rndv.begin() + middle_pivot_idx, middle_rndv.end());
+
+  sort(back_rndv.begin(), back_rndv.begin() + back_pivot_idx);
+  sort(back_rndv.begin() + back_pivot_idx, back_rndv.end());
+
+  time_counter time;
+  resource_counter resource;
+
+  start_counters(time, resource);
+
+  // No limit.
+  mem_bench(1.0,
+	    front_revv, middle_revv, back_revv,
+	    fwdv,
+	    front_wstv, middle_wstv, back_wstv,
+	    front_rndv, middle_rndv, back_rndv);
+
+  stop_counters(time, resource);
+
+  report_performance(__FILE__, "bench 1 / 1 memory", time, resource);
+  clear_counters(time, resource);
+
+  start_counters(time, resource);
+
+  // Limit to the fourth.
+  mem_bench(1.0 / 4,
+	    front_revv, middle_revv, back_revv,
+	    fwdv,
+	    front_wstv, middle_wstv, back_wstv,
+	    front_rndv, middle_rndv, back_rndv);
+
+  stop_counters(time, resource);
+
+  report_performance(__FILE__, "bench 1 / 4 memory", time, resource);
+  clear_counters(time, resource);
+
+  start_counters(time, resource);
+
+  // Really limit allocation.
+  mem_bench(1.0 / 64,
+	    front_revv, middle_revv, back_revv,
+	    fwdv,
+	    front_wstv, middle_wstv, back_wstv,
+	    front_rndv, middle_rndv, back_rndv);
+
+  stop_counters(time, resource);
+
+  report_performance(__FILE__, "bench 1 /64 memory", time, resource);
+  clear_counters(time, resource);
+
+  middle_pivot_idx = small_size / 2;
+  back_pivot_idx = small_size - front_pivot_idx;
+  reduce_size(front_revv, middle_revv, back_revv);
+  fwdv.resize(small_size);
+  reduce_size(front_wstv, middle_wstv, back_wstv);
+  reduce_size(front_rndv, middle_rndv, back_rndv);
+
+  start_counters(time, resource);
+
+  // No memory.
+  mem_bench(0.0,
+	    front_revv, middle_revv, back_revv,
+	    fwdv,
+	    front_wstv, middle_wstv, back_wstv,
+	    front_rndv, middle_rndv, back_rndv);
+
+  stop_counters(time, resource);
+
+  report_performance(__FILE__, "bench 0 / 1 memory", time, resource);
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/performance/25_algorithms/stable_sort.cc b/libstdc++-v3/testsuite/performance/25_algorithms/stable_sort.cc
index 02b869dd195..fe526638aaf 100644
--- a/libstdc++-v3/testsuite/performance/25_algorithms/stable_sort.cc
+++ b/libstdc++-v3/testsuite/performance/25_algorithms/stable_sort.cc
@@ -17,49 +17,107 @@
 
 #include <vector>
 #include <algorithm>
+
+#include <testsuite_new_operators.h>
 #include <testsuite_performance.h>
 
-int main()
+const int max_size = 10000000;
+const int small_size = 200000;
+
+void bench(size_t mem_threshold,
+	   std::vector<int> revv,
+	   std::vector<int> fwdv,
+	   std::vector<int> rndv)
 {
   using namespace __gnu_test;
 
   time_counter time;
   resource_counter resource;
 
-  const int max_size = 10000000;
-
-  std::vector<int> v(max_size);
-
-  for (int i = 0; i < max_size; ++i)
-    v[i] = -i;
+  set_new_limit(mem_threshold);
 
   start_counters(time, resource);
-  std::stable_sort(v.begin(), v.end());
+  std::stable_sort(revv.begin(), revv.end());
   stop_counters(time, resource);
 
+  set_new_limit(~size_t(0));
   report_performance(__FILE__, "reverse", time, resource);
   clear_counters(time, resource);
 
-  for (int i = 0; i < max_size; ++i)
-    v[i] = i;
+  set_new_limit(mem_threshold);
 
   start_counters(time, resource);
-  std::stable_sort(v.begin(), v.end());
+  std::stable_sort(fwdv.begin(), fwdv.end());
   stop_counters(time, resource);
 
+  set_new_limit(~size_t(0));
   report_performance(__FILE__, "forwards", time, resource);
   clear_counters(time, resource);
 
-  // a simple psuedo-random series which does not rely on rand() and friends
-  v[0] = 0;
+  start_counters(time, resource);
+  std::stable_sort(rndv.begin(), rndv.end());
+  stop_counters(time, resource);
+
+  set_new_limit(~size_t(0));
+  report_performance(__FILE__, "random", time, resource);
+}
+
+int main()
+{
+  using namespace __gnu_test;
+
+  // No memory constraint.
+  set_new_limit(~size_t(0));
+
+  std::vector<int> revv(max_size);
+  for (int i = 0; i < max_size; ++i)
+    revv[i] = -i;
+
+  std::vector<int> fwdv(max_size);
+  for (int i = 0; i < max_size; ++i)
+    fwdv[i] = i;
+
+  // a simple pseudo-random series which does not rely on rand() and friends
+  std::vector<int> rndv(max_size);
+  rndv[0] = 0;
   for (int i = 1; i < max_size; ++i)
-    v[i] = (v[i-1] + 110211473) * 745988807;
+    rndv[i] = (rndv[i-1] + 110211473) * 745988807;
+
+  time_counter time;
+  resource_counter resource;
 
   start_counters(time, resource);
-  std::stable_sort(v.begin(), v.end());
+  bench(~size_t(0), revv, fwdv, rndv);
   stop_counters(time, resource);
 
-  report_performance(__FILE__, "random", time, resource);
+  report_performance(__FILE__, "bench 1 / 1 memory", time, resource);
+  clear_counters(time, resource);
+
+  start_counters(time, resource);
+  // Limit to fourth the expected size of the sorted array.
+  bench(max_size * sizeof(int) / 4, revv, fwdv, rndv);
+  stop_counters(time, resource);
+
+  report_performance(__FILE__, "bench 1 / 4 memory", time, resource);
+  clear_counters(time, resource);
+
+  start_counters(time, resource);
+  // Limit to 1/64 of range size.
+  bench(max_size * sizeof(int) / 64, revv, fwdv, rndv);
+  stop_counters(time, resource);
+
+  report_performance(__FILE__, "bench 1 /64 memory", time, resource);
+  clear_counters(time, resource);
+
+  revv.resize(small_size);
+  fwdv.resize(small_size);
+  rndv.resize(small_size);
+
+  start_counters(time, resource);
+  // Forbid any allocation.
+  bench(0, revv, fwdv, rndv);
+  stop_counters(time, resource);
 
+  report_performance(__FILE__, "bench 0 / 1 memory", time, resource);
   return 0;
 }