[Patch] libstdc++/23425

[Howard Hinnant]

On Nov 4, 2005, at 5:05 AM, Paolo Carlini wrote:

> Paolo Carlini wrote:
>
>
>> Hi,
>>
>>
>>> lear() is best not thought of as a special case of erase().  It is
>>> best thought of as a special case of a private function which  
>>> I'll call:
>>>
>>> void __erase_at_end(size_type n);
>>>
>>> Erases the last n elements from the vector.  This is needed in the
>>> following public members of vector:
>>>
>>> All forms of assign.
>>> All forms of erase.
>>> All forms of resize.
>>> clear.
>>>
>>>
>>>
>> Howard, makes sense to you that essentially the same optimization is
>> possible for std::deque? I'm looking at the code and, besides the
>> additional complexity of freeing the nodes, it seems everything is  
>> very,
>> very similar. I can work on that too in the branch.
>>
>>
>>
> + understandably, an _M_erase_at_begin could be expected...
>
> However I'm not sure that it would find as many uses, besides the
> implementation of erase(iterator, iterator)...

Ay, a really good deque is head&shoulders the most complicated  
container in the lib.  Far, far more complicated than the rb tree.

Yes, _M_erase_at_end would be useful under assign, pop_back, erase,  
and resize.  A good _M_erase_at_end will do more than simply run the  
iterator through.  It will do the "segmented iterator" optimization  
as  promoted by Dietmar for so many years.  That is, it will consist  
of nested loops where the inner loop runs through a node (or partial  
node) at a time with pointers.  And I'm not sure what the node- 
freeing policy is for our deque.  Imho it is a good idea to leave an  
empty node out there on the end because the very next thing is either  
going to be a push_back, requiring the node again, or a push_front  
which could (if it needed) transfer the empty node from back to front.

And here is where we really, really need a quality  
has_trivial_destructor.  So much so, that we should go ahead and use  
whatever we have.  The trivial dtor version of _M_erase_at_end can't  
be optimized by the compiler.  This version can completely eliminate  
the inner loop and just concentrate on freeing nodes and adjusting  
the size.

_M_erase_at_begin?  Yup.  Same comments, but useful only under  
pop_front and erase.  Given that for pop_front to call erase is  
overkill for code and speed (it can merely call _M_erase_at_begin(1)  
or whatever), and there are two versions of erase that can make use  
of _M_erase_at_begin, I think it is a good deal (especially if it is  
optimized to the hilt with segmented iterator and trivial dtor).

deque is a bear.  And I've barely looked at ours.  But I've looked at  
it enough to have the opinion that it might benefit from some major  
surgery, not the least of which is it's overhead:  sizeof(deque<int>)  
is 40 (on a 32 bit machine).  I think we can get that down some.  The  
CodeWarrior deque is 24.  Now it may be that we don't go that far  
down.  As I recall there are some tradeoffs with iterator as you  
squeeze the size of the deque.  But I think it is an area that  
wouldn't hurt from some review.

And of course this all needs to be done without breaking exception  
safety.  Do we run (and pass) Abrahams exception safety test?   
Additionally, if we don't already have it, we could use some  
exception safety tests that stress the corner cases of adding,  
deleting, transferring nodes both on empty deques and non-empty  
deques.  <sigh>  Last time I fooled with deque it was a multi-month  
project...

I encourage you to go ahead with _M_erase_at_end/_M_erase_at_begin.   
If we are going to change the size at all, it couldn't be until v7  
anyway.

-Howard