[PATCH] PR 83938 Reduce memory consumption in stable_sort/inplace_merge

Jonathan Wakely jwakely@redhat.com
Wed Jun 24 17:39:26 GMT 2020

On 11/06/20 08:32 +0200, François Dumont via Libstdc++ wrote:
>As we are on patching algos we still have this old one.
>    From the original patch I only kept the memory optimization part 
>as the new performance test was not showing good result for the other 
>part to change pivot value. I also kept the small change in 
>get_temporary_buffer even if I don't have strong feeling about it, it 
>just make sure that we'll try to allocate 1 element as a last chance 
>    Note that there is still place for an improvement. If we miss 
>memory on the heap we then use a recursive implementation which then 
>rely on stack memory. I would be surprise that a system which miss 
>heap memory would have no problem to allocate about the same on the 
>stack so we will surely end up in a stack overflow. I still have this 
>on my todo even if I already made several tries with no satisfying 
>result in terms of performance.
>    Tested under Linux x86_64.
>Commit message:
>    libstdc++: Limit memory allocation in stable_sort/inplace_merge 
>(PR 83938)
>    Reduce memory consumption in stable_sort/inplace_merge to what is used.
>    Co-authored-by: François Dumont  <fdumont@gcc.gnu.org>
>    libstdc++-v3/ChangeLog:
>    2020-06-11  John Chang  <john.chang@samba.tv>
>                François Dumont  <fdumont@gcc.gnu.org>
>            PR libstdc++/83938
>            * include/bits/stl_tempbuf.h (get_temporary_buffer): 
>Change __len
>            computation in the loop.
>            * include/bits/stl_algo.h:
>            (__inplace_merge): Take temporary buffer length from 
>smallest range.
>            (__stable_sort): Limit temporary buffer length.
>            * testsuite/25_algorithms/inplace_merge/1.cc (test03): 
>Test different
>            pivot positions.
>            * testsuite/performance/25_algorithms/stable_sort.cc: Test 
>            under different heap memory conditions.
>            * testsuite/performance/25_algorithms/inplace_merge.cc: New.
>Ok to commit ?

I'm very nervous about changes to sort algos that aren't absolutely
necessary for correctness. It needs careful review and lots of
testing. Please be patient.

More information about the Libstdc++ mailing list