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

[François Dumont]

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

-------------- next part --------------
A non-text attachment was scrubbed...
Name: pr83938.patch
Type: text/x-patch
Size: 16082 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/libstdc++/attachments/20200611/501678db/attachment-0001.bin>