OSDN Git Service

2013-09-30 Chris Jefferson <chris@bubblescope.net>
authorpaolo <paolo@138bc75d-0d04-0410-961f-82ee72b054a4>
Mon, 30 Sep 2013 17:43:05 +0000 (17:43 +0000)
committerpaolo <paolo@138bc75d-0d04-0410-961f-82ee72b054a4>
Mon, 30 Sep 2013 17:43:05 +0000 (17:43 +0000)
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.

git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/branches/gcc-4_7-branch@203037 138bc75d-0d04-0410-961f-82ee72b054a4

libstdc++-v3/ChangeLog
libstdc++-v3/include/bits/stl_algo.h
libstdc++-v3/testsuite/performance/25_algorithms/sort.cc [new file with mode: 0644]
libstdc++-v3/testsuite/performance/25_algorithms/sort_heap.cc [new file with mode: 0644]
libstdc++-v3/testsuite/performance/25_algorithms/stable_sort.cc [new file with mode: 0644]

index 19707c2..d5aebe8 100644 (file)
@@ -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-26  Jonathan Wakely  <jwakely.gcc@gmail.com>
 
        Backport from mainline
index f337e0c..239b63c 100644 (file)
@@ -74,10 +74,11 @@ namespace std _GLIBCXX_VISIBILITY(default)
 {
 _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
-  /// Swaps the median value of *__a, *__b and *__c to *__a
+  /// Swaps the median value of *__a, *__b and *__c to *__result
   template<typename _Iterator>
     void
-    __move_median_first(_Iterator __a, _Iterator __b, _Iterator __c)
+    __move_median_to_first(_Iterator __result, _Iterator __a,
+                          _Iterator __b, _Iterator __c)
     {
       // concept requirements
       __glibcxx_function_requires(_LessThanComparableConcept<
@@ -86,23 +87,26 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       if (*__a < *__b)
        {
          if (*__b < *__c)
-           std::iter_swap(__a, __b);
+           std::iter_swap(__result, __b);
          else if (*__a < *__c)
-           std::iter_swap(__a, __c);
+           std::iter_swap(__result, __c);
+         else
+           std::iter_swap(__result, __a);
        }
       else if (*__a < *__c)
-       return;
+       std::iter_swap(__result, __a);
       else if (*__b < *__c)
-       std::iter_swap(__a, __c);
+       std::iter_swap(__result, __c);
       else
-       std::iter_swap(__a, __b);
+       std::iter_swap(__result, __b);
     }
 
-  /// 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)
     {
       // concept requirements
       __glibcxx_function_requires(_BinaryFunctionConcept<_Compare, bool,
@@ -112,16 +116,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       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);
     }
 
   // for_each
@@ -2305,7 +2311,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
                                _RandomAccessIterator __last)
     {
       _RandomAccessIterator __mid = __first + (__last - __first) / 2;
-      std::__move_median_first(__first, __mid, (__last - 1));
+      std::__move_median_to_first(__first, __first + 1, __mid, (__last - 2));
       return std::__unguarded_partition(__first + 1, __last, *__first);
     }
 
@@ -2317,7 +2323,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 (file)
index 0000000..07062ab
--- /dev/null
@@ -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 (file)
index 0000000..63cb224
--- /dev/null
@@ -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 (file)
index 0000000..6440eb3
--- /dev/null
@@ -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;
+}