Limit std::sort comparisons on small list

[François Dumont]

On 09/30/2013 11:45 PM, Christopher Jefferson wrote:
> On 30 September 2013 17:11, Paolo Carlini <paolo.carlini@oracle.com> wrote:
>> Hi,
>>
>>
>> On 09/29/2013 10:19 PM, Christopher Jefferson wrote:
>>> (we also perform 2 comparisons where one should be enough, but that's a
>>> different issue)
>>> That is worth looking at (although increasingly, I want to investigate
>>> doing a fresh sort altogether. In my own code I use an implementation
>>> of timsort, which shows much better performance where data is partly
>>> sorted. However, that's a different patch/discussion!)
>> It's definitely a different patch / discussion. What I'm trying to
>> understand is how old the issue is, whether is a relatively recent
>> regression or it's an old issue. Because the behavior seems first blush
>> really weird, but if it dates back to the HP / SGI times, it can probably
>> wait a bit more. 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.
>
> So the short version is: We do the extra value comparison on purpose,
> and taking it out will make the algorithm quite a lot more in iterator
> comparisions.
>
> We could add a special case std::sort for very small lists, for
> example up to size 4 or 5, and use a 'sort network'. Not sure how
> often these cases come up, and if it is worth the code bloat.
>
> Chris

If you don't mind I changed the subject as we all agree that the 
original discussion has changed.

I also had a look on my side and was about to propose this

Index: include/bits/stl_algo.h
===================================================================
--- include/bits/stl_algo.h    (revision 203080)
+++ include/bits/stl_algo.h    (working copy)
@@ -1850,6 +1850,8 @@
            _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
            *__first = _GLIBCXX_MOVE(__val);
          }
+      else if (__i == __first + 1)
+        continue;
        else
          std::__unguarded_linear_insert(__i,
                  __gnu_cxx::__ops::__val_comp_iter(__comp));


Calling __unguarded_linear_insert is useless as long as __i is just 
__first + 1. It doesn't only avoid a comparison but also two moves to 
put __i in a value_type instance and then back to __i again.

If you think this additional check is too expensive we could unroll the 
for loop in __insertion_sort to deal with __first + 1 outside of it and 
start the loop only at __first + 2. Something like this:

Index: include/bits/stl_algo.h
===================================================================
--- include/bits/stl_algo.h    (revision 203080)
+++ include/bits/stl_algo.h    (working copy)
@@ -1841,7 +1841,14 @@
      {
        if (__first == __last) return;

-      for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
+      _RandomAccessIterator __i = __first + 1;
+
+      if (__i == __last) return;
+
+      if (__comp(__i, __first))
+    std::iter_swap(__i, __first);
+
+      for (++__i; __i != __last; ++__i)
      {
        if (__comp(__i, __first))
          {


François