Re: std::includes performance tweak

[Jonathan Wakely via Gcc-patches]

On 19/06/20 12:49 +0200, Marc Glisse wrote:

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)

Thanks, I'll take care of it (and the std::optional one which I still
haven't done).