Re: [PATCH] Simplify branching in algos
On Mon, 18 Jul 2022 at 11:25, François Dumont wrote: > > Hi > > I just noticed that I still had this nice enhancement in my local > branches. > > Ok to commit ? OK, thanks.
Re: [PATCH] Simplify branching in algos
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
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
+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
+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, __bu
Re: [PATCH] Simplify branching in algos
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.
- templatetemplate
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
+ 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
+
[PATCH] Simplify branching in algos
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
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
+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
+ template
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
+void
+__stable_sort_adaptive_resize(_RandomAccessIterator __first,
+ _RandomAccessIterator __last,
+ _Pointer __buffer, _Distance __buffer_size,
+ _Compare __comp)
{
const _Distance __l
