From patchwork Wed Oct 31 22:14:50 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: =?utf-8?q?Fran=C3=A7ois_Dumont?= X-Patchwork-Id: 196018 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]) by ozlabs.org (Postfix) with SMTP id 7C8F82C0199 for ; Thu, 1 Nov 2012 09:15:23 +1100 (EST) Comment: DKIM? See http://www.dkim.org DKIM-Signature: v=1; a=rsa-sha1; c=relaxed/relaxed; d=gcc.gnu.org; s=default; x=1352326524; h=Comment: DomainKey-Signature:Received:Received:Received:Received:Received: Received:Message-ID:Date:From:User-Agent:MIME-Version:To:CC: Subject:References:In-Reply-To:Content-Type:Mailing-List: Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:Sender:Delivered-To; bh=Ze6viQwA08Swu0zlKvqBKYFAIog=; b=N0rwfw/cLo6oud58tpurCyoyu2I26mWhVnh+1C2i3wBhIHMNXOTv0aPp7HA5qK nji1RDaxrKcFeesRV2LqmzoaYoixws2gk6KRsB3weAcSWN4txOm1R6dE/AOZb8cw AuA8D+LPSHE4PVoMx3+EJ9CxOw+JrwUw9dGyu66muRRmw= Comment: DomainKeys? See http://antispam.yahoo.com/domainkeys DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=default; d=gcc.gnu.org; h=Received:Received:X-SWARE-Spam-Status:X-Spam-Check-By:Received:Received:Received:Received:Message-ID:Date:From:User-Agent:MIME-Version:To:CC:Subject:References:In-Reply-To:Content-Type:Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help:Sender:Delivered-To; b=y3U3O/kc8gJR6OpGB7TQgztVIlepVm2hMKn8OymZC+/sbDcyATGVc6uhg/jb9N EpRL91DKxUqZ0LUlwMWlYsUgvNPL0HB9iGlf3WFCgD1fzdxWIyr8yksgEBsn7u9x bJN/u6UrWPZion4hK7DhuMdcNnHlpXUC7NaESiKi+NFow=; Received: (qmail 8038 invoked by alias); 31 Oct 2012 22:15:09 -0000 Received: (qmail 7922 invoked by uid 22791); 31 Oct 2012 22:15:01 -0000 X-SWARE-Spam-Status: No, hits=-5.2 required=5.0 tests=AWL, BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, KHOP_RCVD_TRUST, KHOP_THREADED, RCVD_IN_DNSWL_LOW, RCVD_IN_HOSTKARMA_YE X-Spam-Check-By: sourceware.org Received: from mail-we0-f175.google.com (HELO mail-we0-f175.google.com) (74.125.82.175) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Wed, 31 Oct 2012 22:14:55 +0000 Received: by mail-we0-f175.google.com with SMTP id t44so921413wey.20 for ; Wed, 31 Oct 2012 15:14:53 -0700 (PDT) Received: by 10.180.8.197 with SMTP id t5mr4947885wia.5.1351721693837; Wed, 31 Oct 2012 15:14:53 -0700 (PDT) Received: from localhost.localdomain (arf62-1-82-237-250-248.fbx.proxad.net. [82.237.250.248]) by mx.google.com with ESMTPS id j8sm19694225wiy.9.2012.10.31.15.14.51 (version=SSLv3 cipher=OTHER); Wed, 31 Oct 2012 15:14:52 -0700 (PDT) Message-ID: <5091A2DA.5090205@gmail.com> Date: Wed, 31 Oct 2012 23:14:50 +0100 From: =?ISO-8859-1?Q?Fran=E7ois_Dumont?= User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:15.0) Gecko/20120829 Thunderbird/15.0 MIME-Version: 1.0 To: Jonathan Wakely CC: "libstdc++@gcc.gnu.org" , gcc-patches Subject: Re: Optimize hashtable allocator References: <50904047.1060702@gmail.com> In-Reply-To: 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 On 10/30/2012 10:26 PM, Jonathan Wakely wrote: > > I try to adapt pretty printer code but haven't been able to test it as I > don't have the necessary gdb version and don't have time to update it at the > moment. If you prefer I can leave it untouched. > Please try to install a newer GDB, building it is as simple as > ./configure --prefix=PREFIX && make install and takes a few minutes. > You need GDB 7.x for GCC 4.7 anyway, which would also be new enough to > test the pretty printers. Either test the changes or don't change the > printers. Are you sure all GDB 7.x should work ? I have gdb 7.1 and when running pretty printers tests I have: Spawning: gdb -nw -nx -quiet -batch -ex "python print gdb.lookup_global_symbol" ESC[?1034hTraceback (most recent call last): File "", line 1, in AttributeError: 'module' object has no attribute 'lookup_global_symbol' Error while executing Python code. UNSUPPORTED: prettyprinters.exp > >> By the way, there is suspect >> code in it. It tries to deal with std and std::tr1 unordered containers >> through the same python code but it won't work anymore for iterators. They >> are different in std and tr1 modes so there are adaptations missing if we >> still want to support both versions. > Yes we want to support both. > > Can the difference between the iterators be handled easily the same > way I changed the printers to use _M_h when necessary, or should be > just have separate StdHashtableIterator and Tr1HashtableIterator > printers? Yes, I think the same code could deal both type of iterators. > > >> 2012-09-29 François Dumont > 2012-10 :) > > + > + template > + _Before_begin(_Alloc __a) > + : _NodeAlloc(__a) > + { } > > Can this use a "universal reference" (to use Scott Meyers's term) to > avoid a copy? > > template > _Before_begin(_Alloc&& __a) > : _NodeAlloc(std::forward<_Alloc>(__a)) > { } > > There's no need to use Doxygen for _Before_begin, it's not for end users. > Here is the patch I came to. I use the 'universal reference' like you propose but some tests started to fail because I think gcc called it instead of the move constructor. Making those constructors explicit, even if using default implementation, fix the tests. I still need to check if tests are checking instantiation of unordered containers passing an allocator instance to confirm that the universal reference behaves correctly. I should be able to do so next week. François Index: include/bits/hashtable_policy.h =================================================================== --- include/bits/hashtable_policy.h (revision 192992) +++ include/bits/hashtable_policy.h (working copy) @@ -1708,6 +1708,24 @@ return true; } + /** + * This type is to combine a _Hash_node_base instance with an allocator + * instance through inheritance to benefit from EBO when possible. + */ + template + struct _Before_begin : public _NodeAlloc + { + _Hash_node_base _M_node; + + _Before_begin(const _Before_begin&) = default; + _Before_begin(_Before_begin&&) = default; + + template + _Before_begin(_Alloc&& __a) + : _NodeAlloc(std::forward<_Alloc>(__a)) + { } + }; + //@} hashtable-detail _GLIBCXX_END_NAMESPACE_VERSION } // namespace __detail Index: include/bits/hashtable.h =================================================================== --- include/bits/hashtable.h (revision 192992) +++ include/bits/hashtable.h (working copy) @@ -99,7 +99,7 @@ * Each _Hashtable data structure has: * * - _Bucket[] _M_buckets - * - _Hash_node_base _M_before_begin + * - _Hash_node_base _M_bbegin * - size_type _M_bucket_count * - size_type _M_element_count * @@ -302,17 +302,31 @@ _Node_allocator_type; typedef typename _Alloc::template rebind<__bucket_type>::other _Bucket_allocator_type; - typedef typename _Alloc::template rebind::other - _Value_allocator_type; + using __before_begin = __detail::_Before_begin<_Node_allocator_type>; - _Node_allocator_type _M_node_allocator; __bucket_type* _M_buckets; size_type _M_bucket_count; - __node_base _M_before_begin; + __before_begin _M_bbegin; size_type _M_element_count; _RehashPolicy _M_rehash_policy; + _Node_allocator_type& + _M_node_allocator() + { return _M_bbegin; } + + const _Node_allocator_type& + _M_node_allocator() const + { return _M_bbegin; } + + __node_base& + _M_before_begin() + { return _M_bbegin._M_node; } + + const __node_base& + _M_before_begin() const + { return _M_bbegin._M_node; } + template __node_type* _M_allocate_node(_Args&&... __args); @@ -337,7 +351,7 @@ __node_type* _M_begin() const - { return static_cast<__node_type*>(_M_before_begin._M_nxt); } + { return static_cast<__node_type*>(_M_before_begin()._M_nxt); } public: // Constructor, destructor, assignment, swap @@ -455,11 +469,11 @@ allocator_type get_allocator() const noexcept - { return allocator_type(_M_node_allocator); } + { return allocator_type(_M_node_allocator()); } size_type max_size() const noexcept - { return _M_node_allocator.max_size(); } + { return _M_node_allocator().max_size(); } // Observers key_equal @@ -685,15 +699,15 @@ _H1, _H2, _Hash, _RehashPolicy, _Traits>:: _M_allocate_node(_Args&&... __args) { - __node_type* __n = _M_node_allocator.allocate(1); + __node_type* __n = _M_node_allocator().allocate(1); __try { - _M_node_allocator.construct(__n, std::forward<_Args>(__args)...); + _M_node_allocator().construct(__n, std::forward<_Args>(__args)...); return __n; } __catch(...) { - _M_node_allocator.deallocate(__n, 1); + _M_node_allocator().deallocate(__n, 1); __throw_exception_again; } } @@ -707,8 +721,8 @@ _H1, _H2, _Hash, _RehashPolicy, _Traits>:: _M_deallocate_node(__node_type* __n) { - _M_node_allocator.destroy(__n); - _M_node_allocator.deallocate(__n, 1); + _M_node_allocator().destroy(__n); + _M_node_allocator().deallocate(__n, 1); } template:: _M_allocate_buckets(size_type __n) { - _Bucket_allocator_type __alloc(_M_node_allocator); + _Bucket_allocator_type __alloc(_M_node_allocator()); __bucket_type* __p = __alloc.allocate(__n); __builtin_memset(__p, 0, __n * sizeof(__bucket_type)); @@ -754,7 +768,7 @@ _H1, _H2, _Hash, _RehashPolicy, _Traits>:: _M_deallocate_buckets(__bucket_type* __p, size_type __n) { - _Bucket_allocator_type __alloc(_M_node_allocator); + _Bucket_allocator_type __alloc(_M_node_allocator()); __alloc.deallocate(__p, __n); } @@ -786,8 +800,8 @@ : __hashtable_base(__exk, __h1, __h2, __h, __eq), __map_base(), __rehash_base(), - _M_node_allocator(__a), _M_bucket_count(0), + _M_bbegin(__a), _M_element_count(0), _M_rehash_policy() { @@ -815,8 +829,8 @@ : __hashtable_base(__exk, __h1, __h2, __h, __eq), __map_base(), __rehash_base(), - _M_node_allocator(__a), _M_bucket_count(0), + _M_bbegin(__a), _M_element_count(0), _M_rehash_policy() { @@ -854,15 +868,15 @@ : __hashtable_base(__ht), __map_base(__ht), __rehash_base(__ht), - _M_node_allocator(__ht._M_node_allocator), _M_bucket_count(__ht._M_bucket_count), + _M_bbegin(__ht._M_bbegin), _M_element_count(__ht._M_element_count), _M_rehash_policy(__ht._M_rehash_policy) { _M_buckets = _M_allocate_buckets(_M_bucket_count); __try { - if (!__ht._M_before_begin._M_nxt) + if (!__ht._M_before_begin()._M_nxt) return; // First deal with the special first node pointed to by @@ -870,8 +884,8 @@ const __node_type* __ht_n = __ht._M_begin(); __node_type* __this_n = _M_allocate_node(__ht_n->_M_v); this->_M_copy_code(__this_n, __ht_n); - _M_before_begin._M_nxt = __this_n; - _M_buckets[_M_bucket_index(__this_n)] = &_M_before_begin; + _M_before_begin()._M_nxt = __this_n; + _M_buckets[_M_bucket_index(__this_n)] = &_M_before_begin(); // Then deal with other nodes. __node_base* __prev_n = __this_n; @@ -904,20 +918,19 @@ : __hashtable_base(__ht), __map_base(__ht), __rehash_base(__ht), - _M_node_allocator(std::move(__ht._M_node_allocator)), _M_buckets(__ht._M_buckets), _M_bucket_count(__ht._M_bucket_count), - _M_before_begin(__ht._M_before_begin._M_nxt), + _M_bbegin(std::move(__ht._M_bbegin)), _M_element_count(__ht._M_element_count), _M_rehash_policy(__ht._M_rehash_policy) { // Update, if necessary, bucket pointing to before begin that hasn't move. if (_M_begin()) - _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin; + _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin(); __ht._M_rehash_policy = _RehashPolicy(); __ht._M_bucket_count = __ht._M_rehash_policy._M_next_bkt(0); __ht._M_buckets = __ht._M_allocate_buckets(__ht._M_bucket_count); - __ht._M_before_begin._M_nxt = nullptr; + __ht._M_before_begin()._M_nxt = nullptr; __ht._M_element_count = 0; } @@ -949,22 +962,22 @@ // _GLIBCXX_RESOLVE_LIB_DEFECTS // 431. Swapping containers with unequal allocators. - std::__alloc_swap<_Node_allocator_type>::_S_do_it(_M_node_allocator, - __x._M_node_allocator); + std::__alloc_swap<_Node_allocator_type>::_S_do_it(_M_node_allocator(), + __x._M_node_allocator()); std::swap(_M_rehash_policy, __x._M_rehash_policy); std::swap(_M_buckets, __x._M_buckets); std::swap(_M_bucket_count, __x._M_bucket_count); - std::swap(_M_before_begin._M_nxt, __x._M_before_begin._M_nxt); + std::swap(_M_before_begin()._M_nxt, __x._M_before_begin()._M_nxt); std::swap(_M_element_count, __x._M_element_count); // Fix buckets containing the _M_before_begin pointers that // can't be swapped. if (_M_begin()) - _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin; + _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin(); if (__x._M_begin()) __x._M_buckets[__x._M_bucket_index(__x._M_begin())] - = &(__x._M_before_begin); + = &(__x._M_before_begin()); } template_M_nxt = _M_before_begin._M_nxt; - _M_before_begin._M_nxt = __node; + __node->_M_nxt = _M_before_begin()._M_nxt; + _M_before_begin()._M_nxt = __node; if (__node->_M_nxt) // We must update former begin bucket that is pointing to // _M_before_begin. _M_buckets[_M_bucket_index(__node->_M_next())] = __node; - _M_buckets[__bkt] = &_M_before_begin; + _M_buckets[__bkt] = &_M_before_begin(); } } @@ -1193,8 +1206,8 @@ _M_buckets[__next_bkt] = _M_buckets[__bkt]; // Second update before begin node if necessary - if (&_M_before_begin == _M_buckets[__bkt]) - _M_before_begin._M_nxt = __next; + if (&_M_before_begin() == _M_buckets[__bkt]) + _M_before_begin()._M_nxt = __next; _M_buckets[__bkt] = nullptr; } } @@ -1614,7 +1627,7 @@ _M_deallocate_nodes(_M_begin()); __builtin_memset(_M_buckets, 0, _M_bucket_count * sizeof(__bucket_type)); _M_element_count = 0; - _M_before_begin._M_nxt = nullptr; + _M_before_begin()._M_nxt = nullptr; } template_M_nxt = _M_before_begin._M_nxt; - _M_before_begin._M_nxt = __p; - __new_buckets[__bkt] = &_M_before_begin; + __p->_M_nxt = _M_before_begin()._M_nxt; + _M_before_begin()._M_nxt = __p; + __new_buckets[__bkt] = &_M_before_begin(); if (__p->_M_nxt) __new_buckets[__bbegin_bkt] = __p; __bbegin_bkt = __bkt; @@ -1718,7 +1731,7 @@ __bucket_type* __new_buckets = _M_allocate_buckets(__n); __node_type* __p = _M_begin(); - _M_before_begin._M_nxt = nullptr; + _M_before_begin()._M_nxt = nullptr; std::size_t __bbegin_bkt; std::size_t __prev_bkt; __node_type* __prev_p = nullptr; @@ -1763,9 +1776,9 @@ if (!__new_buckets[__bkt]) { - __p->_M_nxt = _M_before_begin._M_nxt; - _M_before_begin._M_nxt = __p; - __new_buckets[__bkt] = &_M_before_begin; + __p->_M_nxt = _M_before_begin()._M_nxt; + _M_before_begin()._M_nxt = __p; + __new_buckets[__bkt] = &_M_before_begin(); if (__p->_M_nxt) __new_buckets[__bbegin_bkt] = __p; __bbegin_bkt = __bkt;