From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 31607 invoked by alias); 20 May 2014 20:37:06 -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 31585 invoked by uid 89); 20 May 2014 20:37:05 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.6 required=5.0 tests=AWL,BAYES_00,FREEMAIL_FROM,RCVD_IN_DNSWL_LOW,SPF_PASS autolearn=ham version=3.3.2 X-Spam-User: qpsmtpd, 2 recipients X-HELO: mail-wi0-f174.google.com Received: from mail-wi0-f174.google.com (HELO mail-wi0-f174.google.com) (209.85.212.174) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-SHA encrypted) ESMTPS; Tue, 20 May 2014 20:37:03 +0000 Received: by mail-wi0-f174.google.com with SMTP id r20so6622789wiv.1 for ; Tue, 20 May 2014 13:37:00 -0700 (PDT) X-Received: by 10.194.85.225 with SMTP id k1mr31688926wjz.49.1400618220252; Tue, 20 May 2014 13:37:00 -0700 (PDT) Received: from [192.168.0.22] (arf62-1-82-237-250-248.fbx.proxad.net. [82.237.250.248]) by mx.google.com with ESMTPSA id bn7sm19715554wjc.7.2014.05.20.13.36.58 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Tue, 20 May 2014 13:36:59 -0700 (PDT) Message-ID: <537BBCE9.3030907@gmail.com> Date: Tue, 20 May 2014 20:37:00 -0000 From: =?ISO-8859-1?Q?Fran=E7ois_Dumont?= User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.5.0 MIME-Version: 1.0 To: Jonathan Wakely CC: "libstdc++@gcc.gnu.org" , gcc-patches Subject: Re: [patch] libstdc++/61143 make unordered containers usable after move References: <53752198.1030705@gmail.com> <20140515205221.GA30753@redhat.com> <537A693C.9040904@gmail.com> <20140520193614.GA5959@redhat.com> In-Reply-To: <20140520193614.GA5959@redhat.com> Content-Type: multipart/mixed; boundary="------------010705060106020207020903" X-SW-Source: 2014-05/txt/msg01675.txt.bz2 This is a multi-part message in MIME format. --------------010705060106020207020903 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 8bit Content-length: 640 On 20/05/2014 21:36, Jonathan Wakely wrote: > > OK. My sketch above avoided calling _M_moved_from() more than once per > object, but the compiler should be able to optimise your version to > avoid multiple calls anyway. > >> Here is the new patch limited to what I really want to commit this time. > > Great. Please commit to trunk and the 4.9 branch - thanks! > > As I have integrated your remarks I won't have time to commit this evening. So I submit this update here, just in case you want to see it again and I will commit tomorrow. I finally use a simplified version of your sketch in the swap implementation. François --------------010705060106020207020903 Content-Type: text/x-patch; name="hashtable.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="hashtable.patch" Content-length: 14250 Index: include/bits/hashtable.h =================================================================== --- include/bits/hashtable.h (revision 210657) +++ include/bits/hashtable.h (working copy) @@ -316,14 +316,49 @@ size_type _M_element_count; _RehashPolicy _M_rehash_policy; + // A single bucket used when only need for 1 bucket. Especially + // interesting in move semantic to leave hashtable with only 1 buckets + // which is not allocated so that we can have those operations noexcept + // qualified. + // Note that we can't leave hashtable with 0 bucket without adding + // numerous checks in the code to avoid 0 modulus. + __bucket_type _M_single_bucket; + + bool + _M_uses_single_bucket(__bucket_type* __bkts) const + { return __builtin_expect(_M_buckets == &_M_single_bucket, false); } + + bool + _M_uses_single_bucket() const + { return _M_uses_single_bucket(_M_buckets); } + __hashtable_alloc& _M_base_alloc() { return *this; } - using __hashtable_alloc::_M_deallocate_buckets; + __bucket_type* + _M_allocate_buckets(size_type __n) + { + if (__builtin_expect(__n == 1, false)) + { + _M_single_bucket = nullptr; + return &_M_single_bucket; + } + return __hashtable_alloc::_M_allocate_buckets(__n); + } + void + _M_deallocate_buckets(__bucket_type* __bkts, size_type __n) + { + if (_M_uses_single_bucket(__bkts)) + return; + + __hashtable_alloc::_M_deallocate_buckets(__bkts, __n); + } + + void _M_deallocate_buckets() - { this->_M_deallocate_buckets(_M_buckets, _M_bucket_count); } + { _M_deallocate_buckets(_M_buckets, _M_bucket_count); } // Gets bucket begin, deals with the fact that non-empty buckets contain // their before begin node. @@ -703,11 +738,7 @@ size_type erase(const key_type& __k) - { - if (__builtin_expect(_M_bucket_count == 0, false)) - return 0; - return _M_erase(__unique_keys(), __k); - } + { return _M_erase(__unique_keys(), __k); } iterator erase(const_iterator, const_iterator); @@ -768,7 +799,7 @@ _M_rehash_policy() { _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint); - _M_buckets = this->_M_allocate_buckets(_M_bucket_count); + _M_buckets = _M_allocate_buckets(_M_bucket_count); } template_M_allocate_buckets(_M_bucket_count); + _M_buckets = _M_allocate_buckets(_M_bucket_count); __try { for (; __f != __l; ++__f) @@ -833,9 +864,9 @@ { // Replacement allocator cannot free existing storage. this->_M_deallocate_nodes(_M_begin()); - if (__builtin_expect(_M_bucket_count != 0, true)) - _M_deallocate_buckets(); - _M_reset(); + _M_before_begin._M_nxt = nullptr; + _M_deallocate_buckets(); + _M_buckets = nullptr; std::__alloc_on_copy(__this_alloc, __that_alloc); __hashtable_base::operator=(__ht); _M_bucket_count = __ht._M_bucket_count; @@ -867,7 +898,7 @@ if (_M_bucket_count != __ht._M_bucket_count) { __former_buckets = _M_buckets; - _M_buckets = this->_M_allocate_buckets(__ht._M_bucket_count); + _M_buckets = _M_allocate_buckets(__ht._M_bucket_count); _M_bucket_count = __ht._M_bucket_count; } else @@ -885,8 +916,7 @@ [&__roan](const __node_type* __n) { return __roan(__n->_M_v()); }); if (__former_buckets) - this->_M_deallocate_buckets(__former_buckets, - __former_bucket_count); + _M_deallocate_buckets(__former_buckets, __former_bucket_count); } __catch(...) { @@ -917,7 +947,7 @@ { __bucket_type* __buckets = nullptr; if (!_M_buckets) - _M_buckets = __buckets = this->_M_allocate_buckets(_M_bucket_count); + _M_buckets = __buckets = _M_allocate_buckets(_M_bucket_count); __try { @@ -964,8 +994,9 @@ _M_reset() noexcept { _M_rehash_policy._M_reset(); - _M_bucket_count = 0; - _M_buckets = nullptr; + _M_bucket_count = 1; + _M_single_bucket = nullptr; + _M_buckets = &_M_single_bucket; _M_before_begin._M_nxt = nullptr; _M_element_count = 0; } @@ -980,12 +1011,16 @@ _M_move_assign(_Hashtable&& __ht, std::true_type) { this->_M_deallocate_nodes(_M_begin()); - if (__builtin_expect(_M_bucket_count != 0, true)) - _M_deallocate_buckets(); - + _M_deallocate_buckets(); __hashtable_base::operator=(std::move(__ht)); _M_rehash_policy = __ht._M_rehash_policy; - _M_buckets = __ht._M_buckets; + if (!__ht._M_uses_single_bucket()) + _M_buckets = __ht._M_buckets; + else + { + _M_buckets = &_M_single_bucket; + _M_single_bucket = __ht._M_single_bucket; + } _M_bucket_count = __ht._M_bucket_count; _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt; _M_element_count = __ht._M_element_count; @@ -1019,7 +1054,7 @@ if (_M_bucket_count != __ht._M_bucket_count) { __former_buckets = _M_buckets; - _M_buckets = this->_M_allocate_buckets(__ht._M_bucket_count); + _M_buckets = _M_allocate_buckets(__ht._M_bucket_count); _M_bucket_count = __ht._M_bucket_count; } else @@ -1093,10 +1128,18 @@ _M_element_count(__ht._M_element_count), _M_rehash_policy(__ht._M_rehash_policy) { + // Update, if necessary, buckets if __ht is using its single bucket. + if (__ht._M_uses_single_bucket()) + { + _M_buckets = &_M_single_bucket; + _M_single_bucket = __ht._M_single_bucket; + } + // Update, if necessary, bucket pointing to before begin that hasn't // moved. if (_M_begin()) _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin; + __ht._M_reset(); } @@ -1139,7 +1182,14 @@ { if (__ht._M_node_allocator() == this->_M_node_allocator()) { - _M_buckets = __ht._M_buckets; + if (__ht._M_uses_single_bucket()) + { + _M_buckets = &_M_single_bucket; + _M_single_bucket = __ht._M_single_bucket; + } + else + _M_buckets = __ht._M_buckets; + _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt; // Update, if necessary, bucket pointing to before begin that hasn't // moved. @@ -1189,15 +1239,34 @@ std::__alloc_on_swap(this->_M_node_allocator(), __x._M_node_allocator()); std::swap(_M_rehash_policy, __x._M_rehash_policy); - std::swap(_M_buckets, __x._M_buckets); + + // Deal properly with potentially moved instances. + if (this->_M_uses_single_bucket()) + { + if (!__x._M_uses_single_bucket()) + { + _M_buckets = __x._M_buckets; + __x._M_buckets = &__x._M_single_bucket; + } + } + else if (__x._M_uses_single_bucket()) + { + __x._M_buckets = _M_buckets; + _M_buckets = &_M_single_bucket; + } + else + 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_element_count, __x._M_element_count); + std::swap(_M_single_bucket, __x._M_single_bucket); // 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; + if (__x._M_begin()) __x._M_buckets[__x._M_bucket_index(__x._M_begin())] = &__x._M_before_begin; @@ -1230,9 +1299,6 @@ _H1, _H2, _Hash, _RehashPolicy, _Traits>:: find(const key_type& __k) { - if (__builtin_expect(_M_bucket_count == 0, false)) - return end(); - __hash_code __code = this->_M_hash_code(__k); std::size_t __n = _M_bucket_index(__k, __code); __node_type* __p = _M_find_node(__n, __k, __code); @@ -1250,9 +1316,6 @@ _H1, _H2, _Hash, _RehashPolicy, _Traits>:: find(const key_type& __k) const { - if (__builtin_expect(_M_bucket_count == 0, false)) - return end(); - __hash_code __code = this->_M_hash_code(__k); std::size_t __n = _M_bucket_index(__k, __code); __node_type* __p = _M_find_node(__n, __k, __code); @@ -1270,9 +1333,6 @@ _H1, _H2, _Hash, _RehashPolicy, _Traits>:: count(const key_type& __k) const { - if (__builtin_expect(_M_bucket_count == 0, false)) - return 0; - __hash_code __code = this->_M_hash_code(__k); std::size_t __n = _M_bucket_index(__k, __code); __node_type* __p = _M_bucket_begin(__n); @@ -1287,7 +1347,7 @@ else if (__result) // All equivalent values are next to each other, if we // found a non-equivalent value after an equivalent one it - // means that we won't find any more equivalent values. + // means that we won't find any new equivalent value. break; if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n) break; @@ -1311,9 +1371,6 @@ _H1, _H2, _Hash, _RehashPolicy, _Traits>:: equal_range(const key_type& __k) { - if (__builtin_expect(_M_bucket_count == 0, false)) - return std::make_pair(end(), end()); - __hash_code __code = this->_M_hash_code(__k); std::size_t __n = _M_bucket_index(__k, __code); __node_type* __p = _M_find_node(__n, __k, __code); @@ -1347,9 +1404,6 @@ _H1, _H2, _Hash, _RehashPolicy, _Traits>:: equal_range(const key_type& __k) const { - if (__builtin_expect(_M_bucket_count == 0, false)) - return std::make_pair(end(), end()); - __hash_code __code = this->_M_hash_code(__k); std::size_t __n = _M_bucket_index(__k, __code); __node_type* __p = _M_find_node(__n, __k, __code); @@ -1944,7 +1998,7 @@ _H1, _H2, _Hash, _RehashPolicy, _Traits>:: _M_rehash_aux(size_type __n, std::true_type) { - __bucket_type* __new_buckets = this->_M_allocate_buckets(__n); + __bucket_type* __new_buckets = _M_allocate_buckets(__n); __node_type* __p = _M_begin(); _M_before_begin._M_nxt = nullptr; std::size_t __bbegin_bkt = 0; @@ -1969,8 +2023,7 @@ __p = __next; } - if (__builtin_expect(_M_bucket_count != 0, true)) - _M_deallocate_buckets(); + _M_deallocate_buckets(); _M_bucket_count = __n; _M_buckets = __new_buckets; } @@ -1986,7 +2039,7 @@ _H1, _H2, _Hash, _RehashPolicy, _Traits>:: _M_rehash_aux(size_type __n, std::false_type) { - __bucket_type* __new_buckets = this->_M_allocate_buckets(__n); + __bucket_type* __new_buckets = _M_allocate_buckets(__n); __node_type* __p = _M_begin(); _M_before_begin._M_nxt = nullptr; @@ -2060,8 +2113,7 @@ __new_buckets[__next_bkt] = __prev_p; } - if (__builtin_expect(_M_bucket_count != 0, true)) - _M_deallocate_buckets(); + _M_deallocate_buckets(); _M_bucket_count = __n; _M_buckets = __new_buckets; } Index: testsuite/23_containers/unordered_set/61143.cc =================================================================== --- testsuite/23_containers/unordered_set/61143.cc (revision 0) +++ testsuite/23_containers/unordered_set/61143.cc (working copy) @@ -0,0 +1,38 @@ +// { dg-options "-std=gnu++11" } + +// Copyright (C) 2014 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 +// . + +// libstdc++/61143 + +#include + +void test01() +{ + std::unordered_set us1, us2; + us1.insert(1); + + us2 = std::move(us1); + + us1.insert(1); +} + +int main() +{ + test01(); + return 0; +} Index: testsuite/23_containers/unordered_set/modifiers/swap.cc =================================================================== --- testsuite/23_containers/unordered_set/modifiers/swap.cc (revision 0) +++ testsuite/23_containers/unordered_set/modifiers/swap.cc (working copy) @@ -0,0 +1,65 @@ +// Copyright (C) 2014 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 +// . + +// { dg-options "-std=gnu++11" } + +#include +#include + +void test01() +{ + bool test __attribute__((unused)) = true; + std::unordered_set us1 { 0, 1 }; + { + std::unordered_set us2(std::move(us1)); + + us1.swap(us2); + + VERIFY( us1.find(0) != us1.end() ); + + us1.insert(2); + + VERIFY( us1.size() == 3 ); + + us2.swap(us1); + + VERIFY( us2.size() == 3 ); + VERIFY( us2.find(2) != us2.end() ); + + us1 = { 3, 4, 5 }; + + VERIFY( us1.size() == 3 ); + VERIFY( us1.bucket_count() >= 3 ); + + std::unordered_set us3(std::move(us1)); + us3 = std::move(us2); + + us1.swap(us2); + + VERIFY( us1.empty() ); + VERIFY( us2.empty() ); + } + + us1 = { 0, 1 }; + VERIFY( us1.size() == 2 ); +} + +int main() +{ + test01(); + return 0; +} --------------010705060106020207020903--