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