[C++ PATCH] Speed up inplace_merge algorithm & fix inefficient logic(PR libstdc++/83938)

François Dumont frs.dumont@gmail.com
Tue Aug 21 20:34:00 GMT 2018 

I missed a test that was failing because of this patch. So I revert a 
small part of it and here is the new proposal.

Tested under Linux x86_64, ok to commit ?

François


On 24/07/2018 12:22, François Dumont wrote:
> Hi
>
>     Any chance to review this patch ?
>
> François
>
>
> On 06/06/2018 18:39, François Dumont wrote:
>> Hi
>>
>>     I review and rework this proposal. I noticed that the same idea 
>> to limit buffer size within inplace_merge also apply to stable_sort.
>>
>>     I also change the decision when buffer is too small to consider 
>> the buffer size rather than going through successive cuts of the 
>> original ranges. This way we won't cut the range more than necessary. 
>> Note that if you prefer this second part could be committed seperatly.
>>
>>     PR libstdc++/83938
>>     * include/bits/stl_algo.h:
>>     (__stable_partition_adaptive): When buffer to small cut range using
>>     buffer size.
>>     (__inplace_merge): Take temporary buffer length from smallest range.
>>     (__merge_adaptive): When buffer too small consider smallest range 
>> first
>>     and cut based on buffer size.
>>     (__stable_sort_adaptive): When buffer too small cut based on buffer
>>     size.
>>     (__stable_sort): Limit temporary buffer length.
>>     * include/bits/stl_tempbuf.h (get_temporary_buffer): Change function
>>     to reduce requested buffer length on allocation failure.
>>
>> Tested under Linux x86_64.
>>
>> Ok to commit ?
>>
>> François
>>
>>
>> On 25/01/2018 23:37, chang jc wrote:
>>> Hi:
>>>
>>> 1. The __len = (__len + 1) / 2; is as you suggested, need to modify as
>>> __len = (__len == 1) ? 0 : ((__len + 1) / 2);
>>>
>>> 2. The coding gain has been shown  PR c++/83938; I re-post here
>>>
>>>
>>>
>>>
>>>    21
>>>    20
>>>    19
>>>    18
>>>    17
>>>    16
>>>
>>>
>>>    0.471136
>>>    0.625695
>>>    0.767262
>>>    0.907461
>>>    1.04838
>>>    1.19508
>>>
>>>
>>>    0.340845
>>>    0.48651
>>>    0.639139
>>>    0.770133
>>>    0.898454
>>>    1.04632
>>>
>>> it means when Merge [0, 4325376, 16777216); A is a sorted integer with
>>> 4325376 & B with 12451840 elements, total with 16M integers
>>>
>>> The proposed method has the speed up under given buffer size =, ex
>>> 2^16, 2^17, ... 2^21 in unit of sizeof(int), for example, 2^16 means
>>> given sizof(int)*64K bytes.
>>>
>>> 3. As your suggestion, _TmpBuf __buf should be rewrite.
>>>
>>> 4. It represents a fact that the intuitive idea to split from larger
>>> part is wrong.
>>>
>>> For example, if you have an input sorted array A & B, A has 8 integers
>>> & B has 24 integers. Given tmp buffer whose capacity = 4 integers.
>>>
>>> Current it tries to split from B, right?
>>>
>>> Then we have:
>>>
>>> A1 | A2  B1 | B2
>>>
>>> B1 & B2 has 12 integers each, right?
>>>
>>> Current algorithm selects pivot as 13th integer from B, right?
>>>
>>> If the corresponding upper bound of A is 6th integer.
>>>
>>> Then it split in
>>>
>>> A1 = 5 | A2 = 3 | B1 = 12 | B2 = 12
>>>
>>> After rotate, we have two arrays to merge
>>>
>>> [A1 = 5 | B1 = 12]  & [A2 = 3 | B2 = 12]
>>>
>>> Great, [A2 = 3 | B2 = 12] can use tmp buffer to merge.
>>>
>>> Sadly, [A1 = 5 | B1 = 12] CANNOT.
>>>
>>> So we do rotate again, split & merge the two split arrays from [A1 = 5
>>> | B1 = 12] again.
>>>
>>>
>>> But wait, if we always split from the smaller one instead of larger 
>>> one.
>>>
>>> After rotate, it promises two split arrays both contain 
>>> ceiling[small/2].
>>>
>>> Since tmp buffer also allocate by starting from sizeof(small) &
>>> recursively downgrade by ceiling[small/2^(# of fail allocate)].
>>>
>>> It means the allocated tmp buffer promises to be sufficient at the
>>> level of (# of fail allocate).
>>>
>>> Instead, you can see if split from large at level (# of fail allocate)
>>> several split array still CANNOT use  tmp buffer to do buffered merge.
>>>
>>>
>>> As you know, buffered merge is far speed then (split, rotate, and
>>> merge two sub-arrays) (PR c++/83938 gives the profiling figures),
>>>
>>> the way should provide speedup.
>>>
>>>
>>> Thanks.
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>> On 24/01/2018 18:23, François Dumont wrote:
>>>
>>> Hi
>>>
>>>
>>>      It sounds like a very sensitive change to make but nothing 
>>> worth figures.
>>> Do you have any bench showing the importance of the gain ?
>>>
>>>      At least the memory usage optimization is obvious.
>>>
>>> On 19/01/2018 10:43, chang jc wrote:
>>>
>>> Current std::inplace_merge() suffers from performance issue by 
>>> inefficient
>>>
>>> logic under limited memory,
>>>
>>> It leads to performance downgrade.
>>>
>>> Please help to review it.
>>>
>>> Index: include/bits/stl_algo.h
>>> ===================================================================
>>> --- include/bits/stl_algo.h    (revision 256871)
>>> +++ include/bits/stl_algo.h    (working copy)
>>> @@ -2437,7 +2437,7 @@
>>>          _BidirectionalIterator __second_cut = __middle;
>>>          _Distance __len11 = 0;
>>>          _Distance __len22 = 0;
>>> -      if (__len1 > __len2)
>>> +      if (__len1 < __len2)
>>>            {
>>>              __len11 = __len1 / 2;
>>>              std::advance(__first_cut, __len11);
>>> @@ -2539,9 +2539,15 @@
>>>          const _DistanceType __len1 = std::distance(__first, __middle);
>>>          const _DistanceType __len2 = std::distance(__middle, __last);
>>>
>>> +
>>>
>>>          typedef _Temporary_buffer<_BidirectionalIterator, _ValueType>
>>> _TmpBuf;
>>>
>>> -      _TmpBuf __buf(__first, __last);
>>> -
>>> +      _BidirectionalIterator __start, __end;
>>> +      if (__len1 < __len2) {
>>> +    __start = __first; __end = __middle;
>>> +      } else {
>>> +    __start = __middle; __end = __last;
>>> +      }
>>> +      _TmpBuf __buf(__start, ___end);
>>>
>>> Note another optimization, we could introduce a _Temporary_buffer<> 
>>> constructor
>>> in order to write:
>>>
>>> _TmpBuf __buf(std::min(__len1, __len2), __first);
>>>
>>> So that std::distance do not need to be called again.
>>>
>>>          if (__buf.begin() == 0)
>>>        std::__merge_without_buffer
>>>          (__first, __middle, __last, __len1, __len2, __comp);
>>> Index: include/bits/stl_tempbuf.h
>>> ===================================================================
>>> --- include/bits/stl_tempbuf.h    (revision 256871)
>>> +++ include/bits/stl_tempbuf.h    (working copy)
>>> @@ -95,7 +95,7 @@
>>>                                std::nothrow));
>>>          if (__tmp != 0)
>>>            return std::pair<_Tp*, ptrdiff_t>(__tmp, __len);
>>> -      __len /= 2;
>>> +      __len = (__len + 1) / 2;
>>>
>>> This part is problematic, if __len is 1 and allocation fails it will 
>>> loop
>>> forever.
>>>
>>> It doesn't seem really necessary for your patch.
>>>
>>>
>>> 2018-01-20 4:05 GMT+08:00 Jason Merrill<jason@redhat.com>:
>>>
>>>> This is a libstdc++ bug and patch, not the C++ front end.  So I'm
>>>> adding the libstdc++ list to CC.
>>>>
>>>> On Fri, Jan 19, 2018 at 3:02 AM, chang jc<r97922153@gmail.com>  wrote:
>>>>> Current std::inplace_merge() suffers from performance issue by
>>>> inefficient
>>>>> logic under limited memory,
>>>>>
>>>>> It leads to performance downgrade.
>>>>>
>>>>> Please help to review it.
>>>>>
>>>>> Index: include/bits/stl_algo.h
>>>>> ===================================================================
>>>>> --- include/bits/stl_algo.h     (revision 256871)
>>>>> +++ include/bits/stl_algo.h     (working copy)
>>>>> @@ -2437,7 +2437,7 @@
>>>>>            _BidirectionalIterator __second_cut = __middle;
>>>>>            _Distance __len11 = 0;
>>>>>            _Distance __len22 = 0;
>>>>> -         if (__len1 > __len2)
>>>>> +         if (__len1 < __len2)
>>>>>              {
>>>>>                __len11 = __len1 / 2;
>>>>>                std::advance(__first_cut, __len11);
>>>>> @@ -2539,9 +2539,15 @@
>>>>>         const _DistanceType __len1 = std::distance(__first, 
>>>>> __middle);
>>>>>         const _DistanceType __len2 = std::distance(__middle, __last);
>>>>>
>>>>> +
>>>>>         typedef _Temporary_buffer<_BidirectionalIterator, _ValueType>
>>>> _TmpBuf;
>>>>> -      _TmpBuf __buf(__first, __last);
>>>>> -
>>>>> +      _BidirectionalIterator __start, __end;
>>>>> +      if (__len1 < __len2) {
>>>>> +       __start = __first; __end = __middle;
>>>>> +      } else {
>>>>> +       __start = __middle; __end = __last;
>>>>> +      }
>>>>> +      _TmpBuf __buf(__start, ___end);
>>>>>         if (__buf.begin() == 0)
>>>>>          std::__merge_without_buffer
>>>>>            (__first, __middle, __last, __len1, __len2, __comp);
>>>>> Index: include/bits/stl_tempbuf.h
>>>>> ===================================================================
>>>>> --- include/bits/stl_tempbuf.h  (revision 256871)
>>>>> +++ include/bits/stl_tempbuf.h  (working copy)
>>>>> @@ -95,7 +95,7 @@
>>>>> std::nothrow));
>>>>>            if (__tmp != 0)
>>>>>              return std::pair<_Tp*, ptrdiff_t>(__tmp, __len);
>>>>> -         __len /= 2;
>>>>> +         __len = (__len + 1) / 2;
>>>>>          }
>>>>>         return std::pair<_Tp*, ptrdiff_t>(static_cast<_Tp*>(0), 0);
>>>>>       }
>>>>>
>>>>>
>>>>>
>>>>>
>>>>> Thanks
>>
>>
>

-------------- next part --------------
A non-text attachment was scrubbed...
Name: pr83938.patch
Type: text/x-patch
Size: 3921 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20180821/c0900219/attachment.bin>

More information about the Libstdc++ mailing list