Re: std::includes performance tweak
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 * 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.
Re: std::includes performance tweak
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.h2020-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
* 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).
std::includes performance tweak
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.h2020-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
* 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;
}
