From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-1.mimecast.com (us-smtp-1.mimecast.com [207.211.31.81]) by sourceware.org (Postfix) with ESMTP id 83EDA3851C0A for ; Mon, 8 Jun 2020 23:06:01 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 83EDA3851C0A Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-208-EAH4B49WNzKDjgsBKO2Nxw-1; Mon, 08 Jun 2020 19:02:24 -0400 X-MC-Unique: EAH4B49WNzKDjgsBKO2Nxw-1 Received: from smtp.corp.redhat.com (int-mx06.intmail.prod.int.phx2.redhat.com [10.5.11.16]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id E97ED835B8E; Mon, 8 Jun 2020 23:02:23 +0000 (UTC) Received: from localhost (unknown [10.33.36.10]) by smtp.corp.redhat.com (Postfix) with ESMTP id 502455C5FA; Mon, 8 Jun 2020 23:02:23 +0000 (UTC) Date: Tue, 9 Jun 2020 00:02:22 +0100 From: Jonathan Wakely To: =?iso-8859-1?Q?Fran=E7ois?= Dumont Cc: "libstdc++@gcc.gnu.org" , gcc-patches Subject: Re: libstdc++: Extend memcmp optimization in std::lexicographical_compare Message-ID: <20200608230222.GT4137376@redhat.com> References: <0cfba2ec-cd66-fe64-a41c-4028403d9dea@gmail.com> <20200608182040.GA352899@redhat.com> <20200608210806.GS4137376@redhat.com> MIME-Version: 1.0 In-Reply-To: <20200608210806.GS4137376@redhat.com> X-Clacks-Overhead: GNU Terry Pratchett X-Scanned-By: MIMEDefang 2.79 on 10.5.11.16 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset=iso-8859-1; format=flowed Content-Transfer-Encoding: 8bit Content-Disposition: inline X-Spam-Status: No, score=-16.8 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H4, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=unavailable autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: libstdc++@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libstdc++ mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 08 Jun 2020 23:06:02 -0000 On 08/06/20 22:08 +0100, Jonathan Wakely wrote: >On 08/06/20 19:20 +0100, Jonathan Wakely wrote: >>On 05/06/20 22:24 +0200, François Dumont via Libstdc++ wrote: >>>Hi >>> >>>    Here is the last of my algo patches this time to extend the >>>memcmp optimization to std::deque iterators and _GLIBCXX_DEBUG >>>mode. >>> >>>    To do so I had to return int in implementation details of >>>lexicographical_compare to make sure we can treat a deque iterator >>>range by chunk in a performant way. > >Here's a simpler version, which doesn't alter anything for the >existing code (i.e. all iterators that aren't deque iterators) and >also fixes the infinite loop bug. > >This seems simpler and less invasive. > >Please take a look. I've actually tested it in debug mode now, and ... >diff --git a/libstdc++-v3/include/debug/safe_iterator.tcc b/libstdc++-v3/include/debug/safe_iterator.tcc >index 888ac803ae5..db6a301655f 100644 >--- a/libstdc++-v3/include/debug/safe_iterator.tcc >+++ b/libstdc++-v3/include/debug/safe_iterator.tcc >@@ -470,6 +470,80 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > return __equal_aux1(__first1, __last1, __first2); > } > >+ template+ typename _II2> >+ int This should return bool here. >+ __lexicographical_compare_aux( >+ const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __first1, >+ const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __last1, >+ _II2 __first2, _II2 __last2) >+ { >+ typename ::__gnu_debug::_Distance_traits<_Ite1>::__type __dist1; >+ __glibcxx_check_valid_range2(__first1, __last1, __dist1); >+ __glibcxx_check_valid_range(__first2, __last2); >+ >+ if (__dist1.second > ::__gnu_debug::__dp_equality) >+ return std::__lexicographical_compare_aux(__first1.base(), >+ __last1.base(), >+ __first2, __last2); >+ return std::__lexicographical_compare_aux1(__first1, __last1, >+ __first2, __last2); >+ } >+ >+ template+ typename _Ite2, typename _Seq2, typename _Cat2> >+ int And here. >+ __lexicographical_compare_aux( >+ _II1 __first1, _II1 __last1, >+ const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __first2, >+ const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __last2) >+ { >+ __glibcxx_check_valid_range(__first1, __last1); >+ typename ::__gnu_debug::_Distance_traits<_II1>::__type __dist2; >+ __glibcxx_check_valid_range2(__first2, __last2, __dist2); >+ >+ if (__dist2.second > ::__gnu_debug::__dp_equality) >+ return std::__lexicographical_compare_aux(__first1, __last1, >+ __first2.base(), >+ __last2.base()); >+ return std::__lexicographical_compare_aux1(__first1, __last1, >+ __first2, __last2); >+ } >+ >+ template+ typename _Ite2, typename _Seq2, typename _Cat2> >+ int And here. >+ __lexicographical_compare_aux( >+ const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __first1, >+ const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __last1, >+ const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __first2, >+ const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __last2) >+ { >+ typename ::__gnu_debug::_Distance_traits<_Ite1>::__type __dist1; >+ __glibcxx_check_valid_range2(__first1, __last1, __dist1); >+ typename ::__gnu_debug::_Distance_traits<_Ite2>::__type __dist2; >+ __glibcxx_check_valid_range2(__first2, __last2, __dist2); >+ >+ if (__dist1.second > ::__gnu_debug::__dp_equality) >+ { >+ if (__dist2.second > ::__gnu_debug::__dp_equality) >+ return std::__lexicographical_compare_aux(__first1.base(), >+ __last1.base(), >+ __first2.base(), >+ __last2.base()); >+ return std::__lexicographical_compare_aux(__first1.base(), >+ __last1.base(), >+ __first2, __last2); >+ } >+ >+ if (__dist2.second > ::__gnu_debug::__dp_equality) >+ return std::__lexicographical_compare_aux(__first1, __last1, >+ __first2.base(), >+ __last2.base()); >+ return std::__lexicographical_compare_aux1(__first1, __last1, >+ __first2, __last2); >+ } >+ > _GLIBCXX_END_NAMESPACE_VERSION > } // namespace std