[Bug libstdc++/57916] New: Improve std::sort paritioning by explicitly employing the pivot

[Bug libstdc++/57916] New: Improve std::sort paritioning by explicitly employing the pivot

[alexey.tourbin at gmail dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57916

            Bug ID: 57916
           Summary: Improve std::sort paritioning by explicitly employing
                    the pivot
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: enhancement
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: alexey.tourbin at gmail dot com

Created attachment 30515
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=30515&action=edit
Move the median back to its pivot position. Exclude the pivot from further
partitioning.

In the original SGI code, partitioning does not use the concept of pivot
explicitly.  The routine __unguarded_partition(first, last, pivot) only cuts
the sequence into two halves: [ <= pivot | >= pivot].  Note that the actual
pivot element used for partitioning can end up anywhere within the sequence,
not necessarily adjacent to the cut point.  (Also, note that the name
"__unguarded" indicates that certain boundary checks are omitted, which places
some restrictions on how the pivot can be selected.)

In 2009, Chris Jefferson introduced a new helper function,
__unguarded_partition_pivot(first, last) which calls __unguarded_partition
using the median of 3 elements as a pivot.  The median is actually placed into
the first element of the sequence and excluded from partitioning: [pivot| <=
pivot | >= pivot].  (Since this pivot selection scheme satisfies the
restrictions placed by __unguarded_partition, the "__unguarded" part ought to
be excluded from the name of this helper function.)

However, when partitioning is finished, this helper routine does NOT install
the pivot back to its final position: [ <= pivot | pivot | >= pivot ]. 
Although it can be argued that the resulting code is still correct, it does not
follow the common practice and misses an opportunity for optimization.  Indeed,
by installing the pivot back to its final position, we can exclude it from
further partitioning stages.  Although the change is small, it propagates
throughout partitioning tree and produces a cumulative effect.  Measurements
show (see below) that this change improves std::sort running time by 2% to %3.

The same technique of excluding the pivot can also be applied to __introselect
helper function (used to implement the nth_element routine).  Actually we can
check whether the pivot returned by partitioning is exactly the nth element,
and return immediately in this case.  Although an improvement in running time,
if any, is hard to measure, there is an important special case: when the
nth_element is used to select the middle element of the sequence, and the
sequence is already sorted, only one partitioning stage will be executed.

I use the following program to evaluate the effect on the running time of
std::sort.

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#define N (64 << 20)
int a[N];
int main()
{
    for (size_t i = 0; i < N; i++)
        a[i] = rand();
    std::time_t start = std::clock();
    std::sort(a, a + N);
    std::cout << (clock() - start) / (double) CLOCKS_PER_SEC << std::endl;
    return 0;
}

(before the change)
$ g++ -O2 test-sort.cc && ./a.out
9.48

(after the change)
$ g++ -I. -O2 test-sort.cc && ./a.out
9.29

Callgrind annotations also indicate an improvement - the number of instruction
reads has actually dropped by 10%!

(before this change)
16,344,046,167  PROGRAM TOTALS
10,249,743,434  ???:void std::__introsort_loop<int*, long>(int*, int*, long)'2
 2,263,595,692  ???:main
 1,742,665,662  /usr/src/debug/glibc-2.17-alt5/stdlib/random_r.c:random_r
 1,140,850,688  /usr/src/debug/glibc-2.17-alt5/stdlib/random.c:random
   677,198,672  ???:void std::__introsort_loop<int*, long>(int*, int*, long)
   268,435,456  /usr/src/debug/glibc-2.17-alt5/stdlib/rand.c:rand

(after the change)
14,976,731,729  PROGRAM TOTALS
9,180,509,971  ???:void std::__introsort_loop<int*, long>(int*, int*, long)'2
2,110,233,226  ???:main
1,742,665,662  /usr/src/debug/glibc-2.17-alt5/stdlib/random_r.c:random_r
1,140,850,688  /usr/src/debug/glibc-2.17-alt5/stdlib/random.c:random
  532,670,993  ???:void std::__introsort_loop<int*, long>(int*, int*, long)
  268,435,456  /usr/src/debug/glibc-2.17-alt5/stdlib/rand.c:rand

[Bug libstdc++/57916] Improve std::sort paritioning by explicitly employing the pivot

[redi at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57916

--- Comment #1 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Thanks for the patch, do you have a GCC opyright assignment in place?

Please see
http://gcc.gnu.org/onlinedocs/libstdc++/manual/appendix_contributing.html#list.copyright
for details on contributing.

[Bug libstdc++/57916] Improve std::sort paritioning by explicitly employing the pivot

[alexey.tourbin at gmail dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57916

--- Comment #2 from Alexey Tourbin <alexey.tourbin at gmail dot com> ---
> Thanks for the patch, do you have a GCC opyright assignment in place?

I don't have a copyright assignmet, but I'm willing to undergo the procedure
(and perhaps to sign an assignment for all future changes).  So how do I
proceed?

[Bug libstdc++/57916] Improve std::sort partitioning by explicitly employing the pivot

[paolo.carlini at oracle dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57916

Paolo Carlini <paolo.carlini at oracle dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|Improve std::sort           |Improve std::sort
                   |paritioning by explicitly   |partitioning by explicitly
                   |employing the pivot         |employing the pivot

--- Comment #3 from Paolo Carlini <paolo.carlini at oracle dot com> ---
I'm sending you privately the forms.

[Bug libstdc++/57916] Improve std::sort partitioning by explicitly employing the pivot

[paolo.carlini at oracle dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57916

--- Comment #4 from Paolo Carlini <paolo.carlini at oracle dot com> ---
Alexey I sent you the questionnaire on July, 21st. Did you get it?

[Bug libstdc++/57916] Improve std::sort partitioning by explicitly employing the pivot

[chris at bubblescope dot net]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57916

Chris Jefferson <chris at bubblescope dot net> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |chris at bubblescope dot net

--- Comment #5 from Chris Jefferson <chris at bubblescope dot net> ---
I have not carefully analysed this, but it might be worth changing the names of
methods you change if interaction between the old and new methods could break
std::sort, as when code compiled using different versions of the library is
linked, the linker will choose one version of each function at random.

As I say, I haven't looked carefully enough to see if this is a real problem
(sorry).