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

[Howard Hinnant <hhinnant at apple dot com>]

On Nov 25, 2005, at 2:00 PM, Paolo Carlini wrote:

> So, finally... Here is what I have, taking shape... Exactly as per
> Howard's suggestions, the basic ideas are:
> 1- Consistently use _M_erase_at_begin/_M_erase_at_end and avoid  
> calling
> move/copy unnecessarily.
> 2- Consistently use the "segmented iterator" optimization, when  
> nothing
> better is available, that is, when _Destroy(iterator, iterator)  
> doesn't
> boil down for sure to nothing (see _M_destroy_data_aux).
>
> I have verified from dumps that the loops over pointers produced by 2-
> are optimized to empty loops as expected, even to nothing if  
> _Destroy is
> overloaded for random access iterators (but probably the additional
> overloads can wait because the loop optimizer will be improved and we
> have a PR about that opened by Chris, 23361). And of course that
> otherwise the dumps are as good or better than current mainline ;)
>
> Testcases ran through valgrind.
>
> Anyone can spot something wrong? Otherwise I will probably go ahead  
> for v7.

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.

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.

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.

-Howard