Deque... (Re: [Patch] libstdc++/23425)

[Paolo Carlini]

Hi Howard,

> I've done a brief visual and can find nothing wrong.  It sure looks 
> like you cleaned up erase(iter,iter)! :-)
>
> The optimization for scalars is slick.  Nice job!  Can't wait till 
> that works for user-defined types too.

Yeah... Better waiting a bit in case that loop optimization PR gets
fixed quickly. Otherwise we can always overload _Destroy for random
access iterators...

> A very minor nit:  We're passing around the allocator by value for 
> the purpose of function dispatching.  Can we change that to by ref?  
> I'd like to get ready for stateful allocators.  I believe this would 
> be a fairly minor mod to  _M_get_Tp_allocator() and its clients.  
> Perhaps starting with:
>
>       _Tp_alloc_type&
>       _M_get_Tp_allocator()
>       { return *static_cast<_Tp_alloc_type*>(&this->_M_impl); }
>
>       _Tp_alloc_type const&
>       _M_get_Tp_allocator() const
>       { return *static_cast<const _Tp_alloc_type*>(&this->_M_impl); }
>
> I'm guessing this would be a minor optimization if the allocator has 
> state.

Totally agreed! I noticed that a few days ago and fixed it (only the
non-const version) for ext/vstring.h in mainline and basic_string in
v7-branch! Actually, wanted to ask you confirmation that we had this
simple preliminary issue in preparation for efficient stateful
allocators and swap everywhere. My plan was to prepare a separate patch
for that, touching *all* the containers.

Probably the real, maybe unconscious, reason why I delayed that work, I
was not 100% sure that was fine from the binary compatibility point of
view: the new _M_get_Tp_allocator compared to the one in mainline would
have the same signature but different return type... And I really wanted
to do first work which, after a bit of testing is amenable to be merged
more or less as-is to mainline. Looks like a plan? Next week I will
start on that, with the simplifications to the algos already in v7 for
mainline. I want to merge as much stuff as possible very quickly, now
that mainline is finally open for new features.

> Not for this patch, but as I was looking about I noticed a couple of 
> places that could still be optimized (this is future work, not a 
> suggestion for this patch!)...
>
> *  I think on erase we should keep a spare empty node hanging around 
> so that it can be recycled on the next insert, even if it needs to be 
> moved from front to back or vice versa.  I'm especially concerned 
> about the steady-state queue use case:
>
> while (a long time)
> {
>      dq.push_front(t);
>      ...
>      dq.pop_back();
> }
>
> I believe that after reaching a steady state the above loop should 
> not continually allocate/deallocate nodes.  Rather it should keep the 
> just emptied back node around and then move it to the front when 
> push_front requests it.  I'd keep no more than one empty node on each 
> end, and maybe that's too much.  Maybe at most just one empty node on 
> either end (since it can be moved where needed).
>
> *  We call std::copy a lot internally (with deque::iterators as the 
> output range, or both input and output).  We need to specialize 
> (overload) std::copy to work nicely with deque::iterator (the 
> segmented iterator optimization).    Same goes for the other 
> std::algorithms we call.

Cool! Thanks a lot. Probably I will link those consideration to our open
deque enhancement PR.

Thanks again!
Paolo.