std::includes performance tweak

Message ID alpine.DEB.2.02.2006191247440.20750@stedding.saclay.inria.fr
State New
Headers show
Series
  • std::includes performance tweak
Related show

Commit Message

Marc Glisse June 19, 2020, 10:49 a.m.
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

Comments

Christophe Lyon via Gcc-patches June 19, 2020, 11:17 a.m. | #1
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.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)


Thanks, I'll take care of it (and the std::optional one which I still
haven't done).
Christophe Lyon via Gcc-patches June 19, 2020, 12:04 p.m. | #2
On 19/06/20 12:17 +0100, Jonathan Wakely wrote:
>On 19/06/20 12:49 +0200, Marc Glisse wrote:

>>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)

>

>Thanks, I'll take care of it (and the std::optional one which I still

>haven't done).


Pushed to master as r11-1554 465520e3eb45d83ad18394aa537150bfa6bdf117

Thanks again.

Patch

diff --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;
     }