std::includes performance tweak

[Marc Glisse]

Hello,

I am proposing a small tweak to the implementation of __includes, which in 
my application saves 20% of the running time. I noticed it because using 
range-v3 was giving unexpected performance gains.

The unified diff is attached, but let me first show a more readable 
context diff.

*** /tmp/zzm2NX_stl_algo.h	2020-06-19 10:48:58.702634366 +0200
--- libstdc++-v3/include/bits/stl_algo.h	2020-06-18 23:16:06.183427245 +0200
***************
*** 2783,2797 ****
   	       _Compare __comp)
       {
         while (__first1 != __last1 && __first2 != __last2)
! 	if (__comp(__first2, __first1))
! 	  return false;
! 	else if (__comp(__first1, __first2))
! 	  ++__first1;
! 	else
! 	  {
! 	    ++__first1;
   	    ++__first2;
! 	  }

         return __first2 == __last2;
       }
--- 2783,2795 ----
   	       _Compare __comp)
       {
         while (__first1 != __last1 && __first2 != __last2)
! 	{
! 	  if (__comp(__first2, __first1))
! 	    return false;
! 	  if (!__comp(__first1, __first2))
   	    ++__first2;
! 	  ++__first1;
! 	}

         return __first2 == __last2;
       }

As you can see, it isn't much change. Some of the gain comes from pulling 
the 2 calls ++__first1 out of the condition so there is just one call. And 
most of the gain comes from replacing the resulting

if (__comp(__first1, __first2))
   ;
else
   ++__first2;

with

if (!__comp(__first1, __first2))
   ++__first2;

I was very surprised that the code ended up being so different for such a 
change, and I still don't really understand where the extra time is 
going...

Anyway, while I blame the compiler for not generating very good code with 
the current implementation, I believe the change can be seen as a 
simplification and should be pushed to master. It regtests fine.

2020-06-20  Marc Glisse  <marc.glisse@inria.fr>

 	* include/bits/stl_algo.h (__includes): Simplify the code.

(as with the patch for std::optional, I still haven't worked on my ssh key 
issue and cannot currently push)

-- 
Marc Glisse
-------------- next part --------------
A non-text attachment was scrubbed...
Name: includes.patch
Type: text/x-diff
Size: 710 bytes
Desc: 
URL: <https://gcc.gnu.org/pipermail/gcc-patches/attachments/20200619/b936eab2/attachment.bin>