Index: include/bits/stl_algo.h =================================================================== --- include/bits/stl_algo.h (revision 202752) +++ include/bits/stl_algo.h (working copy) @@ -72,10 +72,11 @@ { _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 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< @@ -84,23 +85,26 @@ 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 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, @@ -110,16 +114,18 @@ 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 @@ -2273,7 +2279,7 @@ _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); } @@ -2285,7 +2291,8 @@ _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); } Index: testsuite/performance/25_algorithms/sort.cc =================================================================== --- testsuite/performance/25_algorithms/sort.cc (revision 0) +++ testsuite/performance/25_algorithms/sort.cc (working copy) @@ -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 +// . + +#include +#include +#include + +int main() +{ + using namespace __gnu_test; + + time_counter time; + resource_counter resource; + + const int max_size = 10000000; + + std::vector 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; +} Index: testsuite/performance/25_algorithms/sort_heap.cc =================================================================== --- testsuite/performance/25_algorithms/sort_heap.cc (revision 0) +++ testsuite/performance/25_algorithms/sort_heap.cc (working copy) @@ -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 +// . + +#include +#include +#include + +int main() +{ + using namespace __gnu_test; + + time_counter time; + resource_counter resource; + + const int max_size = 10000000; + + std::vector 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; +} Index: testsuite/performance/25_algorithms/stable_sort.cc =================================================================== --- testsuite/performance/25_algorithms/stable_sort.cc (revision 0) +++ testsuite/performance/25_algorithms/stable_sort.cc (working copy) @@ -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 +// . + +#include +#include +#include + +int main() +{ + using namespace __gnu_test; + + time_counter time; + resource_counter resource; + + const int max_size = 10000000; + + std::vector 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; +}