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

[Jonathan Wakely]

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 
>allocation.
>
>Â Â Â  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 
>stable_sort
>Â Â Â Â Â Â Â Â Â Â Â  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.