[committed] libstdc++: Micro-optimisations for lexicographical_compare_three_way

Message ID 20200303110905.GA2916923@redhat.com
State New
Headers show
Series
  • [committed] libstdc++: Micro-optimisations for lexicographical_compare_three_way
Related show

Commit Message

Jonathan Wakely March 3, 2020, 11:09 a.m.
As noted in LWG 3410 the specification in the C++20 draft performs more
iterator comparisons than necessary when the end of either range is
reached. Our implementation followed that specification. This removes
the redundant comparisons so that we do no unnecessary work as soon as
we find that we've reached the end of either range.

The odd-looking return statement is because it generates better code
than the original version that copied the global constants.

	* include/bits/stl_algobase.h (lexicographical_compare_three_way):
	Avoid redundant iterator comparisons (LWG 3410).

Tested powerpc64le-linux, committed to master.
commit 9b4f00dd3f799337d8b8ef5e79f5a682c8059ab9
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Tue Mar 3 11:06:26 2020 +0000

    libstdc++: Micro-optimisations for lexicographical_compare_three_way
    
    As noted in LWG 3410 the specification in the C++20 draft performs more
    iterator comparisons than necessary when the end of either range is
    reached. Our implementation followed that specification. This removes
    the redundant comparisons so that we do no unnecessary work as soon as
    we find that we've reached the end of either range.
    
    The odd-looking return statement is because it generates better code
    than the original version that copied the global constants.
    
            * include/bits/stl_algobase.h (lexicographical_compare_three_way):
            Avoid redundant iterator comparisons (LWG 3410).

Patch

diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h
index 7a9d932b421..4b63086965d 100644
--- a/libstdc++-v3/include/bits/stl_algobase.h
+++ b/libstdc++-v3/include/bits/stl_algobase.h
@@ -1711,15 +1711,16 @@  _GLIBCXX_BEGIN_NAMESPACE_ALGO
 		return __lencmp;
 	      }
 #endif // is_constant_evaluated
-      while (__first1 != __last1 && __first2 != __last2)
+      while (__first1 != __last1)
 	{
+	  if (__first2 == __last2)
+	    return strong_ordering::greater;
 	  if (auto __cmp = __comp(*__first1, *__first2); __cmp != 0)
 	    return __cmp;
 	  ++__first1;
 	  ++__first2;
 	}
-      return __first1 != __last1 ? strong_ordering::greater
-	: __first2 != __last2 ? strong_ordering::less : strong_ordering::equal;
+      return (__first2 == __last2) <=> true; // See PR 94006
     }
 
   template<typename _InputIter1, typename _InputIter2>