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 <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 ?
François
