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.
Sure, just note that there is no change to the algo logic in any way. It
is only to limit the temporary buffer allocation to what is being used.
This kind of situation illustrates also why PR management would be nice.
I wouldn't wonder if the patch hasn't been forgotten. I know that you
are for it, I hope you'll make your point one day.
Thanks
