From patchwork Sat Jun 29 08:24:55 2013 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: 255720 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 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (Client CN "localhost", Issuer "www.qmailtoaster.com" (not verified)) by ozlabs.org (Postfix) with ESMTPS id 75D2B2C0085 for ; Sat, 29 Jun 2013 18:25:22 +1000 (EST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :message-id:date:from:mime-version:to:cc:subject:references :in-reply-to:content-type; q=dns; s=default; b=k4DsguaOVpbT0YjIG 413TA3mtx1SDoWrm4MA6WnPevBu1bG6tqrZzbEBAtNyrQ6whqoahGObEnXNd4JAo s3QGG5WeEaWiYll0/BjyZMc3P9EDuCtPA8QHDInM6Qo/MHXV+D3/ZXFFskB8ZVlC r9/YiN9LEl1/3gwdGSIciIeT00= 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 :message-id:date:from:mime-version:to:cc:subject:references :in-reply-to:content-type; s=default; bh=xWHrk4ReqgdneLbLYdvabJ3 Edpk=; b=DhM2c1RJQo25CNiUwTOoui6zipVf45AusBT6z49oxXhgZVE0775oVLM BpwPcJYhKirnF+uqZqjSf4BoMNjI/Us/EAzATUfi7ljlI6eOljoKKoGAl9bnBbfU iV7oTAwDPUdrF+aX0E66waaKHRV4aw5iQr1Bguz/cggDdXrTBuTE= Received: (qmail 28711 invoked by alias); 29 Jun 2013 08:25:06 -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 28689 invoked by uid 89); 29 Jun 2013 08:25:05 -0000 X-Spam-SWARE-Status: No, score=-3.5 required=5.0 tests=AWL, BAYES_00, FREEMAIL_FROM, KHOP_THREADED, RCVD_IN_DNSWL_LOW, RCVD_IN_HOSTKARMA_YE, SPF_PASS autolearn=ham version=3.3.1 X-Spam-User: qpsmtpd, 2 recipients Received: from mail-wi0-f174.google.com (HELO mail-wi0-f174.google.com) (209.85.212.174) by sourceware.org (qpsmtpd/0.84/v0.84-167-ge50287c) with ESMTP; Sat, 29 Jun 2013 08:25:01 +0000 Received: by mail-wi0-f174.google.com with SMTP id k10so1525678wiv.1 for ; Sat, 29 Jun 2013 01:24:59 -0700 (PDT) X-Received: by 10.180.189.68 with SMTP id gg4mr5333205wic.27.1372494298955; Sat, 29 Jun 2013 01:24:58 -0700 (PDT) Received: from localhost.localdomain (arf62-1-82-237-250-248.fbx.proxad.net. [82.237.250.248]) by mx.google.com with ESMTPSA id fd3sm2434728wic.10.2013.06.29.01.24.56 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Sat, 29 Jun 2013 01:24:57 -0700 (PDT) Message-ID: <51CE99D7.2050001@gmail.com> Date: Sat, 29 Jun 2013 10:24:55 +0200 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: Paolo Carlini , "libstdc++@gcc.gnu.org" , gcc-patches Subject: Re: Unordered container insertion hints References: <5193E6AE.8020306@gmail.com> <519E75B2.4040000@gmail.com> <519E9F88.3010309@oracle.com> <51B0F21A.9030707@gmail.com> <51B8D627.3000203@gmail.com> <51C20CDC.7040200@gmail.com> In-Reply-To: X-Virus-Found: No Patch applied, I also needed to update some dg-error line numbers, it was not part of the original patch. The only remaining thing will be to update the doxygen links on the unordered containers to point to the new hint doc. 2013-06-29 François Dumont * include/bits/hashtable_policy.h (_Insert_base): Consider hint in insert methods. * include/bits/hashtable.h: Likewise. * testsuite/23_containers/unordered_multimap/insert/hint.cc: New. * testsuite/performance/23_containers/insert/unordered_multiset_hint.cc: New. * testsuite/23_containers/unordered_set/instantiation_neg.cc: Adjust dg-error line number. * testsuite/23_containers/unordered_set/ not_default_constructible_hash_neg.cc: Likewise. * doc/xml/manual/containers.xml: Document hinting in unordered containers. François On 06/28/2013 01:46 PM, Jonathan Wakely wrote: > On 23 June 2013 13:51, Jonathan Wakely wrote: >> On 19 June 2013 20:56, François Dumont wrote: >>> Still no chance to have a look ? >> I'll try to finish reviewing it today, thanks for the reminder. > Sorry for the delay. The patch is OK, with a few small changes to the new docs: > > Please change "rational" to "rationale" > > "can require to update the bucket" should be "can require updating the bucket" > > "need to compute following node hash code." should be "need to compute > the following node's hash code." > > "won't compute next element hash code" should be "won't compute the > next element's hash code" > > "bench" should be "benchmark" > > I would say "more harm than good" instead of "more bad than good" > > Thanks! > Index: include/bits/hashtable_policy.h =================================================================== --- include/bits/hashtable_policy.h (revision 200491) +++ include/bits/hashtable_policy.h (working copy) @@ -612,7 +612,6 @@ using __unique_keys = typename __hashtable_base::__unique_keys; using __ireturn_type = typename __hashtable_base::__ireturn_type; - using __iconv_type = typename __hashtable_base::__iconv_type; __hashtable& _M_conjure_hashtable() @@ -626,8 +625,11 @@ } iterator - insert(const_iterator, const value_type& __v) - { return __iconv_type()(insert(__v)); } + insert(const_iterator __hint, const value_type& __v) + { + __hashtable& __h = _M_conjure_hashtable(); + return __h._M_insert(__hint, __v, __unique_keys()); + } void insert(initializer_list __l) @@ -711,8 +713,11 @@ } iterator - insert(const_iterator, value_type&& __v) - { return insert(std::move(__v)).first; } + insert(const_iterator __hint, value_type&& __v) + { + __hashtable& __h = this->_M_conjure_hashtable(); + return __h._M_insert(__hint, std::move(__v), __unique_keys()); + } }; /// Specialization. @@ -745,9 +750,12 @@ } iterator - insert(const_iterator, value_type&& __v) - { return insert(std::move(__v)); } - }; + insert(const_iterator __hint, value_type&& __v) + { + __hashtable& __h = this->_M_conjure_hashtable(); + return __h._M_insert(__hint, std::move(__v), __unique_keys()); + } + }; /// Specialization. template> iterator - insert(const_iterator, _Pair&& __v) - { return __iconv_type()(insert(std::forward<_Pair>(__v))); } + insert(const_iterator __hint, _Pair&& __v) + { + __hashtable& __h = this->_M_conjure_hashtable(); + return __h._M_emplace(__hint, __unique_keys(), + std::forward<_Pair>(__v)); + } }; /** @@ -1470,10 +1481,6 @@ using __ireturn_type = typename std::conditional<__unique_keys::value, std::pair, iterator>::type; - - using __iconv_type = typename std::conditional<__unique_keys::value, - _Select1st, _Identity - >::type; private: using _EqualEBO = _Hashtable_ebo_helper<0, _Equal>; using _EqualHelper = _Equal_helper<_Key, _Value, _ExtractKey, _Equal, Index: include/bits/hashtable.h =================================================================== --- include/bits/hashtable.h (revision 200491) +++ include/bits/hashtable.h (working copy) @@ -225,7 +225,6 @@ using __node_base = typename __hashtable_base::__node_base; using __bucket_type = typename __hashtable_base::__bucket_type; using __ireturn_type = typename __hashtable_base::__ireturn_type; - using __iconv_type = typename __hashtable_base::__iconv_type; using __map_base = __detail::_Map_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, @@ -680,7 +679,8 @@ // Insert node with hash code __code. Take ownership of the node, // deallocate it on exception. iterator - _M_insert_multi_node(__hash_code __code, __node_type* __n); + _M_insert_multi_node(__node_type* __hint, + __hash_code __code, __node_type* __n); template std::pair @@ -688,16 +688,39 @@ template iterator - _M_emplace(std::false_type, _Args&&... __args); + _M_emplace(std::false_type __uk, _Args&&... __args) + { return _M_emplace(cend(), __uk, std::forward<_Args>(__args)...); } + // Emplace with hint, useless when keys are unique. + template + iterator + _M_emplace(const_iterator, std::true_type __uk, _Args&&... __args) + { return _M_emplace(__uk, std::forward<_Args>(__args)...).first; } + + template + iterator + _M_emplace(const_iterator, std::false_type, _Args&&... __args); + template std::pair _M_insert(_Arg&&, std::true_type); template iterator - _M_insert(_Arg&&, std::false_type); + _M_insert(_Arg&& __arg, std::false_type __uk) + { return _M_insert(cend(), std::forward<_Arg>(__arg), __uk); } + // Insert with hint, not used when keys are unique. + template + iterator + _M_insert(const_iterator, _Arg&& __arg, std::true_type __uk) + { return _M_insert(std::forward<_Arg>(__arg), __uk).first; } + + // Insert with hint when keys are not unique. + template + iterator + _M_insert(const_iterator, _Arg&&, std::false_type); + size_type _M_erase(std::true_type, const key_type&); @@ -716,8 +739,11 @@ template iterator - emplace_hint(const_iterator, _Args&&... __args) - { return __iconv_type()(emplace(std::forward<_Args>(__args)...)); } + emplace_hint(const_iterator __hint, _Args&&... __args) + { + return _M_emplace(__hint, __unique_keys(), + std::forward<_Args>(__args)...); + } // Insert member functions via inheritance. @@ -1642,7 +1668,7 @@ _Traits>::iterator _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>:: - _M_emplace(std::false_type, _Args&&... __args) + _M_emplace(const_iterator __hint, std::false_type, _Args&&... __args) { // First build the node to get its hash code. __node_type* __node = _M_allocate_node(std::forward<_Args>(__args)...); @@ -1658,7 +1684,7 @@ __throw_exception_again; } - return _M_insert_multi_node(__code, __node); + return _M_insert_multi_node(__hint._M_cur, __code, __node); } template::iterator _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>:: - _M_insert_multi_node(__hash_code __code, __node_type* __node) + _M_insert_multi_node(__node_type* __hint, __hash_code __code, + __node_type* __node) { const __rehash_state& __saved_state = _M_rehash_policy._M_state(); std::pair __do_rehash @@ -1725,13 +1752,28 @@ const key_type& __k = this->_M_extract()(__node->_M_v()); size_type __bkt = _M_bucket_index(__k, __code); - // Find the node before an equivalent one. - __node_base* __prev = _M_find_before_node(__bkt, __k, __code); + // Find the node before an equivalent one or use hint if it exists and + // if it is equivalent. + __node_base* __prev + = __builtin_expect(__hint != nullptr, false) + && this->_M_equals(__k, __code, __hint) + ? __hint + : _M_find_before_node(__bkt, __k, __code); if (__prev) { // Insert after the node before the equivalent one. __node->_M_nxt = __prev->_M_nxt; __prev->_M_nxt = __node; + if (__builtin_expect(__prev == __hint, false)) + // hint might be the last bucket node, in this case we need to + // update next bucket. + if (__node->_M_nxt + && !this->_M_equals(__k, __code, __node->_M_next())) + { + size_type __next_bkt = _M_bucket_index(__node->_M_next()); + if (__next_bkt != __bkt) + _M_buckets[__next_bkt] = __node; + } } else // The inserted node has no equivalent in the @@ -1786,7 +1828,7 @@ _Traits>::iterator _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>:: - _M_insert(_Arg&& __v, std::false_type) + _M_insert(const_iterator __hint, _Arg&& __v, std::false_type) { // First compute the hash code so that we don't do anything if it // throws. @@ -1795,7 +1837,7 @@ // Second allocate new node so that we don't rehash if it throws. __node_type* __node = _M_allocate_node(std::forward<_Arg>(__v)); - return _M_insert_multi_node(__code, __node); + return _M_insert_multi_node(__hint._M_cur, __code, __node); } template. + +// { dg-options "-std=gnu++11" } + +#include + +#include +#include +#include +#include + +namespace +{ + const int sz = 2000000; + const std::string pattern = "test string #"; + const int nb_copies = 100; + + // Special std::string hasher based on std::hash but not tag as + // slow so that hash code is not cached. It is easier to show impact of + // hinting in this context. + struct hasher + { + std::size_t + operator()(const std::string& str) const noexcept + { + //std::istringstream istr(str.substr(pattern.size())); + //std::size_t str_index; + //istr >> str_index; + //return str_index; + std::hash std_hasher; + return std_hasher(str); + } + }; + + using ums_t = std::unordered_multiset; + + void + insert_with_perfect_hint1(const std::vector& strs, + ums_t& ms) + { + std::vector hints; + hints.reserve(strs.size()); + for (auto str : strs) + hints.push_back(ms.insert(str)); + + for (int j = 1; j != nb_copies; ++j) + for (std::size_t i = 0; i != strs.size(); ++i) + ms.insert(hints[i], strs[i]); + } + + void + insert_with_perfect_hint2(const std::vector& strs, + ums_t& ms) + { + std::vector hints; + hints.reserve(strs.size()); + for (auto str : strs) + hints.push_back(ms.insert(str)); + + for (std::size_t i = 0; i != strs.size(); ++i) + for (int j = 1; j != nb_copies; ++j) + ms.insert(hints[i], strs[i]); + } + + // Always insert with the result of the previous insertion. The result of + // the previous insertion will never be followed by an equivalent node + // resulting in a re-computation of its hash code which is expensive. + void + insert_with_good_hint(const std::vector& strs, + ums_t& ms) + { + std::vector hints; + hints.reserve(strs.size()); + for (auto str : strs) + hints.push_back(ms.insert(str)); + + for (int j = 1; j != nb_copies; ++j) + for (std::size_t i = 0; i != strs.size(); ++i) + hints[i] = ms.insert(hints[i], strs[i]); + } + + // Note that the following use case is particularly bad especially compared to + // the solution without hint because without hint the first insertion will put + // it first in the bucket and following insertions will detect it and insert + // just before. By giving a hint insertion will be done just after forcing to + // check if it has no impact on the following bucket. + void + insert_with_bad_hint(const std::vector& strs, + ums_t& ms) + { + std::vector hints; + hints.reserve(strs.size()); + for (auto str : strs) + hints.push_back(ms.insert(str)); + + for (std::size_t i = 0; i != strs.size(); ++i) + for (int j = 1; j != nb_copies; ++j) + hints[i] = ms.insert(hints[i], strs[i]); + } + + void + insert_without_hint1(const std::vector& strs, + ums_t& ms) + { + std::vector hints; + hints.reserve(strs.size()); + for (auto str : strs) + hints.push_back(ms.insert(str)); + + for (int j = 1; j != nb_copies; ++j) + for (std::size_t i = 0; i != strs.size(); ++i) + hints[i] = ms.insert(strs[i]); + } + + // This version is the best one if you insert all equivalent elements at the + // same time. It demonstrates that most of the time it is better not to give + // any hint unless you have written a benchmark for your application showing + // that it does have a positive effect. + void + insert_without_hint2(const std::vector& strs, + ums_t& ms) + { + std::vector hints; + hints.reserve(strs.size()); + for (auto str : strs) + hints.push_back(ms.insert(str)); + + for (std::size_t i = 0; i != strs.size(); ++i) + for (int j = 1; j != nb_copies; ++j) + hints[i] = ms.insert(strs[i]); + } + + void + insert_with_any_hint1(const std::vector& strs, + ums_t& ms) + { + std::vector hints; + hints.reserve(strs.size()); + for (auto str : strs) + hints.push_back(ms.insert(ms.begin(), str)); + + std::size_t offset = strs.size() / 2; + for (int j = 1; j != nb_copies; ++j) + for (std::size_t i = 0; i != strs.size(); ++i) + { + ms.insert(hints[(i + offset) % hints.size()], strs[i]); + ++offset; + } + } + + void + insert_with_any_hint2(const std::vector& strs, + ums_t& ms) + { + std::vector hints; + hints.reserve(strs.size()); + for (auto str : strs) + hints.push_back(ms.insert(ms.begin(), str)); + + std::size_t offset = strs.size() / 2; + for (std::size_t i = 0; i != strs.size(); ++i) + for (int j = 1; j != nb_copies; ++j) + { + ms.insert(hints[(i + offset) % hints.size()], strs[i]); + ++offset; + } + } +} + +int main() +{ + using namespace __gnu_test; + + const int nb_iter = 10; + + std::vector strs; + strs.reserve(sz / nb_copies); + + for (int i = 0; i != sz / nb_copies; ++i) + { + std::ostringstream osstr; + osstr << pattern << i; + strs.push_back(osstr.str()); + } + + ums_t ms; + // Use a large load factor to make the context ideal for using hint because we + // will have many elements per bucket. + ms.max_load_factor(10.0f); + ms.reserve(sz); + + // Warm up. + { + for (auto str : strs) + for (int j = 0; j != nb_copies; ++j) + ms.insert(str); + } + + time_counter time_no_hint1, time_any_hint1, time_bad_hint, time_perfect_hint1; + time_counter time_no_hint2, time_any_hint2, time_good_hint, time_perfect_hint2; + resource_counter resource_no_hint1, resource_any_hint1, resource_bad_hint, + resource_perfect_hint1; + resource_counter resource_no_hint2, resource_any_hint2, resource_good_hint, + resource_perfect_hint2; + + for (int i = 0; i != nb_iter; ++i) + { + // Bad hint + { + ms.clear(); + start_counters(time_bad_hint, resource_bad_hint); + insert_with_bad_hint(strs, ms); + stop_counters(time_bad_hint, resource_bad_hint); + } + + // No hint + { + ms.clear(); + start_counters(time_no_hint1, resource_no_hint1); + insert_without_hint1(strs, ms); + stop_counters(time_no_hint1, resource_no_hint1); + } + + // Any hint + { + ms.clear(); + start_counters(time_any_hint1, resource_any_hint1); + insert_with_any_hint1(strs, ms); + stop_counters(time_any_hint1, resource_any_hint1); + } + + // Good hint + { + ms.clear(); + start_counters(time_good_hint, resource_good_hint); + insert_with_good_hint(strs, ms); + stop_counters(time_good_hint, resource_good_hint); + } + + // No hint + { + ms.clear(); + start_counters(time_no_hint2, resource_no_hint2); + insert_without_hint2(strs, ms); + stop_counters(time_no_hint2, resource_no_hint2); + } + + // Perfect hint + { + ms.clear(); + start_counters(time_perfect_hint2, resource_perfect_hint2); + insert_with_perfect_hint2(strs, ms); + stop_counters(time_perfect_hint2, resource_perfect_hint2); + } + + // Any hint + { + ms.clear(); + start_counters(time_any_hint2, resource_any_hint2); + insert_with_any_hint2(strs, ms); + stop_counters(time_any_hint2, resource_any_hint2); + } + + // Perfect hint + { + ms.clear(); + start_counters(time_perfect_hint1, resource_perfect_hint1); + insert_with_perfect_hint1(strs, ms); + stop_counters(time_perfect_hint1, resource_perfect_hint1); + } + } + + std::ostringstream ostr; + ostr << "unordered_set " << nb_copies << " X " << sz / nb_copies + << " insertions w/o hint"; + report_performance(__FILE__, ostr.str().c_str(), + time_no_hint1, resource_no_hint1); + + ostr.str(""); + ostr << "unordered_set " << nb_copies << " X " << sz / nb_copies + << " insertions with any hint"; + report_performance(__FILE__, ostr.str().c_str(), + time_any_hint1, resource_any_hint1); + + ostr.str(""); + ostr << "unordered_set " << nb_copies << " X " << sz / nb_copies + << " insertions with good hint"; + report_performance(__FILE__, ostr.str().c_str(), + time_good_hint, resource_good_hint); + + ostr.str(""); + ostr << "unordered_set " << nb_copies << " X " << sz / nb_copies + << " insertions with perfect hint"; + report_performance(__FILE__, ostr.str().c_str(), + time_perfect_hint1, resource_perfect_hint1); + + ostr.str(""); + ostr << "unordered_set " << sz / nb_copies << " X " << nb_copies + << " insertions w/o hint"; + report_performance(__FILE__, ostr.str().c_str(), + time_no_hint2, resource_no_hint2); + + ostr.str(""); + ostr << "unordered_set " << sz / nb_copies << " X " << nb_copies + << " insertions with any hint"; + report_performance(__FILE__, ostr.str().c_str(), + time_any_hint2, resource_any_hint2); + + ostr.str(""); + ostr << "unordered_set " << sz / nb_copies << " X " << nb_copies + << " insertions with bad hint"; + report_performance(__FILE__, ostr.str().c_str(), + time_bad_hint, resource_bad_hint); + + ostr.str(""); + ostr << "unordered_set " << sz / nb_copies << " X " << nb_copies + << " insertions with perfect hint"; + report_performance(__FILE__, ostr.str().c_str(), + time_perfect_hint2, resource_perfect_hint2); + return 0; +} Index: testsuite/23_containers/unordered_multimap/insert/hint.cc =================================================================== --- testsuite/23_containers/unordered_multimap/insert/hint.cc (revision 0) +++ testsuite/23_containers/unordered_multimap/insert/hint.cc (revision 0) @@ -0,0 +1,123 @@ +// Copyright (C) 2013 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" } + +// Insert with hint, specific to this library implementation. + +#include +#include +#include + +void test01() +{ + bool test __attribute__((unused)) = true; + + typedef std::unordered_multimap Map; + typedef typename Map::value_type Pair; + + Map m; + + auto it1 = m.insert(Pair(0, 0)); + VERIFY( it1 != m.end() ); + VERIFY( it1->first == 0 ); + VERIFY( it1->second == 0 ); + + auto it2 = m.insert(it1, Pair(0, 2)); + VERIFY( it2 != m.end() ); + VERIFY( it2 != it1 ); + VERIFY( it2->second == 2 ); + VERIFY( it2 == std::next(it1) ); + + Pair p(0, 1); + it2 = m.insert(it1, p); + VERIFY( it2 == std::next(it1) ); +} + +struct hasher +{ + std::size_t operator()(int val) const + { return val / 2; } +}; + +void test02() +{ + bool test __attribute__((unused)) = true; + + typedef std::unordered_multimap Map; + typedef typename Map::value_type Pair; + + Map m; + + auto it1 = m.insert(Pair(0, 0)); + auto it2 = m.insert(it1, Pair(1, 0)); + VERIFY( m.bucket(it1->first) == m.bucket(it2->first) ); + VERIFY( m.bucket_size(m.bucket(it1->first)) == 2 ); + + auto it3 = m.insert(it2, Pair(2, 0)); + VERIFY( m.bucket(it3->first) != m.bucket(it2->first) ); + VERIFY( m.bucket_size(m.bucket(it3->first)) == 1 ); + + auto it4 = m.insert(it1, Pair(0, 1)); + VERIFY( it4 == std::next(it1) ); + VERIFY( m.bucket_size(m.bucket(it1->first)) == 3 ); + VERIFY( m.bucket_size(m.bucket(it3->first)) == 1 ); + + Pair p(1, 1); + it4 = m.insert(it2, p); + VERIFY( it4 == std::next(it2) ); + VERIFY( m.bucket_size(m.bucket(it1->first)) == 4 ); + auto range = m.equal_range(0); + VERIFY( std::distance(range.first, range.second) == 2 ); + range = m.equal_range(1); + VERIFY( std::distance(range.first, range.second) == 2 ); +} + +void test03() +{ + bool test __attribute__((unused)) = true; + + typedef std::unordered_multimap Map; + typedef typename Map::value_type Pair; + + Map m; + + auto it1 = m.insert(Pair(0, 0)); + VERIFY( it1 != m.end() ); + VERIFY( it1->first == 0 ); + VERIFY( it1->second == 0 ); + + auto it2 = m.emplace_hint(it1, std::piecewise_construct, + std::make_tuple(0), + std::make_tuple(2)); + VERIFY( it2 != m.end() ); + VERIFY( it2 != it1 ); + VERIFY( it2->second == 2 ); + VERIFY( it2 == std::next(it1) ); + + Pair p(0, 1); + it2 = m.emplace_hint(it1, p); + VERIFY( it2 == std::next(it1) ); +} + +int main() +{ + test01(); + test02(); + test03(); + return 0; +} Index: testsuite/23_containers/unordered_set/not_default_constructible_hash_neg.cc =================================================================== --- testsuite/23_containers/unordered_set/not_default_constructible_hash_neg.cc (revision 200491) +++ testsuite/23_containers/unordered_set/not_default_constructible_hash_neg.cc (working copy) @@ -19,7 +19,7 @@ // with this library; see the file COPYING3. If not see // . -// { dg-error "default constructible" "" { target *-*-* } 272 } +// { dg-error "default constructible" "" { target *-*-* } 271 } #include Index: testsuite/23_containers/unordered_set/instantiation_neg.cc =================================================================== --- testsuite/23_containers/unordered_set/instantiation_neg.cc (revision 200491) +++ testsuite/23_containers/unordered_set/instantiation_neg.cc (working copy) @@ -19,7 +19,7 @@ // with this library; see the file COPYING3. If not see // . -// { dg-error "with noexcept" "" { target *-*-* } 254 } +// { dg-error "with noexcept" "" { target *-*-* } 253 } #include Index: doc/xml/manual/containers.xml =================================================================== --- doc/xml/manual/containers.xml (revision 200491) +++ doc/xml/manual/containers.xml (working copy) @@ -354,6 +354,60 @@ Unordered Associative +
+ Insertion Hints + + + Here is how the hinting works in the libstdc++ implementation of unordered + containers, and the rationale behind this behavior. + + + In the following text, the phrase equivalent to refer + to the result of the invocation of the equal predicate imposed on the + container by its key_equal object, which defaults to (basically) + ==. + + + Unordered containers can be seen as a std::vector of + std::forward_list. The std::vector represents + the buckets and each std::forward_list is the list of nodes + belonging to the same bucket. When inserting an element in such a data + structure we first need to compute the element hash code to find the + bucket to insert the element to, the second step depends on the uniqueness + of elements in the container. + + + In the case of std::unordered_set and + std::unordered_map you need to look through all bucket's + elements for an equivalent one. If there is none the insertion can be + achieved, otherwise the insertion fails. As we always need to loop though + all bucket's elements, the hint doesn't tell us if the element is already + present, and we don't have any constraint on where the new element is to + be inserted, the hint won't be of any help and will then be ignored. + + + In the case of std::unordered_multiset + and std::unordered_multimap equivalent elements must be + linked together so that the equal_range(const key_type&) + can return the range of iterators pointing to all equivalent elements. + This is where hinting can be used to point to another equivalent element + already part of the container and so skip all non equivalent elements of + the bucket. So to be useful the hint shall point to an element equivalent + to the one being inserted. The new element will be then inserted right + after the hint. Note that because of an implementation detail inserting + after a node can require updating the bucket of the following node. To + check if the next bucket is to be modified we need to compute the + following node's hash code. So if you want your hint to be really efficient + it should be followed by another equivalent element, the implementation + will detect this equivalence and won't compute next element hash code. + + + It is highly advised to start using unordered containers hints only if you + have a benchmark that will demonstrate the benefit of it. If you don't then do + not use hints, it might do more harm than good. + +
+
Hash Code