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

[Paolo Carlini]

Howard Hinnant wrote:

>>> FYI, I'm working on this. It looks like, we are already using the
>>> optimization for deque::clear() and we are not for
>>> deque::erase(iterator, iterator). It seems to me that we should just
>>> take out the code in clear() which implements the double loop pattern
>>> and call it from both. Which in fact would be _M_erase_at_end or
>>> _M_erase_at_begin ;) ...
>>
>> ... and of course, going to loops over plain pointers, instead of
>> deque::iterators means that _Destroy will be optimized very, very well
>> by the compiler, similarly to what happens for vector! (especially 
>> so if
>> we overload it for random access iterators)
>>
>> :-)
>
> Thanks Paolo!

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.

Paolo.

//////////////////
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: CL_deque
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20051125/d9aec60a/attachment.ksh>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: patch_deque
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20051125/d9aec60a/attachment-0001.ksh>