From patchwork Wed Oct 5 14:15:00 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jonathan Wakely X-Patchwork-Id: 678475 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 3spyVm3VnVz9s3v for ; Thu, 6 Oct 2016 01:15:44 +1100 (AEDT) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b=O/9KJlwH; 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:subject:message-id:mime-version:content-type; q=dns; s= default; b=jOYcJDwIuutsMixt1yVqjTX//UjLratGwCDDhBYXN3GLU6fyamOMe kACbZDQ/wHWx5Giie2wRylh9xe+ngJUneh0o1RElifa6jEiut8KReZKtL41eoKr0 doylQVhXCWuMFn/XtlzMgRE6z9sqIxnf4A7+nIZfMp+Z3SRmthfly8= 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:subject:message-id:mime-version:content-type; s= default; bh=GAlk3b5gtYYwSLhzslkkHqbJ8T4=; b=O/9KJlwHhDWzi3x8LDVw SsbjTuFw6fGyNTmOWw1HXt1F285kF26C5aLAuOzlxMI1b6GoncpuCKJWRP//KqJG X7GVqBqRD+oFECYvYuQho+N2EruNXjmwDHov9aEMyPnoph7kI7yVsxAGLQ1n+6/9 TlXJ0rEGkjysvj7Ejrbepo8= Received: (qmail 21230 invoked by alias); 5 Oct 2016 14:15:08 -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 21092 invoked by uid 89); 5 Oct 2016 14:15:06 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-4.5 required=5.0 tests=BAYES_00, RP_MATCHES_RCVD, SPF_HELO_PASS autolearn=ham version=3.3.2 spammy=5987, 9038, 7687, unspecified 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 ESMTP; Wed, 05 Oct 2016 14:15:03 +0000 Received: from int-mx11.intmail.prod.int.phx2.redhat.com (int-mx11.intmail.prod.int.phx2.redhat.com [10.5.11.24]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mx1.redhat.com (Postfix) with ESMTPS id 2B970A0A5C; Wed, 5 Oct 2016 14:15:02 +0000 (UTC) Received: from localhost (ovpn-116-122.ams2.redhat.com [10.36.116.122]) by int-mx11.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id u95EF1kh003674; Wed, 5 Oct 2016 10:15:01 -0400 Date: Wed, 5 Oct 2016 15:15:00 +0100 From: Jonathan Wakely To: libstdc++@gcc.gnu.org, gcc-patches@gcc.gnu.org Subject: [PATCH] Non-backwards compatible improvements to std::deque Message-ID: <20161005141500.GP29482@redhat.com> MIME-Version: 1.0 Content-Disposition: inline X-Clacks-Overhead: GNU Terry Pratchett User-Agent: Mutt/1.7.0 (2016-08-17) This is a proof-of-concept showing how we can fix some known deficiencies in std::deque (24693, 77524, throwing moves) for builds using --enable-symvers=gnu-versioned-namespace, which don't need to preserve ABI compatibility. I'm also considering defining an allocator adaptor that would also enable these fixes, so that std::deque> would be equivalent to std::deque except that it would enable these improvements even for the default --enable-symvers=gnu mode. There should be very little overhead to the extra code, because most of the new branches depend on compile-time constants. Are people interested in seeing this for GCC 7? commit 4db4982f72c14be120b941b3ee8822e1044ab3e5 Author: Jonathan Wakely Date: Tue Oct 4 15:28:21 2016 +0100 Do not allocate memory for empty deques diff --git a/libstdc++-v3/include/bits/deque.tcc b/libstdc++-v3/include/bits/deque.tcc index 389e877..e80eb2c 100644 --- a/libstdc++-v3/include/bits/deque.tcc +++ b/libstdc++-v3/include/bits/deque.tcc @@ -133,6 +133,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER deque<_Tp, _Alloc>:: emplace_front(_Args&&... __args) { + if (!_M_valid_map()) + _M_reallocate_map(_Base::_S_initial_map_size, true); if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first) { _Alloc_traits::construct(this->_M_impl, @@ -150,6 +152,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER deque<_Tp, _Alloc>:: emplace_back(_Args&&... __args) { + if (!_M_valid_map()) + _M_reallocate_map(_Base::_S_initial_map_size, false); if (this->_M_impl._M_finish._M_cur != this->_M_impl._M_finish._M_last - 1) { @@ -903,8 +907,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER deque<_Tp, _Alloc>:: _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front) { - const size_type __old_num_nodes - = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1; + const size_type __old_num_nodes = _M_valid_map() + ? this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1 + : 0; const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add; _Map_pointer __new_nstart; @@ -931,17 +936,38 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER _Map_pointer __new_map = this->_M_allocate_map(__new_map_size); __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2 + (__add_at_front ? __nodes_to_add : 0); - std::copy(this->_M_impl._M_start._M_node, - this->_M_impl._M_finish._M_node + 1, - __new_nstart); - _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size); + if (_M_valid_map()) + { + std::copy(this->_M_impl._M_start._M_node, + this->_M_impl._M_finish._M_node + 1, + __new_nstart); + _M_deallocate_map(this->_M_impl._M_map, + this->_M_impl._M_map_size); + } + else + __try + { + *__new_nstart = this->_M_really_allocate_node(); + } + __catch(...) + { + _M_deallocate_map(__new_map, __new_map_size); + __throw_exception_again; + } this->_M_impl._M_map = __new_map; this->_M_impl._M_map_size = __new_map_size; } this->_M_impl._M_start._M_set_node(__new_nstart); - this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1); + if (__old_num_nodes) + this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1); + else + { + this->_M_impl._M_finish._M_set_node(__new_nstart); + this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first; + this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first; + } } // Overload for deque::iterators, exploiting the "segmented-iterator diff --git a/libstdc++-v3/include/bits/stl_deque.h b/libstdc++-v3/include/bits/stl_deque.h index 3b1f8e9..3af3aba 100644 --- a/libstdc++-v3/include/bits/stl_deque.h +++ b/libstdc++-v3/include/bits/stl_deque.h @@ -154,7 +154,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER iterator _M_const_cast() const _GLIBCXX_NOEXCEPT - { return iterator(_M_cur, _M_node); } + { return _M_cur ? iterator(_M_cur, _M_node) : iterator(); } reference operator*() const _GLIBCXX_NOEXCEPT @@ -351,6 +351,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER operator-(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x, const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) _GLIBCXX_NOEXCEPT { + if (!__x._M_node && !__y._M_node) + return 0; return typename _Deque_iterator<_Tp, _Ref, _Ptr>::difference_type (_Deque_iterator<_Tp, _Ref, _Ptr>::_S_buffer_size()) * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first) @@ -363,6 +365,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER operator-(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x, const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT { + if (!__x._M_node && !__y._M_node) + return 0; return typename _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type (_Deque_iterator<_Tp, _RefL, _PtrL>::_S_buffer_size()) * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first) @@ -473,6 +477,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER #endif static const bool _S_recycle_nodes = bool(_GLIBCXX_INLINE_VERSION); + static const bool _S_allow_null_map = bool(_GLIBCXX_INLINE_VERSION); typedef typename _Alloc_traits::template rebind<_Ptr>::other _Map_alloc_type; @@ -518,7 +523,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER this->_M_impl._M_swap_data(__x._M_impl); } - _Deque_base(_Deque_base&& __x) + _Deque_base(_Deque_base&& __x) noexcept(_S_allow_null_map) : _Deque_base(std::move(__x), typename _Alloc_traits::is_always_equal{}) { } @@ -684,6 +689,20 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER if (!_M_impl._M_map) return std::move(_M_impl); + if (_S_allow_null_map) + { + _Deque_impl __ret{std::move(_M_get_Tp_allocator())}; + _M_impl._M_swap_data(__ret); + return __ret; + } + + // This path is complicated because the standard allows a moved-from + // allocator to compare unequal to its previous value. To be exception + // safe we need to create an empty map using a moved-from allocator + // before making any changes to this->_M_impl. This relies on the + // assumption that the two moved-from allocators compare equal, but + // there doesn't seem to be any way to avoid that. + // Create a copy of the current allocator. _Tp_alloc_type __alloc{_M_get_Tp_allocator()}; // Put that copy in a moved-from state. @@ -725,6 +744,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER _Deque_base<_Tp, _Alloc>:: _M_initialize_map(size_t __num_elements) { + if (_S_allow_null_map && __num_elements == 0) + return; + const size_t __num_nodes = (__num_elements/ __deque_buf_size(sizeof(_Tp)) + 1); @@ -927,7 +949,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER /** * @brief Creates a %deque with no elements. */ - deque() : _Base() { } + deque() _GLIBCXX_NOEXCEPT_IF(_Base::_S_allow_null_map) + : _Base() { } /** * @brief Creates a %deque with no elements. @@ -1001,11 +1024,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * The newly-created %deque contains the exact contents of @a __x. * The contents of @a __x are a valid, but unspecified %deque. */ - deque(deque&& __x) + deque(deque&& __x) noexcept(_Base::_S_allow_null_map) : _Base(std::move(__x)) { } /// Copy constructor with alternative allocator deque(const deque& __x, const allocator_type& __a) + noexcept(_Base::_S_allow_null_map + && _Alloc_traits::is_always_equal::value) : _Base(__a, __x.size()) { std::__uninitialized_copy_a(__x.begin(), __x.end(), this->_M_impl._M_start, @@ -1546,6 +1571,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER void push_front(const value_type& __x) { + if (!_M_valid_map()) + _M_reallocate_map(_Base::_S_initial_map_size, true); if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first) { _Alloc_traits::construct(this->_M_impl, @@ -1567,6 +1594,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER emplace_front(_Args&&... __args); #endif + bool + _M_valid_map() const _GLIBCXX_NOEXCEPT + { return !_Base::_S_allow_null_map || this->_M_impl._M_map; } + /** * @brief Add data to the end of the %deque. * @param __x Data to be added. @@ -1579,6 +1610,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER void push_back(const value_type& __x) { + if (!_M_valid_map()) + _M_reallocate_map(_Base::_S_initial_map_size, false); if (this->_M_impl._M_finish._M_cur != this->_M_impl._M_finish._M_last - 1) { @@ -2156,10 +2189,15 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER iterator _M_reserve_elements_at_back(size_type __n) { - const size_type __vacancies = (this->_M_impl._M_finish._M_last - - this->_M_impl._M_finish._M_cur) - 1; - if (__n > __vacancies) - _M_new_elements_at_back(__n - __vacancies); + if (!_M_valid_map()) + _M_new_elements_at_back(__n); + else + { + const size_type __vacancies = (this->_M_impl._M_finish._M_last + - this->_M_impl._M_finish._M_cur) - 1; + if (__n > __vacancies) + _M_new_elements_at_back(__n - __vacancies); + } return this->_M_impl._M_finish + difference_type(__n); } @@ -2229,12 +2267,16 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { // Create new data first, so if allocation fails there are no effects. deque __newobj(std::forward<_Args>(__args)...); - // Free existing storage using existing allocator. - clear(); - _M_deallocate_node(*begin()._M_node); // one node left after clear() - _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size); - this->_M_impl._M_map = nullptr; - this->_M_impl._M_map_size = 0; + if (this->_M_impl._M_map) + { + // Free existing storage using existing allocator. + clear(); + // Free the single node left after clear(), then free the map. + _M_deallocate_node(*this->_M_impl._M_start._M_node); + _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size); + this->_M_impl._M_map = nullptr; + this->_M_impl._M_map_size = 0; + } // Take ownership of replacement memory. this->_M_impl._M_swap_data(__newobj._M_impl); } commit 2c816add85ea0a8c720d5e790b162b9fe2732c19 Author: Jonathan Wakely Date: Mon Oct 3 16:59:43 2016 +0100 Recycle deque nodes diff --git a/libstdc++-v3/include/bits/deque.tcc b/libstdc++-v3/include/bits/deque.tcc index 96ec9f8..389e877 100644 --- a/libstdc++-v3/include/bits/deque.tcc +++ b/libstdc++-v3/include/bits/deque.tcc @@ -532,7 +532,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER void deque<_Tp, _Alloc>:: _M_pop_back_aux() { - _M_deallocate_node(this->_M_impl._M_finish._M_first); + this->_M_dispose_node(this->_M_impl._M_finish._M_first); this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1); this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1; _Alloc_traits::destroy(_M_get_Tp_allocator(), @@ -550,7 +550,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { _Alloc_traits::destroy(_M_get_Tp_allocator(), this->_M_impl._M_start._M_cur); - _M_deallocate_node(this->_M_impl._M_start._M_first); + this->_M_dispose_node(this->_M_impl._M_start._M_first); this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1); this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first; } diff --git a/libstdc++-v3/include/bits/stl_deque.h b/libstdc++-v3/include/bits/stl_deque.h index 7192f65..3b1f8e9 100644 --- a/libstdc++-v3/include/bits/stl_deque.h +++ b/libstdc++-v3/include/bits/stl_deque.h @@ -472,6 +472,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER typedef typename _Alloc_traits::const_pointer _Ptr_const; #endif + static const bool _S_recycle_nodes = bool(_GLIBCXX_INLINE_VERSION); + typedef typename _Alloc_traits::template rebind<_Ptr>::other _Map_alloc_type; typedef __gnu_cxx::__alloc_traits<_Map_alloc_type> _Map_alloc_traits; @@ -596,7 +598,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { return _Map_alloc_type(_M_get_Tp_allocator()); } _Ptr - _M_allocate_node() + _M_really_allocate_node() { typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Traits; return _Traits::allocate(_M_impl, __deque_buf_size(sizeof(_Tp))); @@ -609,20 +611,62 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER _Traits::deallocate(_M_impl, __p, __deque_buf_size(sizeof(_Tp))); } + _Ptr + _M_allocate_node() + { + if (_S_recycle_nodes) + if (_Ptr& __cached = _M_cached_node()) + { + _Ptr __ret = __cached; + __cached = _Ptr(); + return __ret; + } + return _M_really_allocate_node(); + } + + void + _M_dispose_node(_Ptr __p) _GLIBCXX_NOEXCEPT + { + if (_S_recycle_nodes) + { + _Ptr& __cached = _M_cached_node(); + if (!__cached) + { + __cached = __p; + return; + } + } + _M_deallocate_node(__p); + } + _Map_pointer _M_allocate_map(size_t __n) { + __n += size_t(_S_recycle_nodes); _Map_alloc_type __map_alloc = _M_get_map_allocator(); - return _Map_alloc_traits::allocate(__map_alloc, __n); + _Map_pointer __p = _Map_alloc_traits::allocate(__map_alloc, __n); + if (_S_recycle_nodes) + *__p++ = _Ptr(); + return __p; } void _M_deallocate_map(_Map_pointer __p, size_t __n) _GLIBCXX_NOEXCEPT { + if (_S_recycle_nodes) + { + ++__n; + if (*--__p) + _M_deallocate_node(*__p); + } _Map_alloc_type __map_alloc = _M_get_map_allocator(); _Map_alloc_traits::deallocate(__map_alloc, __p, __n); } + _Ptr& + _M_cached_node() _GLIBCXX_NOEXCEPT + { return *(_M_impl._M_map - 1); } + protected: void _M_initialize_map(size_t); void _M_create_nodes(_Map_pointer __nstart, _Map_pointer __nfinish); @@ -724,7 +768,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER __try { for (__cur = __nstart; __cur < __nfinish; ++__cur) - *__cur = this->_M_allocate_node(); + *__cur = this->_M_really_allocate_node(); } __catch(...) {