std::includes performance tweak

Jonathan Wakely jwakely@redhat.com
Fri Jun 19 11:17:14 GMT 2020


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




More information about the Libstdc++ mailing list