From patchwork Mon Apr 13 11:42:50 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Marc Glisse X-Patchwork-Id: 460746 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 56E691402F4 for ; Mon, 13 Apr 2015 21:43:04 +1000 (AEST) Authentication-Results: ozlabs.org; dkim=pass reason="1024-bit key; unprotected key" header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b=ZkD+XZYC; dkim-adsp=none (unprotected policy); dkim-atps=neutral DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:cc:subject:message-id:mime-version:content-type; q=dns; s=default; b=AN9W6xEun6yraAurzvJI3XKKh7eH3IS9aeC3Dc0MXbe9ixaFJG oa42sEsQVg8baxAbgAhmBF5LnYzEs237la7zp6E2uGZWSrlWBp3mcFf6ebMhStND ccV9HpLFYjrmnUAYtxCqdSDFjFCTRIe9FTwoGRuCmExItXJXlVmwSu6Mw= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:cc:subject:message-id:mime-version:content-type; s= default; bh=VPzAa8JVxAxjGwproHCsmDdYymE=; b=ZkD+XZYCIn0Wof1xhzip YV5cVGoygIk4ZJj1yo6fH1uzGD15kAVokM8XHGWecyZv6AqsDmj75f7UW9ZhOI1+ E7fVq0AksIZlbiJS0YI1L6F5+sVCABVmNtxJEOi2bJjn68iBPZFB4R7NwbQS4MuN iqitxiw1xd6rL22D0rGPr58= Received: (qmail 50353 invoked by alias); 13 Apr 2015 11:42:57 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 50335 invoked by uid 89); 13 Apr 2015 11:42:57 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.0 required=5.0 tests=AWL, BAYES_00, KAM_ASCII_DIVIDERS, KAM_LAZY_DOMAIN_SECURITY, T_RP_MATCHES_RCVD autolearn=no version=3.3.2 X-Spam-User: qpsmtpd, 2 recipients X-HELO: mail2-relais-roc.national.inria.fr Received: from mail2-relais-roc.national.inria.fr (HELO mail2-relais-roc.national.inria.fr) (192.134.164.83) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (CAMELLIA256-SHA encrypted) ESMTPS; Mon, 13 Apr 2015 11:42:55 +0000 Received: from stedding.saclay.inria.fr (HELO stedding) ([193.55.250.194]) by mail2-relais-roc.national.inria.fr with ESMTP/TLS/AES128-SHA; 13 Apr 2015 13:42:51 +0200 Received: from glisse (helo=localhost) by stedding with local-esmtp (Exim 4.84) (envelope-from ) id 1YhclP-00055e-0O; Mon, 13 Apr 2015 13:42:51 +0200 Date: Mon, 13 Apr 2015 13:42:50 +0200 (CEST) From: Marc Glisse To: libstdc++@gcc.gnu.org cc: gcc-patches@gcc.gnu.org Subject: [libstdc++/61347] std::distance(list.first(),list.end()) in O(1) Message-ID: User-Agent: Alpine 2.02 (DEB 1266 2009-07-14) MIME-Version: 1.0 Hello, 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 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. 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. 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. 2015-04-13 Marc Glisse PR libstdc++/61347 * include/bits/stl_iterator_base_funcs.h (distance): Do not qualify the call to __distance. * include/bits/stl_list.h (__distance): New overloads for _List_iterator and _List_const_iterator. * testsuite/23_containers/list/61347.cc: New testcase. 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)); } template inline void __advance(_InputIterator& __i, _Distance __n, input_iterator_tag) { // concept requirements __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) _GLIBCXX_DEBUG_ASSERT(__n >= 0); while (__n--) Index: include/bits/stl_list.h =================================================================== --- include/bits/stl_list.h (revision 222041) +++ include/bits/stl_list.h (working copy) @@ -1861,13 +1861,64 @@ _GLIBCXX_END_NAMESPACE_CXX11 operator>=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) { return !(__x < __y); } /// See std::list::swap(). template inline void swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y) { __x.swap(__y); } _GLIBCXX_END_NAMESPACE_CONTAINER + +#if _GLIBCXX_USE_CXX11_ABI +_GLIBCXX_BEGIN_NAMESPACE_VERSION + + // 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) + return static_cast(__last._M_node)->_M_data; + + ptrdiff_t __n = 0; + while (__first != __last) + { + ++__first; + ++__n; + } + return __n; + } + + template + inline ptrdiff_t + __distance(_GLIBCXX_STD_C::_List_const_iterator<_Tp> __first, + _GLIBCXX_STD_C::_List_const_iterator<_Tp> __last, + input_iterator_tag) + { + typedef _GLIBCXX_STD_C::_List_node _Sentinel; + _GLIBCXX_STD_C::_List_const_iterator<_Tp> __beyond = __last; + ++__beyond; + bool __whole = __first == __beyond; + if (__builtin_constant_p (__whole) && __whole) + return static_cast(__last._M_node)->_M_data; + + ptrdiff_t __n = 0; + while (__first != __last) + { + ++__first; + ++__n; + } + return __n; + } + +_GLIBCXX_END_NAMESPACE_VERSION +#endif } // namespace std #endif /* _STL_LIST_H */ Index: testsuite/23_containers/list/61347.cc =================================================================== --- testsuite/23_containers/list/61347.cc (revision 0) +++ testsuite/23_containers/list/61347.cc (working copy) @@ -0,0 +1,49 @@ +// { dg-options "-std=gnu++11 -O2 -D_GLIBCXX_USE_CXX11_ABI" } + +// Copyright (C) 2015 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +#include +#include +#include + +__attribute__((__noinline__, __noclone__)) +void testm(std::list& l) +{ + bool b = std::distance(l.begin(), l.end()) == l.size(); + VERIFY( __builtin_constant_p(b) ); + VERIFY( b ); +} + +__attribute__((__noinline__, __noclone__)) +void testc(const std::list& l) +{ + bool b = std::distance(l.begin(), l.end()) == l.size(); + VERIFY( __builtin_constant_p(b) ); + VERIFY( b ); +} + +int main() +{ + bool test __attribute__((unused)) = true; + +#if _GLIBCXX_USE_DUAL_ABI + std::list l; + testm(l); + testc(l); +#endif +}