Limit std::sort comparisons on small list

[François Dumont]

On 10/01/2013 11:35 PM, Paolo Carlini wrote:
> Hi,
>
>> Il giorno 01/ott/2013, alle ore 22:35, François Dumont<frs.dumont@gmail.com>  ha scritto:
>>
>>> On 09/30/2013 11:45 PM, Christopher Jefferson wrote:
>>>> Any ideas?
>>> This comes from way back in the SGI days by the look of things to me.
>>>
>>> The problem arises in __insertion_sort. The logic looks something like:
>>>
>>>   if (*__i < *__first)
>>> { Then *__i has to go all the way to the start of the array. Do that! }
>>> else
>>> { We don't know where *__i will go, but we know that if we start
>>> moving it back 1 square at a time, we will stop either at or before
>>> __first }
>>>
>>> That second part is __unguarded_linear_insert.
>>>
>>> In the case where actually *__i has to go all the way back to just
>>> after first, we do one comparison too many (we could stop one place
>>> before). However, the whole point of unguarded linear insert is that
>>> we are trading off one comparison to remove the need for a boundary
>>> condition check. We could add a check in the while of
>>> __unguarded_linear_insert of that form (__i > __first), but in many
>>> cases that would end up being more expensive than the comparisons,
>>> particularly because it is only in very rare cases that we expect to
>>> hit this case.
>>>
> Interesting, thanks. Numbers? Could you please see which numbers you get if you run the new performace test provided by Chris + variants of the subtest using pseudo-random numbers? I would say for shorter and longer lists and also averaging over a few different starting random seeds. In any case many repetitions to decresse the variance of the numbers. If/when you have something please send immediately over the tests themselves too: I know that even keeping fix the x86_64 architecture there are rather noticeable relative differences depending on the specific cpu, thus in any case I would like to run the same tests on my machines.
>
> Paolo
Note that this patch is not a solution to the problem explained by 
Christopher. It only avoids 1 comparison (and 2 moves) each time 
__insertion_sort is called without introducing more iterator comparison 
which is rather limited but rather safe too.

I tweak the performance test to make the result of the patch more obvious:

Without it I have:
sort.cc                      reverse 222097162 comparisons 29r   28u    
0s        0mem    0pf
sort.cc                      forwards 222433832 comparisons 28r   28u    
0s        0mem    0pf
sort.cc                      random 282514017 comparisons     102r 
102u    0s        0mem    0pf
stable_sort.cc               reverse 108815190 comparisons 58r   56u    
1s        0mem    0pf
stable_sort.cc               forwards 123367742 comparisons 50r   48u    
1s        0mem    0pf
stable_sort.cc               random 227422991 comparisons     130r 
129u    1s        0mem    0pf

With it I have:
sort.cc                      reverse 222097162 comparisons 27r   27u    
0s        0mem    0pf
sort.cc                      forwards 222433832 comparisons 27r   27u    
0s        0mem    0pf
sort.cc                      random 282514017 comparisons     103r 
102u    0s        0mem    0pf
stable_sort.cc               reverse 108815190 comparisons 58r   57u    
1s        0mem    0pf
stable_sort.cc               forwards 121939170 comparisons 51r   50u    
1s        0mem    0pf
stable_sort.cc               random 226708173 comparisons     130r 
129u    1s        0mem    0pf

So no impact on sort because the number of elements involved is too 
important. Good, even if limited, impact on stable_sort because it 
reduces the number of comparison by about 0.5% in the random case. I 
have added a test to check that on small number of elements it has the 
expected impact, only 1 comparison when 2 elements in the array.

I don't know if Christopher wants to give his opinion but what this 
patch does is only unrolling a for to deal with the first loop in a 
special way.

Tested under Linux x86_64.

2013-10-03  François Dumont  <fdumont@gcc.gnu.org>

     * include/bits/stl_algo.h (__insertion_sort): Avoid a redundant
     comparison.
     * testsuite/25_algorithms/sort/1.cc (test02): New.
     * testsuite/performance/25_algorithms/stable_sort.cc: Display
     number of comparisons within the report.
     * testsuite/performance/25_algorithms/sort.cc: Likewise.

François

-------------- next part --------------
A non-text attachment was scrubbed...
Name: sort.patch
Type: text/x-patch
Size: 6048 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20131003/cf1fb4cf/attachment.bin>