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 <fdum...@gcc.gnu.org>
   libstdc++-v3/ChangeLog:
   2020-06-11 John Chang <john.ch...@samba.tv>
               François Dumont <fdum...@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.