public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
* [PATCH] Simplify branching in algos
@ 2021-05-27  5:04 François Dumont
       [not found] ` <YL+LEU/o0E4UOlIi@redhat.com>
  0 siblings, 1 reply; 4+ messages in thread
From: François Dumont @ 2021-05-27  5:04 UTC (permalink / raw)
  To: libstdc++; +Cc: gcc-patches

[-- Attachment #1: Type: text/plain, Size: 911 bytes --]

Following latest fixes in std::inplace_merge and std::stable_sort you 
propose Jonathan to enhance branching in the first.

Here is a proposal based on yours to do so in both algos.

     libstdc++: Enhance branching in std::inplace_merge and std::stable_sort

     libstdc++-v3/ChangeLog:

             * include/bits/stl_algo.h
             (__merge_adaptive): Adapt to merge only when buffer is 
large enough..
             (__merge_adaptive_resize): New, adapt merge when buffer is 
too small.
             (__inplace_merge): Adapt, use latter.
             (__stable_sort_adaptive): Adapt to sort only when buffer is 
large enough.
             (__stable_sort_adaptive_resize): New, adapt sort when 
buffer is too small.
             (__stable_sort): Adapt, use latter.

Tested under Linux x64.

Ok to commit ?

François


[-- Attachment #2: algo.patch --]
[-- Type: text/x-patch, Size: 6687 bytes --]

diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h
index a18bb000d0c..02ae40c1fb4 100644
--- a/libstdc++-v3/include/bits/stl_algo.h
+++ b/libstdc++-v3/include/bits/stl_algo.h
@@ -2401,28 +2401,42 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     }
 
   /// This is a helper function for the merge routines.
-  template<typename _BidirectionalIterator, typename _Distance, 
+  template<typename _BidirectionalIterator, typename _Distance,
 	   typename _Pointer, typename _Compare>
     void
     __merge_adaptive(_BidirectionalIterator __first,
 		     _BidirectionalIterator __middle,
 		     _BidirectionalIterator __last,
 		     _Distance __len1, _Distance __len2,
-		     _Pointer __buffer, _Distance __buffer_size,
-		     _Compare __comp)
+		     _Pointer __buffer, _Compare __comp)
     {
-      if (__len1 <= __len2 && __len1 <= __buffer_size)
+      if (__len1 <= __len2)
 	{
 	  _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
 	  std::__move_merge_adaptive(__buffer, __buffer_end, __middle, __last,
 				     __first, __comp);
 	}
-      else if (__len2 <= __buffer_size)
+      else
 	{
 	  _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
 	  std::__move_merge_adaptive_backward(__first, __middle, __buffer,
 					      __buffer_end, __last, __comp);
 	}
+    }
+
+  template<typename _BidirectionalIterator, typename _Distance,
+	   typename _Pointer, typename _Compare>
+    void
+    __merge_adaptive_resize(_BidirectionalIterator __first,
+			    _BidirectionalIterator __middle,
+			    _BidirectionalIterator __last,
+			    _Distance __len1, _Distance __len2,
+			    _Pointer __buffer, _Distance __buffer_size,
+			    _Compare __comp)
+    {
+      if (__len1 <= __buffer_size || __len2 <= __buffer_size)
+	std::__merge_adaptive(__first, __middle, __last,
+			      __len1, __len2, __buffer, __comp);
       else
 	{
 	  _BidirectionalIterator __first_cut = __first;
@@ -2450,14 +2464,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
 	  _BidirectionalIterator __new_middle
 	    = std::__rotate_adaptive(__first_cut, __middle, __second_cut,
-				     __len1 - __len11, __len22, __buffer,
-				     __buffer_size);
-	  std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
-				__len22, __buffer, __buffer_size, __comp);
-	  std::__merge_adaptive(__new_middle, __second_cut, __last,
-				__len1 - __len11,
-				__len2 - __len22, __buffer,
-				__buffer_size, __comp);
+				     __len1 - __len11, __len22,
+				     __buffer, __buffer_size);
+	  std::__merge_adaptive_resize(__first, __first_cut, __new_middle,
+				       __len11, __len22,
+				       __buffer, __buffer_size, __comp);
+	  std::__merge_adaptive_resize(__new_middle, __second_cut, __last,
+				       __len1 - __len11, __len2 - __len22,
+				       __buffer, __buffer_size, __comp);
 	}
     }
 
@@ -2535,11 +2549,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       // [first,middle) and [middle,last).
       _TmpBuf __buf(__first, std::min(__len1, __len2));
 
-      if (__buf.begin() == 0)
+      if (__builtin_expect(__buf.size() == __buf.requested_size(), true))
+	std::__merge_adaptive
+	  (__first, __middle, __last, __len1, __len2, __buf.begin(), __comp);
+      else if (__builtin_expect(__buf.begin() == 0, false))
 	std::__merge_without_buffer
 	  (__first, __middle, __last, __len1, __len2, __comp);
       else
-	std::__merge_adaptive
+	std::__merge_adaptive_resize
 	  (__first, __middle, __last, __len1, __len2, __buf.begin(),
 	   _DistanceType(__buf.size()), __comp);
     }
@@ -2720,34 +2737,45 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	}
     }
 
-  template<typename _RandomAccessIterator, typename _Pointer,
-	   typename _Distance, typename _Compare>
+  template<typename _RandomAccessIterator, typename _Pointer, typename _Compare>
     void
     __stable_sort_adaptive(_RandomAccessIterator __first,
+			   _RandomAccessIterator __middle,
 			   _RandomAccessIterator __last,
-			   _Pointer __buffer, _Distance __buffer_size,
-			   _Compare __comp)
+			   _Pointer __buffer, _Compare __comp)
+    {
+      std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
+      std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
+
+      std::__merge_adaptive(__first, __middle, __last,
+			    __middle - __first, __last - __middle,
+			    __buffer, __comp);
+    }
+
+  template<typename _RandomAccessIterator, typename _Pointer,
+	   typename _Distance, typename _Compare>
+    void
+    __stable_sort_adaptive_resize(_RandomAccessIterator __first,
+				  _RandomAccessIterator __last,
+				  _Pointer __buffer, _Distance __buffer_size,
+				  _Compare __comp)
     {
       const _Distance __len = (__last - __first + 1) / 2;
       const _RandomAccessIterator __middle = __first + __len;
       if (__len > __buffer_size)
 	{
-	  std::__stable_sort_adaptive(__first, __middle, __buffer,
-				      __buffer_size, __comp);
-	  std::__stable_sort_adaptive(__middle, __last, __buffer,
-				      __buffer_size, __comp);
+	  std::__stable_sort_adaptive_resize(__first, __middle, __buffer,
+					     __buffer_size, __comp);
+	  std::__stable_sort_adaptive_resize(__middle, __last, __buffer,
+					     __buffer_size, __comp);
+	  std::__merge_adaptive_resize(__first, __middle, __last,
+				       _Distance(__middle - __first),
+				       _Distance(__last - __middle),
+				       __buffer, __buffer_size,
+				       __comp);
 	}
       else
-	{
-	  std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
-	  std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
-	}
-
-      std::__merge_adaptive(__first, __middle, __last,
-			    _Distance(__middle - __first),
-			    _Distance(__last - __middle),
-			    __buffer, __buffer_size,
-			    __comp);
+	__stable_sort_adaptive(__first, __middle, __last, __buffer, __comp);
     }
 
   /// This is a helper function for the stable sorting routines.
@@ -5017,11 +5045,14 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
       // so the buffer only needs to fit half the range at once.
       _TmpBuf __buf(__first, (__last - __first + 1) / 2);
 
-      if (__buf.begin() == 0)
+      if (__builtin_expect(__buf.requested_size() == __buf.size(), true))
+	std::__stable_sort_adaptive(__first, __first + __buf.size(), __last,
+				    __buf.begin(), __comp);
+      else if (__builtin_expect(__buf.begin() == 0, false))
 	std::__inplace_stable_sort(__first, __last, __comp);
       else
-	std::__stable_sort_adaptive(__first, __last, __buf.begin(),
-				    _DistanceType(__buf.size()), __comp);
+	std::__stable_sort_adaptive_resize(__first, __last, __buf.begin(),
+					   _DistanceType(__buf.size()), __comp);
     }
 
   /**

^ permalink raw reply	[flat|nested] 4+ messages in thread

* Re: [PATCH] Simplify branching in algos
       [not found] ` <YL+LEU/o0E4UOlIi@redhat.com>
