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

[François Dumont]

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.
>
>
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