[PATCH] PR 83938 Reduce memory consumption in stable_sort/inplace_merge
Mon Jun 22 06:27:16 GMT 2020
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
> 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
> Co-authored-by: François Dumont <email@example.com>
> 2020-06-11 John Chang <firstname.lastname@example.org>
> François Dumont <email@example.com>
> 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
> under different heap memory conditions.
> * testsuite/performance/25_algorithms/inplace_merge.cc: New.
> Ok to commit ?
More information about the Libstdc++