From: Marc Glisse <marc.glisse@inria.fr>
To: libstdc++@gcc.gnu.org
Cc: gcc-patches@gcc.gnu.org
Subject: [libstdc++/61347] std::distance(list.first(),list.end()) in O(1)
Date: Mon, 13 Apr 2015 11:42:00 -0000 [thread overview]
Message-ID: <alpine.DEB.2.11.1504131033550.13447@stedding.saclay.inria.fr> (raw)
[-- Attachment #1: Type: TEXT/PLAIN, Size: 1648 bytes --]
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<size_t> for
gcc-5, which may look a bit strange at first sight.
2015-04-13 Marc Glisse <marc.glisse@inria.fr>
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.
--
Marc Glisse
[-- Attachment #2: Type: TEXT/PLAIN, Size: 5140 bytes --]
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<typename _InputIterator>
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<typename _InputIterator, typename _Distance>
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<typename _Tp, typename _Alloc>
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<typename _Tp>
+ 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<size_t> _Sentinel;
+ _GLIBCXX_STD_C::_List_iterator<_Tp> __beyond = __last;
+ ++__beyond;
+ bool __whole = __first == __beyond;
+ if (__builtin_constant_p (__whole) && __whole)
+ return static_cast<const _Sentinel*>(__last._M_node)->_M_data;
+
+ ptrdiff_t __n = 0;
+ while (__first != __last)
+ {
+ ++__first;
+ ++__n;
+ }
+ return __n;
+ }
+
+ template<typename _Tp>
+ 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<size_t> _Sentinel;
+ _GLIBCXX_STD_C::_List_const_iterator<_Tp> __beyond = __last;
+ ++__beyond;
+ bool __whole = __first == __beyond;
+ if (__builtin_constant_p (__whole) && __whole)
+ return static_cast<const _Sentinel*>(__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
+// <http://www.gnu.org/licenses/>.
+
+#include <list>
+#include <iterator>
+#include <testsuite_hooks.h>
+
+__attribute__((__noinline__, __noclone__))
+void testm(std::list<short>& 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<short>& 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<short> l;
+ testm(l);
+ testc(l);
+#endif
+}
next reply other threads:[~2015-04-13 11:42 UTC|newest]
Thread overview: 6+ messages / expand[flat|nested] mbox.gz Atom feed top
2015-04-13 11:42 Marc Glisse [this message]
2015-04-13 13:40 ` Jonathan Wakely
2015-04-13 14:15 ` Marc Glisse
2015-04-13 15:11 ` Jonathan Wakely
2015-04-14 8:24 ` Marc Glisse
2015-04-14 9:32 ` Jonathan Wakely
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=alpine.DEB.2.11.1504131033550.13447@stedding.saclay.inria.fr \
--to=marc.glisse@inria.fr \
--cc=gcc-patches@gcc.gnu.org \
--cc=libstdc++@gcc.gnu.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).