* [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
[parent not found: <YL+LEU/o0E4UOlIi@redhat.com>]
* 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).