| Message ID | alpine.DEB.2.02.2006191247440.20750@stedding.saclay.inria.fr |
|---|---|
| State | New |
| Headers | show |
| Series | std::includes performance tweak | expand |
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).
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.
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; }
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)