Deque rotate on current node

[François Dumont]

On 01/09/20 3:25 pm, Jonathan Wakely wrote:
> On 01/09/20 14:06 +0200, François Dumont wrote:
>> Hi
>>
>> No chance to review this small patch ?
>
> I did review it, and I wasn't convinced it was a good change. It only
> helps a particular usage pattern, and might hurt in other cases.

     I shouldn't have illustrate the target of this patch with its 
impact on the use case of an initial push_front. It is clearly not its 
purpose and I agree that it doesn't really improve this use case, it 
doesn't make it worst neither however.


>
> I don't agree with your assertion that you use std::deque when you
> only use push_front() and you use std::list if you need both
> push_front() and push_back().
>
> Ideally we'd keep the most recently reallocated node around for reuse,
> and then in the situation you describe the first push_front would
> allocate a new node, but if you immediately do pop_back() we wouldn't
> deallocate the node. But I haven't figured out a way to do that
> caching without an ABI break.
AFAIR I looked at a solution too and couldn't find any ABI compatible. 
This is why I thought this patch could be a limited answer to this.
>
> The patch also has no tests. Are our existing tests sufficient to
> cover this case? Do we want a test that verifies that we don't
> allocate a new node if doing push_front() into an empty deque?

I initially thought that this patch didn't need any specific test but as 
this patch purpose is performance we could indeed add a performance 
test. This is what I've done in attachment. We can now clearly see the 
impact:

Before:

deque.cc                     push_back/pop_front          1167r 1167u    
0s      528mem    0pf

After:

deque.cc                     push_back/pop_front          1018r 1017u    
0s        0mem    0pf

Some CPU enhancements coming from the limitation on memory usage.

I'll do the same with push_front/pop_back if you eventually validate the 
patch.

But even if the results are great I agree that the conditions to benefit 
from it are limited. You need the deque to be empty when you push_back 
at node past-the-end position to benefit from it.

If you think that this kind of situation is too rare to deserve a 
special piece of code in deque implementation then ok, I won't bother 
you with this proposal anymore.

François


-------------- next part --------------
A non-text attachment was scrubbed...
Name: deque_reuse_node.patch
Type: text/x-patch
Size: 3058 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/libstdc++/attachments/20200902/1342ac4d/attachment-0001.bin>