From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 92848 invoked by alias); 1 Aug 2019 09:57:30 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 92833 invoked by uid 89); 1 Aug 2019 09:57:30 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-16.2 required=5.0 tests=AWL,BAYES_00,GIT_PATCH_0,GIT_PATCH_1,GIT_PATCH_2,GIT_PATCH_3,SPF_HELO_PASS autolearn=ham version=3.3.1 spammy= X-HELO: mx1.redhat.com Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Thu, 01 Aug 2019 09:57:28 +0000 Received: from smtp.corp.redhat.com (int-mx02.intmail.prod.int.phx2.redhat.com [10.5.11.12]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mx1.redhat.com (Postfix) with ESMTPS id 6AFC1308FC4B; Thu, 1 Aug 2019 09:57:27 +0000 (UTC) Received: from localhost (unknown [10.33.36.86]) by smtp.corp.redhat.com (Postfix) with ESMTP id DD0EF60BEC; Thu, 1 Aug 2019 09:57:26 +0000 (UTC) Date: Thu, 01 Aug 2019 09:57:00 -0000 From: Jonathan Wakely To: =?iso-8859-1?Q?Fran=E7ois?= Dumont Cc: "libstdc++@gcc.gnu.org" , gcc-patches Subject: Re: PR 90409 Deque fiil/copy/move/copy_backward/move_backward/equal overloads Message-ID: <20190801095726.GA28280@redhat.com> References: <9357e741-9a71-6783-2ce9-24ba8a3939ba@gmail.com> <84aa6517-1f06-e751-e3ef-dcaea779806e@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1; format=flowed Content-Disposition: inline Content-Transfer-Encoding: 8bit In-Reply-To: <84aa6517-1f06-e751-e3ef-dcaea779806e@gmail.com> X-Clacks-Overhead: GNU Terry Pratchett User-Agent: Mutt/1.12.0 (2019-05-25) X-SW-Source: 2019-08/txt/msg00014.txt.bz2 On 26/07/19 07:06 +0200, François Dumont wrote: >A new version with tests added at the right place, in 25_algorithms, >next to the existing basic ones. > >Ok to commit ? Are there any benchmarks showing the performance improvements? It *should* be faster, but it's a lot of complicated code to add (and maintain) so it'd better be worth it. More comments inline below ... >François > >On 6/19/19 7:32 PM, François Dumont wrote: >>I wanted to implement Debug overloads for those already existing >>overloads but then realized that those algos could be generalized. >>This way we will benefit from the memmove replacement when operating >>with C array or std::array or std::vector iterators. >> >>I might do the same for lexicographical_compare one day. >> >>The ChangeLog below is quite huge so I attached it. I wonder if I >>could use deque::iterator and deque::const_iterator in place of the >>_Deque_iterator<> to reduce it ? >> >>Tested under Linux x86_64 normal and debug modes, ok to commit ? >> >>François >> > >diff --git a/libstdc++-v3/include/bits/deque.tcc b/libstdc++-v3/include/bits/deque.tcc >index 3f77b4f079c..9db869fb666 100644 >--- a/libstdc++-v3/include/bits/deque.tcc >+++ b/libstdc++-v3/include/bits/deque.tcc >@@ -967,155 +967,507 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER > this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1); > } > >+_GLIBCXX_END_NAMESPACE_CONTAINER >+ > // Overload for deque::iterators, exploiting the "segmented-iterator > // optimization". > template > void >- fill(const _Deque_iterator<_Tp, _Tp&, _Tp*>& __first, >- const _Deque_iterator<_Tp, _Tp&, _Tp*>& __last, const _Tp& __value) >+ fill(const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>& __first, >+ const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>& __last, >+ const _Tp& __value) > { >- typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self; >- >- for (typename _Self::_Map_pointer __node = __first._M_node + 1; >- __node < __last._M_node; ++__node) >- std::fill(*__node, *__node + _Self::_S_buffer_size(), __value); >+ typedef typename _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>::_Self >+ _Self; I know it was already there, but this is a terrible name. Using "_Self" inside a class to refer to the class type itself is OK, but using it outside the class doesn't make sense. And anyway, isn't _Deque_iterator::_Self just the same type as _Deque_iterator ? It should be something like: typedef typename _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> _Iter; >+ template >+ typename enable_if< >+ is_same::iterator_category, >+ std::random_access_iterator_tag>::value, Use is_base_of so it works for types derived from random_access_iterator_tag too. >+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::type >+ move(_II __first, _II __last, >+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __result) >+ { >+ __glibcxx_requires_can_increment_range(__first, __last, __result); > >- if (!__llen) >- { >- __llen = _Self::_S_buffer_size(); >- __lend = *(__last._M_node - 1) + __llen; >- } >- if (!__rlen) >- { >- __rlen = _Self::_S_buffer_size(); >- __rend = *(__result._M_node - 1) + __rlen; >- } >+ return __detail::__move_to_dit(__first, __last, __result); >+ } > >- const difference_type __clen = std::min(__len, >- std::min(__llen, __rlen)); >- std::move_backward(__lend - __clen, __lend, __rend); >- __last -= __clen; >- __result -= __clen; >- __len -= __clen; >- } >- return __result; >+ template >+ _OI >+ move_backward( >+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first, >+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> __last, >+ _OI __result) >+ { >+ __glibcxx_requires_can_decrement_range(__first, __last, __result); >+ >+ return __detail::__move_backward_from_dit(__first, __last, __result); >+ } >+ >+ template >+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >+ move_backward( >+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first, >+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> __last, >+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __result) >+ { >+ __glibcxx_requires_can_decrement_range(__first, __last, __result); >+ >+ return __detail::__move_backward_from_dit(__first, __last, __result); >+ } >+ >+ template >+ typename enable_if< >+ is_same::iterator_category, >+ std::random_access_iterator_tag>::value, Here as well. >+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::type >+ move_backward(_II __first, _II __last, >+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __result) >+ { >+ __glibcxx_requires_can_decrement_range(__first, __last, __result); >+ >+ return __detail::__move_backward_to_dit(__first, __last, __result); > } > #endif Please add "// C++11" after the #endif that corresponds to a __cplusplus check. In general every #endif should have a ocmment, unless the distance between the #if and the #endif is only a few lines. >+ template >+ inline _OI >+ copy(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __first, >+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __last, >+ _OI __result) >+ { >+ return std::copy( >+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__first), >+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__last), >+ __result); I think this would be easier to read as: { typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> _Citer; return std::copy(_Citer(__first), _Citer(__last), __result); >+ template >+ typename __gnu_cxx::__enable_if< >+ __are_same::iterator_category, >+ std::random_access_iterator_tag>::__value, This won't work for iterator categories derived from random_access_iterator_tag. Tag dispatching would work. >+#endif Please add "// C++11" after the #endif