re PR libstdc++/58437 (Sorting value in reverse order is much slower compare to gcc44)

2013-09-30  Chris Jefferson  <chris@bubblescope.net>

	PR libstdc++/58437
	* include/bits/stl_algo.h (__move_median_first): Rename to
	__move_median_to_first, change to take an addition argument.
	(__unguarded_partition_pivot): Adjust.
	* testsuite/performance/25_algorithms/sort.cc: New.
	* testsuite/performance/25_algorithms/sort_heap.cc: Likewise.
	* testsuite/performance/25_algorithms/stable_sort.cc: Likewise.

From-SVN: r203035

5 files changed, 246 insertions, 30 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index 7eba2be..a607185 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,3 +1,13 @@
+2013-09-30  Chris Jefferson  <chris@bubblescope.net>
+
+	PR libstdc++/58437
+	* include/bits/stl_algo.h (__move_median_first): Rename to
+	__move_median_to_first, change to take an addition argument.
+	(__unguarded_partition_pivot): Adjust.
+	* testsuite/performance/25_algorithms/sort.cc: New.
+	* testsuite/performance/25_algorithms/sort_heap.cc: Likewise.
+	* testsuite/performance/25_algorithms/stable_sort.cc: Likewise.
+
 2013-09-28  François Dumont  <fdumont@gcc.gnu.org>
 
 	* include/bits/stl_algo.h (remove_copy, remove_copy_if): Declare
@@ -607,23 +617,23 @@
 
 	* regex_automaton.h: Rearrange _NFA's layout.
 	* include/bits/regex_compiler.h: Add _AnyMatcher and _CharMatcher.
-	  Rearrange _BracketMatcher's layout.
-	  (_BracketMatcher<>::_M_add_char): Use set instead of vector for
-	  _M_char_set.
-	  (_BracketMatcher<>::_M_add_collating_element): Likewise.
-	  (_BracketMatcher<>::_M_make_range): Likewise.
+	Rearrange _BracketMatcher's layout.
+	(_BracketMatcher<>::_M_add_char): Use set instead of vector for
+	_M_char_set.
+	(_BracketMatcher<>::_M_add_collating_element): Likewise.
+	(_BracketMatcher<>::_M_make_range): Likewise.
 	* include/bits/regex_compiler.tcc (_Compiler<>::_M_atom): Use
-	  apropriate constructors of matchers above.
+	appropriate constructors of matchers above.
 	* testsuite/28_regex/algorithms/regex_match/ecma/char/anymatcher.cc:
-	  New.
+	New.
 	* testsuite/28_regex/algorithms/regex_match/ecma/char/backref.cc: New.
 	* testsuite/28_regex/algorithms/regex_match/ecma/char/empty_range.cc:
-	  New.
+	New.
 	* testsuite/28_regex/algorithms/regex_match/ecma/char/emptygroup.cc:
-	  New.
+	New.
 	* testsuite/28_regex/algorithms/regex_match/ecma/char/hex.cc: New.
 	* testsuite/28_regex/algorithms/regex_match/ecma/wchar_t/anymatcher.cc:
-	  New.
+	New.
 	* testsuite/28_regex/algorithms/regex_match/ecma/wchar_t/hex.cc: New.
 
 2013-08-30  François Dumont  <fdumont@gcc.gnu.org>
@@ -656,33 +666,33 @@
 2013-08-29  Tim Shen  <timshen91@gmail.com>
 
 	* include/bits/regex.h (basic_regex<>::assign): Don't lose _M_traits.
