From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 4171 invoked by alias); 13 Apr 2015 13:40:31 -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 4148 invoked by uid 89); 13 Apr 2015 13:40:30 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-0.6 required=5.0 tests=AWL,BAYES_50,SPF_HELO_PASS,SPF_PASS,T_RP_MATCHES_RCVD autolearn=ham version=3.3.2 X-Spam-User: qpsmtpd, 2 recipients 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 (AES256-GCM-SHA384 encrypted) ESMTPS; Mon, 13 Apr 2015 13:40:29 +0000 Received: from int-mx11.intmail.prod.int.phx2.redhat.com (int-mx11.intmail.prod.int.phx2.redhat.com [10.5.11.24]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id t3DDeRAQ027650 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=FAIL); Mon, 13 Apr 2015 09:40:27 -0400 Received: from localhost (ovpn-116-88.ams2.redhat.com [10.36.116.88]) by int-mx11.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id t3DDeQiB009939; Mon, 13 Apr 2015 09:40:27 -0400 Date: Mon, 13 Apr 2015 13:40:00 -0000 From: Jonathan Wakely To: Marc Glisse Cc: libstdc++@gcc.gnu.org, gcc-patches@gcc.gnu.org Subject: Re: [libstdc++/61347] std::distance(list.first(),list.end()) in O(1) Message-ID: <20150413134025.GI9755@redhat.com> References: MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii; format=flowed Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.23 (2014-03-12) X-SW-Source: 2015-04/txt/msg00586.txt.bz2 On 13/04/15 13:42 +0200, Marc Glisse wrote: >this patch makes std::distance(list.first(),list.end()) a constant >time operation when optimizing, with no penalty for other calls. We >could do the test always (no __builtin_constant_p) but then it will >add a small runtime penalty for other calls, someone else can take >responsibility for that. I like the way you've done it. No penalty for other calls is great and IMHO it's OK that the optimisation only happens when optimising. (Does it work even at -Og?) >I could protect the whole overload with >#ifdef __OPTIMIZE__ (at -O0 the compiler does not remove the test >++end==first as dead code), but I assume it is better to minimize >differences. Agreed. >There are other ways to specialize distance, but >overloading __distance seems to have the least drawbacks (most others >involve a new extra file). From an optimization POV, it would be a bit >better to avoid the while loop and instead call a separate function >that does it (say the regular __distance), it would make the function >smaller and thus easier to inline, but it is simpler this way and >works. Is there any (dis)advantage to making one call the other, to avoid duplicating the function bodies? template inline ptrdiff_t __distance(_GLIBCXX_STD_C::_List_iterator<_Tp> __first, _GLIBCXX_STD_C::_List_iterator<_Tp> __last, input_iterator_tag __tag) { typedef _GLIBCXX_STD_C::_List_const_iterator<_Tp> _CIter; return std::__distance(_CIter(__first), _CIter(__last), __tag); } >We could do something similar for std::set, but C++ will not let us >find the address of _Rb_tree_impl::_M_node_count from that of >_Rb_tree_impl::_M_header, except when _Key_compare is pod, which >luckily is an easily available information. Avoiding this complication >is why I insisted on wrapping the size of std::list in a >_List_node for gcc-5, which may look a bit strange at first >sight. Sadly, that node is going to look even stranger when I finish adding support for C++11 allocators, as the type of node becomes dependent on the allocator's pointer, which makes _List_node much more complicated :-( I'll have to remember to add additional __distance overloads to handle the new _List_ptr_iterator and _List_ptr_const_iterator types that will be used for fancy pointers (although if I forget the optimisation will still work for std::list>, just not for the vanishingly small number of people using allocators with fancy pointers). >Index: include/bits/stl_iterator_base_funcs.h >=================================================================== >--- include/bits/stl_iterator_base_funcs.h (revision 222041) >+++ include/bits/stl_iterator_base_funcs.h (working copy) >@@ -107,22 +107,21 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > * n may be negative. > * > * For random access iterators, this uses their @c + and @c - operations > * and are constant time. For other %iterator classes they are linear time. > */ > template > inline typename iterator_traits<_InputIterator>::difference_type > distance(_InputIterator __first, _InputIterator __last) > { > // concept requirements -- taken care of in __distance >- return std::__distance(__first, __last, >- std::__iterator_category(__first)); >+ return __distance(__first, __last, std::__iterator_category(__first)); This should still be a qualified call to std::__distance, otherwise the compiler might end up instantiating things to figure out if there are any associated namespaces, e.g. for vector>::iterator we don't want to know T's base classes and rheir associated namespaces. >+ // Detect when distance is used to compute the size of the whole list. >+ template >+ inline ptrdiff_t >+ __distance(_GLIBCXX_STD_C::_List_iterator<_Tp> __first, >+ _GLIBCXX_STD_C::_List_iterator<_Tp> __last, >+ input_iterator_tag) >+ { >+ typedef _GLIBCXX_STD_C::_List_node _Sentinel; >+ _GLIBCXX_STD_C::_List_iterator<_Tp> __beyond = __last; >+ ++__beyond; >+ bool __whole = __first == __beyond; >+ if (__builtin_constant_p (__whole) && __whole) This is clever :-) This shouldn't interfere with any changes we might need to test before backporting to the gcc-5-branch, so with the std:: qualification restored on the call to __distance it's OK for trunk. (I'll trust your judgment/masurements for whether it's worth making the _List_iterator overload call the _List_const_iterator one.)