[PATCH] PR 83938 Reduce memory consumption in stable_sort/inplace_merge

[François Dumont]

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