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.gli...@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 Glissediff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h
index fd6edd0d5f4..550a15f2b3b 100644
--- a/libstdc++-v3/include/bits/stl_algo.h
+++ b/libstdc++-v3/include/bits/stl_algo.h
@@ -2783,15 +2783,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	       _Compare __comp)
     {
       while (__first1 != __last1 && __first2 != __last2)
-	if (__comp(__first2, __first1))
-	  return false;
-	else if (__comp(__first1, __first2))
-	  ++__first1;
-	else
-	  {
-	    ++__first1;
+	{
+	  if (__comp(__first2, __first1))
+	    return false;
+	  if (!__comp(__first1, __first2))
 	    ++__first2;
-	  }
+	  ++__first1;
+	}
 
       return __first2 == __last2;
     }