Gentle reminder now that we are in stage 3 ?
On 24/06/20 7:39 pm, Jonathan Wakely wrote:
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.