-	  (regex_iterator<>::regex_iterator): Return nullptr when regex_search
-	     failed.
-	  (regex_token_iterator<>::_M_end_of_seq): Should be defined true when
-	    _M_result is(not isn't) nullptr.
+	(regex_iterator<>::regex_iterator): Return nullptr when regex_search
+	failed.
+	(regex_token_iterator<>::_M_end_of_seq): Should be defined true when
+	_M_result is(not isn't) nullptr.
 	* include/bits/regex_compiler.h: Store _Compiler::_M_traits by reference
-	  instead of by value.
+	instead of by value.
 	* include/bits/regex_executor.h (_DFSExecutor<>::_DFSExecutor): Add
-	  _M_traits to _DFSExecutor.
+	_M_traits to _DFSExecutor.
 	* include/bits/regex_executor.tcc (__get_executor<>): Pass traits to
-	  _DFSExecutor too.
+	_DFSExecutor too.
 	* testsuite/28_regex/algorithms/regex_match/extended/wstring_locale.cc:
-	  New.
+	New.
 	* testsuite/28_regex/iterators/regex_token_iterator/wchar_t/
-	  wstring_02.cc: New.
+	wstring_02.cc: New.
 
 2013-08-26  Tim Shen  <timshen91@gmail.com>
 
 	* include/Makefile.am: Add regex_scanner.{h,tcc}.
 	* include/Makefile.in: Regenerate.
 	* include/bits/regex.h (match_search): Handle the `__first == __last`
-	  situation correctly.
+	situation correctly.
 	* include/bits/regex_compiler.h: Move _Scanner...
 	* include/bits/regex_scanner.h: ...to here. New.
 	* include/bits/regex_compiler.tcc: Move _Scanner...
 	* include/bits/regex_scanner.tcc: ...to here, too. New.
 	* include/bits/regex_executor.tcc: Use value instead of reference for
-	  submatch.
+	submatch.
 	* include/std/regex: Add regex_scanner.h
 	* testsuite/28_regex/algorithms/regex_match/awk/cstring_01.cc: New.
 	* testsuite/28_regex/algorithms/regex_match/basic/empty_range.cc: New.
diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h
index efd7998..51cbfee 100644
--- a/libstdc++-v3/include/bits/stl_algo.h
+++ b/libstdc++-v3/include/bits/stl_algo.h
@@ -72,25 +72,27 @@ namespace std _GLIBCXX_VISIBILITY(default)
 {
 _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
-  /// Swaps the median value of *__a, *__b and *__c under __comp to *__a
+  /// Swaps the median value of *__a, *__b and *__c under __comp to *__result
   template<typename _Iterator, typename _Compare>
     void
-    __move_median_first(_Iterator __a, _Iterator __b, _Iterator __c,
-			_Compare __comp)
+    __move_median_to_first(_Iterator __result,_Iterator __a, _Iterator __b,
+			   _Iterator __c, _Compare __comp)
     {
       if (__comp(__a, __b))
 	{
 	  if (__comp(__b, __c))
-	    std::iter_swap(__a, __b);
+	    std::iter_swap(__result, __b);
 	  else if (__comp(__a, __c))
-	    std::iter_swap(__a, __c);
+	    std::iter_swap(__result, __c);
+	  else
+	    std::iter_swap(__result, __a);
 	}
       else if (__comp(__a, __c))
-	return;
+	std::iter_swap(__result, __a);
       else if (__comp(__b, __c))
-	std::iter_swap(__a, __c);
+	std::iter_swap(__result, __c);
       else
-	std::iter_swap(__a, __b);
+	std::iter_swap(__result, __b);
     }
 
   /// This is an overload used by find algos for the Input Iterator case.
@@ -1915,7 +1917,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 				_RandomAccessIterator __last, _Compare __comp)
     {
       _RandomAccessIterator __mid = __first + (__last - __first) / 2;
-      std::__move_median_first(__first, __mid, (__last - 1), __comp);
+      std::__move_median_to_first(__first, __first + 1, __mid, (__last - 2),
+				  __comp);
       return std::__unguarded_partition(__first + 1, __last, __first, __comp);
     }
 
diff --git a/libstdc++-v3/testsuite/performance/25_algorithms/sort.cc b/libstdc++-v3/testsuite/performance/25_algorithms/sort.cc
new file mode 100644
index 0000000..07062ab
--- /dev/null
+++ b/libstdc++-v3/testsuite/performance/25_algorithms/sort.cc
@@ -0,0 +1,65 @@
+// Copyright (C) 2013 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 <testsuite_performance.h>
+
+int main()
+{
+  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;
+
+  start_counters(time, resource);
+  std::sort(v.begin(), v.end());
+  stop_counters(time, resource);
+
+  report_performance(__FILE__, "reverse", time, resource);
+  clear_counters(time, resource);
+
+  for (int i = 0; i < max_size; ++i)
+    v[i] = i;
+
+  start_counters(time, resource);
+  std::sort(v.begin(), v.end());
+  stop_counters(time, resource);
+
+  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;
+  for (int i = 1; i < max_size; ++i)
+    v[i] = (v[i-1] + 110211473) * 745988807;
+
+  start_counters(time, resource);
+  std::sort(v.begin(), v.end());
+  stop_counters(time, resource);
+
+  report_performance(__FILE__, "random", time, resource);
+
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/performance/25_algorithms/sort_heap.cc b/libstdc++-v3/testsuite/performance/25_algorithms/sort_heap.cc
new file mode 100644
index 0000000..63cb224
--- /dev/null
+++ b/libstdc++-v3/testsuite/performance/25_algorithms/sort_heap.cc
@@ -0,0 +1,73 @@
+// Copyright (C) 2013 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 <testsuite_performance.h>
+
+int main()
+{
+  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;
+
+  start_counters(time, resource);
+  std::make_heap(v.begin(), v.end());
+  stop_counters(time, resource);
+
+  report_performance(__FILE__, "make_heap_reverse", time, resource);
+  clear_counters(time, resource);
+
+  for (int i = 0; i < max_size; ++i)
+    v[i] = i;
+
+  start_counters(time, resource);
+  std::make_heap(v.begin(), v.end());
+  stop_counters(time, resource);
+
+  report_performance(__FILE__, "make_heap_forwards", time, resource);
+  clear_counters(time, resource);
+
+  // a simple psuedo-random series which does not rely on rand() and friends
+  v[0] = 0;
+  for (int i = 1; i < max_size; ++i)
+    v[i] = (v[i-1] + 110211473) * 745988807;
+
+  start_counters(time, resource);
+  std::make_heap(v.begin(), v.end());
+  stop_counters(time, resource);
+
+  report_performance(__FILE__, "make_heap_random", time, resource);
+
+
+  start_counters(time, resource);
+  std::sort_heap(v.begin(), v.end());
+  stop_counters(time, resource);
+
+  report_performance(__FILE__, "sort_heap", time, resource);
+  clear_counters(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
new file mode 100644
index 0000000..6440eb3
--- /dev/null
+++ b/libstdc++-v3/testsuite/performance/25_algorithms/stable_sort.cc
@@ -0,0 +1,65 @@
+// Copyright (C) 2013 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 <testsuite_performance.h>
+
+int main()
+{
+  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;
+
+  start_counters(time, resource);
+  std::stable_sort(v.begin(), v.end());
+  stop_counters(time, resource);
+
+  report_performance(__FILE__, "reverse", time, resource);
+  clear_counters(time, resource);
+
+  for (int i = 0; i < max_size; ++i)
+    v[i] = i;
+
+  start_counters(time, resource);
+  std::stable_sort(v.begin(), v.end());
+  stop_counters(time, resource);
+
+  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;
+  for (int i = 1; i < max_size; ++i)
+    v[i] = (v[i-1] + 110211473) * 745988807;
+
+  start_counters(time, resource);
+  std::stable_sort(v.begin(), v.end());
+  stop_counters(time, resource);
+
+  report_performance(__FILE__, "random", time, resource);
+
+  return 0;
+}