@ 2021-11-21 20:34   ` François Dumont
  2022-07-18 10:25     ` François Dumont
  0 siblings, 1 reply; 4+ messages in thread
From: François Dumont @ 2021-11-21 20:34 UTC (permalink / raw)
  To: Jonathan Wakely, libstdc++; +Cc: gcc-patches

[-- Attachment #1: Type: text/plain, Size: 10603 bytes --]

A recent thread on this mailing list made me remember that this proposal 
is still open.

I've updated it just to add a missing std qualification.

François

On 08/06/21 5:21 pm, Jonathan Wakely wrote:
> I haven't forgotten this one, I just need to double-check that we
> don't create another problem like std::rotate in 9.1
>
> I'll try to finish the review tomorrow.
>
> J.
>
>
> On 27/05/21 07:04 +0200, François Dumont via Libstdc++ wrote:
>> Following latest fixes in std::inplace_merge and std::stable_sort you 
>> propose Jonathan to enhance branching in the first.
>>
>> Here is a proposal based on yours to do so in both algos.
>>
>>     libstdc++: Enhance branching in std::inplace_merge and 
>> std::stable_sort
>>
>>     libstdc++-v3/ChangeLog:
>>
>>             * include/bits/stl_algo.h
>>             (__merge_adaptive): Adapt to merge only when buffer is 
>> large enough..
>>             (__merge_adaptive_resize): New, adapt merge when buffer 
>> is too small.
>>             (__inplace_merge): Adapt, use latter.
>>             (__stable_sort_adaptive): Adapt to sort only when buffer 
>> is large enough.
>>             (__stable_sort_adaptive_resize): New, adapt sort when 
>> buffer is too small.
>>             (__stable_sort): Adapt, use latter.
>>
>> Tested under Linux x64.
>>
>> Ok to commit ?
>>
>> François
>>
>
>> diff --git a/libstdc++-v3/include/bits/stl_algo.h 
>> b/libstdc++-v3/include/bits/stl_algo.h
>> index a18bb000d0c..02ae40c1fb4 100644
>> --- a/libstdc++-v3/include/bits/stl_algo.h
>> +++ b/libstdc++-v3/include/bits/stl_algo.h
>> @@ -2401,28 +2401,42 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>>     }
>>
>>   /// This is a helper function for the merge routines.
>> -  template<typename _BidirectionalIterator, typename _Distance, +  
>> template<typename _BidirectionalIterator, typename _Distance,
>>        typename _Pointer, typename _Compare>
>>     void
>>     __merge_adaptive(_BidirectionalIterator __first,
>>              _BidirectionalIterator __middle,
>>              _BidirectionalIterator __last,
>>              _Distance __len1, _Distance __len2,
>> -             _Pointer __buffer, _Distance __buffer_size,
>> -             _Compare __comp)
>> +             _Pointer __buffer, _Compare __comp)
>>     {
>> -      if (__len1 <= __len2 && __len1 <= __buffer_size)
>> +      if (__len1 <= __len2)
>>     {
>>       _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, 
>> __buffer);
>>       std::__move_merge_adaptive(__buffer, __buffer_end, __middle, 
>> __last,
>>                      __first, __comp);
>>     }
>> -      else if (__len2 <= __buffer_size)
>> +      else
>>     {
>>       _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, 
>> __buffer);
>>       std::__move_merge_adaptive_backward(__first, __middle, __buffer,
>>                           __buffer_end, __last, __comp);
>>     }
>> +    }
>> +
>> +  template<typename _BidirectionalIterator, typename _Distance,
>> +       typename _Pointer, typename _Compare>
>> +    void
>> +    __merge_adaptive_resize(_BidirectionalIterator __first,
>> +                _BidirectionalIterator __middle,
>> +                _BidirectionalIterator __last,
>> +                _Distance __len1, _Distance __len2,
>> +                _Pointer __buffer, _Distance __buffer_size,
>> +                _Compare __comp)
>> +    {
>> +      if (__len1 <= __buffer_size || __len2 <= __buffer_size)
>> +    std::__merge_adaptive(__first, __middle, __last,
>> +                  __len1, __len2, __buffer, __comp);
>>       else
>>     {
>>       _BidirectionalIterator __first_cut = __first;
>> @@ -2450,14 +2464,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>>
>>       _BidirectionalIterator __new_middle
>>         = std::__rotate_adaptive(__first_cut, __middle, __second_cut,
>> -                     __len1 - __len11, __len22, __buffer,
>> -                     __buffer_size);
>> -      std::__merge_adaptive(__first, __first_cut, __new_middle, 
>> __len11,
>> -                __len22, __buffer, __buffer_size, __comp);
>> -      std::__merge_adaptive(__new_middle, __second_cut, __last,
>> -                __len1 - __len11,
>> -                __len2 - __len22, __buffer,
>> -                __buffer_size, __comp);
>> +                     __len1 - __len11, __len22,
>> +                     __buffer, __buffer_size);
>> +      std::__merge_adaptive_resize(__first, __first_cut, __new_middle,
>> +                       __len11, __len22,
>> +                       __buffer, __buffer_size, __comp);
>> +      std::__merge_adaptive_resize(__new_middle, __second_cut, __last,
>> +                       __len1 - __len11, __len2 - __len22,
>> +                       __buffer, __buffer_size, __comp);
>>     }
>>     }
>>
>> @@ -2535,11 +2549,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>>       // [first,middle) and [middle,last).
>>       _TmpBuf __buf(__first, std::min(__len1, __len2));
>>
>> -      if (__buf.begin() == 0)
>> +      if (__builtin_expect(__buf.size() == __buf.requested_size(), 
>> true))
>> +    std::__merge_adaptive
>> +      (__first, __middle, __last, __len1, __len2, __buf.begin(), 
>> __comp);
>> +      else if (__builtin_expect(__buf.begin() == 0, false))
>>     std::__merge_without_buffer
>>       (__first, __middle, __last, __len1, __len2, __comp);
>>       else
>> -    std::__merge_adaptive
>> +    std::__merge_adaptive_resize
>>       (__first, __middle, __last, __len1, __len2, __buf.begin(),
>>        _DistanceType(__buf.size()), __comp);
>>     }
>> @@ -2720,34 +2737,45 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>>     }
>>     }
>>
>> -  template<typename _RandomAccessIterator, typename _Pointer,
>> -       typename _Distance, typename _Compare>
>> +  template<typename _RandomAccessIterator, typename _Pointer, 
>> typename _Compare>
>>     void
>>     __stable_sort_adaptive(_RandomAccessIterator __first,
>> +               _RandomAccessIterator __middle,
>>                _RandomAccessIterator __last,
>> -               _Pointer __buffer, _Distance __buffer_size,
>> -               _Compare __comp)
>> +               _Pointer __buffer, _Compare __comp)
>> +    {
>> +      std::__merge_sort_with_buffer(__first, __middle, __buffer, 
>> __comp);
>> +      std::__merge_sort_with_buffer(__middle, __last, __buffer, 
>> __comp);
>> +
>> +      std::__merge_adaptive(__first, __middle, __last,
>> +                __middle - __first, __last - __middle,
>> +                __buffer, __comp);
>> +    }
>> +
>> +  template<typename _RandomAccessIterator, typename _Pointer,
>> +       typename _Distance, typename _Compare>
>> +    void
>> +    __stable_sort_adaptive_resize(_RandomAccessIterator __first,
>> +                  _RandomAccessIterator __last,
>> +                  _Pointer __buffer, _Distance __buffer_size,
>> +                  _Compare __comp)
>>     {
>>       const _Distance __len = (__last - __first + 1) / 2;
>>       const _RandomAccessIterator __middle = __first + __len;
>>       if (__len > __buffer_size)
>>     {
>> -      std::__stable_sort_adaptive(__first, __middle, __buffer,
>> -                      __buffer_size, __comp);
>> -      std::__stable_sort_adaptive(__middle, __last, __buffer,
>> -                      __buffer_size, __comp);
>> +      std::__stable_sort_adaptive_resize(__first, __middle, __buffer,
>> +                         __buffer_size, __comp);
>> +      std::__stable_sort_adaptive_resize(__middle, __last, __buffer,
>> +                         __buffer_size, __comp);
>> +      std::__merge_adaptive_resize(__first, __middle, __last,
>> +                       _Distance(__middle - __first),
>> +                       _Distance(__last - __middle),
>> +                       __buffer, __buffer_size,
>> +                       __comp);
>>     }
>>       else
>> -    {
>> -      std::__merge_sort_with_buffer(__first, __middle, __buffer, 
>> __comp);
>> -      std::__merge_sort_with_buffer(__middle, __last, __buffer, 
>> __comp);
>> -    }
>> -
>> -      std::__merge_adaptive(__first, __middle, __last,
>> -                _Distance(__middle - __first),
>> -                _Distance(__last - __middle),
>> -                __buffer, __buffer_size,
>> -                __comp);
>> +    __stable_sort_adaptive(__first, __middle, __last, __buffer, 
>> __comp);
>>     }
>>
>>   /// This is a helper function for the stable sorting routines.
>> @@ -5017,11 +5045,14 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
>>       // so the buffer only needs to fit half the range at once.
>>       _TmpBuf __buf(__first, (__last - __first + 1) / 2);
>>
>> -      if (__buf.begin() == 0)
>> +      if (__builtin_expect(__buf.requested_size() == __buf.size(), 
>> true))
>> +    std::__stable_sort_adaptive(__first, __first + __buf.size(), 
>> __last,
>> +                    __buf.begin(), __comp);
>> +      else if (__builtin_expect(__buf.begin() == 0, false))
>>     std::__inplace_stable_sort(__first, __last, __comp);
>>       else
>> -    std::__stable_sort_adaptive(__first, __last, __buf.begin(),
>> -                    _DistanceType(__buf.size()), __comp);
>> +    std::__stable_sort_adaptive_resize(__first, __last, __buf.begin(),
>> +                       _DistanceType(__buf.size()), __comp);
>>     }
>>
>>   /**
>


[-- Attachment #2: stable_sort.patch --]
[-- Type: text/x-patch, Size: 6701 bytes --]

diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h
index bc611a95ef4..2ebc3b12713 100644
--- a/libstdc++-v3/include/bits/stl_algo.h
+++ b/libstdc++-v3/include/bits/stl_algo.h
@@ -2384,28 +2384,42 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     }
 
   /// This is a helper function for the merge routines.
-  template<typename _BidirectionalIterator, typename _Distance, 
+  template<typename _BidirectionalIterator, typename _Distance,
 	   typename _Pointer, typename _Compare>
     void
     __merge_adaptive(_BidirectionalIterator __first,
 		     _BidirectionalIterator __middle,
 		     _BidirectionalIterator __last,
 		     _Distance __len1, _Distance __len2,
-		     _Pointer __buffer, _Distance __buffer_size,
-		     _Compare __comp)
+		     _Pointer __buffer, _Compare __comp)
     {
-      if (__len1 <= __len2 && __len1 <= __buffer_size)
+      if (__len1 <= __len2)
 	{
 	  _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
 	  std::__move_merge_adaptive(__buffer, __buffer_end, __middle, __last,
 				     __first, __comp);
 	}
-      else if (__len2 <= __buffer_size)
+      else
 	{
 	  _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
 	  std::__move_merge_adaptive_backward(__first, __middle, __buffer,
 					      __buffer_end, __last, __comp);
 	}
+    }
+
+  template<typename _BidirectionalIterator, typename _Distance,
+	   typename _Pointer, typename _Compare>
+    void
+    __merge_adaptive_resize(_BidirectionalIterator __first,
+			    _BidirectionalIterator __middle,
+			    _BidirectionalIterator __last,
+			    _Distance __len1, _Distance __len2,
+			    _Pointer __buffer, _Distance __buffer_size,
+			    _Compare __comp)
+    {
+      if (__len1 <= __buffer_size || __len2 <= __buffer_size)
+	std::__merge_adaptive(__first, __middle, __last,
+			      __len1, __len2, __buffer, __comp);
       else
 	{
 	  _BidirectionalIterator __first_cut = __first;
@@ -2433,14 +2447,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
 	  _BidirectionalIterator __new_middle
 	    = std::__rotate_adaptive(__first_cut, __middle, __second_cut,
-				     __len1 - __len11, __len22, __buffer,
-				     __buffer_size);
-	  std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
-				__len22, __buffer, __buffer_size, __comp);
-	  std::__merge_adaptive(__new_middle, __second_cut, __last,
-				__len1 - __len11,
-				__len2 - __len22, __buffer,
-				__buffer_size, __comp);
+				     __len1 - __len11, __len22,
+				     __buffer, __buffer_size);
+	  std::__merge_adaptive_resize(__first, __first_cut, __new_middle,
+				       __len11, __len22,
+				       __buffer, __buffer_size, __comp);
+	  std::__merge_adaptive_resize(__new_middle, __second_cut, __last,
+				       __len1 - __len11, __len2 - __len22,
+				       __buffer, __buffer_size, __comp);
 	}
     }
 
@@ -2518,11 +2532,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       // [first,middle) and [middle,last).
       _TmpBuf __buf(__first, std::min(__len1, __len2));
 
-      if (__buf.begin() == 0)
+      if (__builtin_expect(__buf.size() == __buf.requested_size(), true))
+	std::__merge_adaptive
+	  (__first, __middle, __last, __len1, __len2, __buf.begin(), __comp);
+      else if (__builtin_expect(__buf.begin() == 0, false))
 	std::__merge_without_buffer
 	  (__first, __middle, __last, __len1, __len2, __comp);
       else
-	std::__merge_adaptive
+	std::__merge_adaptive_resize
 	  (__first, __middle, __last, __len1, __len2, __buf.begin(),
 	   _DistanceType(__buf.size()), __comp);
     }
@@ -2703,34 +2720,46 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	}
     }
 
-  template<typename _RandomAccessIterator, typename _Pointer,
-	   typename _Distance, typename _Compare>
+  template<typename _RandomAccessIterator, typename _Pointer, typename _Compare>
     void
     __stable_sort_adaptive(_RandomAccessIterator __first,
+			   _RandomAccessIterator __middle,
 			   _RandomAccessIterator __last,
-			   _Pointer __buffer, _Distance __buffer_size,
-			   _Compare __comp)
+			   _Pointer __buffer, _Compare __comp)
+    {
+      std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
+      std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
+
+      std::__merge_adaptive(__first, __middle, __last,
+			    __middle - __first, __last - __middle,
+			    __buffer, __comp);
+    }
+
+  template<typename _RandomAccessIterator, typename _Pointer,
+	   typename _Distance, typename _Compare>
+    void
+    __stable_sort_adaptive_resize(_RandomAccessIterator __first,
+				  _RandomAccessIterator __last,
+				  _Pointer __buffer, _Distance __buffer_size,
+				  _Compare __comp)
     {
       const _Distance __len = (__last - __first + 1) / 2;
       const _RandomAccessIterator __middle = __first + __len;
       if (__len > __buffer_size)
 	{
-	  std::__stable_sort_adaptive(__first, __middle, __buffer,
-				      __buffer_size, __comp);
-	  std::__stable_sort_adaptive(__middle, __last, __buffer,
-				      __buffer_size, __comp);
+	  std::__stable_sort_adaptive_resize(__first, __middle, __buffer,
+					     __buffer_size, __comp);
+	  std::__stable_sort_adaptive_resize(__middle, __last, __buffer,
+					     __buffer_size, __comp);
+	  std::__merge_adaptive_resize(__first, __middle, __last,
+				       _Distance(__middle - __first),
+				       _Distance(__last - __middle),
+				       __buffer, __buffer_size,
+				       __comp);
 	}
       else
-	{
-	  std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
-	  std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
-	}
-
-      std::__merge_adaptive(__first, __middle, __last,
-			    _Distance(__middle - __first),
-			    _Distance(__last - __middle),
-			    __buffer, __buffer_size,
-			    __comp);
+	std::__stable_sort_adaptive(__first, __middle, __last,
+				    __buffer, __comp);
     }
 
   /// This is a helper function for the stable sorting routines.
@@ -4995,11 +5024,14 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
       // so the buffer only needs to fit half the range at once.
       _TmpBuf __buf(__first, (__last - __first + 1) / 2);
 
-      if (__buf.begin() == 0)
+      if (__builtin_expect(__buf.requested_size() == __buf.size(), true))
+	std::__stable_sort_adaptive(__first, __first + __buf.size(), __last,
+				    __buf.begin(), __comp);
+      else if (__builtin_expect(__buf.begin() == 0, false))
 	std::__inplace_stable_sort(__first, __last, __comp);
       else
-	std::__stable_sort_adaptive(__first, __last, __buf.begin(),
-				    _DistanceType(__buf.size()), __comp);
+	std::__stable_sort_adaptive_resize(__first, __last, __buf.begin(),
+					   _DistanceType(__buf.size()), __comp);
     }
 
   /**

^ permalink raw reply	[flat|nested] 4+ messages in thread

* Re: [PATCH] Simplify branching in algos
  2021-11-21 20:34   ` François Dumont
@ 2022-07-18 10:25     ` François Dumont
  2022-07-18 10:52       ` Jonathan Wakely
  0 siblings, 1 reply; 4+ messages in thread
From: François Dumont @ 2022-07-18 10:25 UTC (permalink / raw)
  To: Jonathan Wakely, libstdc++; +Cc: gcc-patches

[-- Attachment #1: Type: text/plain, Size: 1643 bytes --]

Hi

     I just noticed that I still had this nice enhancement in my local 
branches.

     Ok to commit ?

François

On 21/11/21 21:34, François Dumont wrote:
> A recent thread on this mailing list made me remember that this 
> proposal is still open.
>
> I've updated it just to add a missing std qualification.
>
> François
>
> On 08/06/21 5:21 pm, Jonathan Wakely wrote:
>> I haven't forgotten this one, I just need to double-check that we
>> don't create another problem like std::rotate in 9.1
>>
>> I'll try to finish the review tomorrow.
>>
>> J.
>>
>>
>> On 27/05/21 07:04 +0200, François Dumont via Libstdc++ wrote:
>>> Following latest fixes in std::inplace_merge and std::stable_sort 
>>> you propose Jonathan to enhance branching in the first.
>>>
>>> Here is a proposal based on yours to do so in both algos.
>>>
>>>     libstdc++: Enhance branching in std::inplace_merge and 
>>> std::stable_sort
>>>
>>>     libstdc++-v3/ChangeLog:
>>>
>>>             * include/bits/stl_algo.h
>>>             (__merge_adaptive): Adapt to merge only when buffer is 
>>> large enough..
>>>             (__merge_adaptive_resize): New, adapt merge when buffer 
>>> is too small.
>>>             (__inplace_merge): Adapt, use latter.
>>>             (__stable_sort_adaptive): Adapt to sort only when buffer 
>>> is large enough.
>>>             (__stable_sort_adaptive_resize): New, adapt sort when 
>>> buffer is too small.
>>>             (__stable_sort): Adapt, use latter.
>>>
>>> Tested under Linux x64.
>>>
>>> Ok to commit ?
>>>
>>> François
>>>

[-- Attachment #2: algo.patch --]
[-- Type: text/x-patch, Size: 6123 bytes --]

diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h
index 1d8ed4e5fa8..c6078054514 100644
--- a/libstdc++-v3/include/bits/stl_algo.h
+++ b/libstdc++-v3/include/bits/stl_algo.h
@@ -2397,21 +2397,35 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
 		     _BidirectionalIterator __middle,
 		     _BidirectionalIterator __last,
 		     _Distance __len1, _Distance __len2,
-		     _Pointer __buffer, _Distance __buffer_size,
-		     _Compare __comp)
+		     _Pointer __buffer, _Compare __comp)
     {
-      if (__len1 <= __len2 && __len1 <= __buffer_size)
+      if (__len1 <= __len2)
 	{
 	  _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
 	  std::__move_merge_adaptive(__buffer, __buffer_end, __middle, __last,
 				     __first, __comp);
 	}
-      else if (__len2 <= __buffer_size)
+      else
 	{
 	  _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
 	  std::__move_merge_adaptive_backward(__first, __middle, __buffer,
 					      __buffer_end, __last, __comp);
 	}
+    }
+
+  template<typename _BidirectionalIterator, typename _Distance,
+	   typename _Pointer, typename _Compare>
+    void
+    __merge_adaptive_resize(_BidirectionalIterator __first,
+			    _BidirectionalIterator __middle,
+			    _BidirectionalIterator __last,
+			    _Distance __len1, _Distance __len2,
+			    _Pointer __buffer, _Distance __buffer_size,
+			    _Compare __comp)
+    {
+      if (__len1 <= __buffer_size || __len2 <= __buffer_size)
+	std::__merge_adaptive(__first, __middle, __last,
+			      __len1, __len2, __buffer, __comp);
       else
 	{
 	  _BidirectionalIterator __first_cut = __first;
@@ -2439,14 +2453,14 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
 
 	  _BidirectionalIterator __new_middle
 	    = std::__rotate_adaptive(__first_cut, __middle, __second_cut,
-				     __len1 - __len11, __len22, __buffer,
-				     __buffer_size);
-	  std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
-				__len22, __buffer, __buffer_size, __comp);
-	  std::__merge_adaptive(__new_middle, __second_cut, __last,
-				__len1 - __len11,
-				__len2 - __len22, __buffer,
-				__buffer_size, __comp);
+				     __len1 - __len11, __len22,
+				     __buffer, __buffer_size);
+	  std::__merge_adaptive_resize(__first, __first_cut, __new_middle,
+				       __len11, __len22,
+				       __buffer, __buffer_size, __comp);
+	  std::__merge_adaptive_resize(__new_middle, __second_cut, __last,
+				       __len1 - __len11, __len2 - __len22,
+				       __buffer, __buffer_size, __comp);
 	}
     }
 
@@ -2524,11 +2538,14 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
       // [first,middle) and [middle,last).
       _TmpBuf __buf(__first, std::min(__len1, __len2));
 
-      if (__buf.begin() == 0)
+      if (__builtin_expect(__buf.size() == __buf.requested_size(), true))
+	std::__merge_adaptive
+	  (__first, __middle, __last, __len1, __len2, __buf.begin(), __comp);
+      else if (__builtin_expect(__buf.begin() == 0, false))
 	std::__merge_without_buffer
 	  (__first, __middle, __last, __len1, __len2, __comp);
       else
-	std::__merge_adaptive
+	std::__merge_adaptive_resize
 	  (__first, __middle, __last, __len1, __len2, __buf.begin(),
 	   _DistanceType(__buf.size()), __comp);
     }
@@ -2709,10 +2726,25 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
 	}
     }
 
+  template<typename _RandomAccessIterator, typename _Pointer, typename _Compare>
+    void
+    __stable_sort_adaptive(_RandomAccessIterator __first,
+			   _RandomAccessIterator __middle,
+			   _RandomAccessIterator __last,
+			   _Pointer __buffer, _Compare __comp)
+    {
+      std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
+      std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
+
+      std::__merge_adaptive(__first, __middle, __last,
+			    __middle - __first, __last - __middle,
+			    __buffer, __comp);
+    }
+
   template<typename _RandomAccessIterator, typename _Pointer,
 	   typename _Distance, typename _Compare>
     void
-    __stable_sort_adaptive(_RandomAccessIterator __first,
+    __stable_sort_adaptive_resize(_RandomAccessIterator __first,
 				  _RandomAccessIterator __last,
 				  _Pointer __buffer, _Distance __buffer_size,
 				  _Compare __comp)
@@ -2721,23 +2753,20 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
       const _RandomAccessIterator __middle = __first + __len;
       if (__len > __buffer_size)
 	{
-	  std::__stable_sort_adaptive(__first, __middle, __buffer,
+	  std::__stable_sort_adaptive_resize(__first, __middle, __buffer,
 					     __buffer_size, __comp);
-	  std::__stable_sort_adaptive(__middle, __last, __buffer,
+	  std::__stable_sort_adaptive_resize(__middle, __last, __buffer,
 					     __buffer_size, __comp);
-	}
-      else
-	{
-	  std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
-	  std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
-	}
-
-      std::__merge_adaptive(__first, __middle, __last,
+	  std::__merge_adaptive_resize(__first, __middle, __last,
 				       _Distance(__middle - __first),
 				       _Distance(__last - __middle),
 				       __buffer, __buffer_size,
 				       __comp);
 	}
+      else
+	std::__stable_sort_adaptive(__first, __middle, __last,
+				    __buffer, __comp);
+    }
 
   /// This is a helper function for the stable sorting routines.
   template<typename _RandomAccessIterator, typename _Compare>
@@ -4996,10 +5025,13 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
       // so the buffer only needs to fit half the range at once.
       _TmpBuf __buf(__first, (__last - __first + 1) / 2);
 
-      if (__buf.begin() == 0)
+      if (__builtin_expect(__buf.requested_size() == __buf.size(), true))
+	std::__stable_sort_adaptive(__first, __first + __buf.size(), __last,
+				    __buf.begin(), __comp);
+      else if (__builtin_expect(__buf.begin() == 0, false))
 	std::__inplace_stable_sort(__first, __last, __comp);
       else
-	std::__stable_sort_adaptive(__first, __last, __buf.begin(),
+	std::__stable_sort_adaptive_resize(__first, __last, __buf.begin(),
 					   _DistanceType(__buf.size()), __comp);
     }
 

^ permalink raw reply	[flat|nested] 4+ messages in thread

* Re: [PATCH] Simplify branching in algos
  2022-07-18 10:25     ` François Dumont
@ 2022-07-18 10:52       ` Jonathan Wakely
  0 siblings, 0 replies; 4+ messages in thread
From: Jonathan Wakely @ 2022-07-18 10:52 UTC (permalink / raw)
  To: François Dumont; +Cc: libstdc++, gcc-patches

On Mon, 18 Jul 2022 at 11:25, François Dumont <frs.dumont@gmail.com> wrote:
>
> Hi
>
>      I just noticed that I still had this nice enhancement in my local
> branches.
>
>      Ok to commit ?

OK, thanks.


^ permalink raw reply	[flat|nested] 4+ messages in thread

end of thread, other threads:[~2022-07-18 10:52 UTC | newest]

Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-05-27  5:04 [PATCH] Simplify branching in algos François Dumont
     [not found] ` <YL+LEU/o0E4UOlIi@redhat.com>
2021-11-21 20:34   ` François Dumont
2022-07-18 10:25     ` François Dumont
2022-07-18 10:52       ` Jonathan Wakely

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).