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

[François Dumont]

Gentle remider.



On 11/06/20 8:32 am, François Dumont 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 ?
>
> François
>