From patchwork Wed Jul 25 14:55:08 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Jonathan Wakely X-Patchwork-Id: 173185 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 AD61D2C00A7 for ; Thu, 26 Jul 2012 00:55:34 +1000 (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=1343832934; h=Comment: DomainKey-Signature:Received:Received:Received:Received: MIME-Version:Received:Received:In-Reply-To:References:Date: Message-ID:Subject:From:To:Cc:Content-Type:Mailing-List: Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:Sender:Delivered-To; bh=ID+RY40o3DgsIMRqZO/VNMVzMOo=; b=Kl8Lr7c7Q8P6dkxu82XQz0tway1wzYgnR1C85qA7E8g2kHEsE74YB8qn+Yxy0C jnbQzOmJNSawjuTkSm31sFpdBK649UWxi8c5DXiF+pQiq/fK7mN4C9uHab1OJuXo MhhZ0z+T9Y3IAeDgVWrywFFPtNDfwbCqLKWy/j1ZvyMSk= 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:MIME-Version:Received:Received:In-Reply-To:References:Date:Message-ID:Subject:From:To:Cc:Content-Type:Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help:Sender:Delivered-To; b=iCVmrAy2bz6UcbSWfUf1gpigkcBnU9ldy9VnuLN3vnpnEvxOLQwcrxJ0VD5Fzq zG2HzVvI0XQ+p44EJEhFXTp6XxLTkX44OgO7m77UiSmfELdMGCtCkMzKQDeJ3lUz FwYMp+MR+RHWHkcTnLECJKc7/8+g5Mzj4YUoxcoZauVHw=; Received: (qmail 22329 invoked by alias); 25 Jul 2012 14:55:28 -0000 Received: (qmail 22308 invoked by uid 22791); 25 Jul 2012 14:55:26 -0000 X-SWARE-Spam-Status: No, hits=-5.1 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-lpp01m010-f47.google.com (HELO mail-lpp01m010-f47.google.com) (209.85.215.47) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Wed, 25 Jul 2012 14:55:10 +0000 Received: by lags15 with SMTP id s15so647257lag.20 for ; Wed, 25 Jul 2012 07:55:08 -0700 (PDT) MIME-Version: 1.0 Received: by 10.112.88.34 with SMTP id bd2mr11382140lbb.33.1343228108241; Wed, 25 Jul 2012 07:55:08 -0700 (PDT) Received: by 10.112.27.228 with HTTP; Wed, 25 Jul 2012 07:55:08 -0700 (PDT) In-Reply-To: <500FBBCD.4010402@gmail.com> References: <500FBBCD.4010402@gmail.com> Date: Wed, 25 Jul 2012 15:55:08 +0100 Message-ID: Subject: Re: PR 54075 Fix hashtable::reserve From: Jonathan Wakely To: =?ISO-8859-1?Q?Fran=E7ois_Dumont?= Cc: "libstdc++@gcc.gnu.org" , gcc-patches 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 (CC gcc-patches) On 25 July 2012 10:26, François Dumont wrote: > Hi > > Here is a patch proposal for PR 54075. I also took the occasion to fix > something that has been delay so far which is usage of std::max to get the > number of buckets to use. The problem of using std::max when using the hash > policy is that the hashtable might be using a number of buckets inconsistent > with the hash policy. > > 2012-07-25 François Dumont > > PR libstdc++/54075 > * include/bits/hashtable.h > (_Hashtable<>::_Hashtable(_InputIterator, _InputIterator, > size_type, ...): Remove std::max usage to guaranty that hashtable > state is consistent with hash policy state. s/guaranty/guarantee/ > (_Hashtable<>::rehash): Likewise. Set _M_prev_resize to 0 to avoid > the hashtable to be shrink on next insertion. s/to be shrink/shrinking/ > * testsuite/23_containers/unordered_set/modifiers/reserve.cc: New. > * testsuite/23_containers/unordered_multiset/modifiers/reserve.cc: New. > * testsuite/23_containers/unordered_map/modifiers/reserve.cc: New. > * testsuite/23_containers/unordered_multimap/modifiers/reserve.cc: New. > > Tested under Linux x86_64. OK with the changelog edits above. > I guess it will have to be apply to the 4.7 branch too, confirm please. Yes, I think so, it's a regression from 4.6. Thanks for dealing with it so quickly. Index: include/bits/hashtable.h =================================================================== --- include/bits/hashtable.h (revision 189626) +++ include/bits/hashtable.h (working copy) @@ -803,11 +803,11 @@ _M_element_count(0), _M_rehash_policy() { - _M_bucket_count = std::max(_M_rehash_policy._M_next_bkt(__bucket_hint), - _M_rehash_policy. - _M_bkt_for_elements(__detail:: - __distance_fw(__f, - __l))); + _M_bucket_count = + _M_rehash_policy._M_bkt_for_elements(__detail::__distance_fw(__f, + __l)); + if (_M_bucket_count <= __bucket_hint) + _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint); // We don't want the rehash policy to ask for the hashtable to // shrink on the first insertion so we need to reset its @@ -1609,10 +1609,20 @@ rehash(size_type __n) { const __rehash_state& __saved_state = _M_rehash_policy._M_state(); - _M_rehash(std::max(_M_rehash_policy._M_next_bkt(__n), - _M_rehash_policy._M_bkt_for_elements(_M_element_count - + 1)), - __saved_state); + std::size_t __buckets + = _M_rehash_policy._M_bkt_for_elements(_M_element_count + 1); + if (__buckets <= __n) + __buckets = _M_rehash_policy._M_next_bkt(__n); + + if (__buckets != _M_bucket_count) + { + _M_rehash(__buckets, __saved_state); + + // We don't want the rehash policy to ask for the hashtable to shrink + // on the next insertion so we need to reset its previous resize + // level. + _M_rehash_policy._M_prev_resize = 0; + } } template. + +#include +#include + +bool test __attribute__((unused)) = true; + +void test01() +{ + const int N = 1000; + + typedef std::unordered_multiset MSet; + MSet s; + s.reserve(N * 2); + + std::size_t bkts = s.bucket_count(); + for (int i = 0; i != N; ++i) + { + s.insert(i); + s.insert(i); + // As long as we insert less than the reserved number of elements we + // shouldn't experiment any rehash. + VERIFY( s.bucket_count() == bkts ); + } +} + +int main() +{ + test01(); + return 0; +} Index: testsuite/23_containers/unordered_map/modifiers/reserve.cc =================================================================== --- testsuite/23_containers/unordered_map/modifiers/reserve.cc (revision 0) +++ testsuite/23_containers/unordered_map/modifiers/reserve.cc (revision 0) @@ -0,0 +1,47 @@ +// { dg-options "-std=gnu++0x" } + +// Copyright (C) 2012 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 +// . + +#include +#include + +bool test __attribute__((unused)) = true; + +void test01() +{ + const int N = 1000; + + typedef std::unordered_map Map; + Map m; + m.reserve(N); + + std::size_t bkts = m.bucket_count(); + for (int i = 0; i != N; ++i) + { + m.insert(std::make_pair(i, i)); + // As long as we insert less than the reserved number of elements we + // shouldn't experiment any rehash. + VERIFY( m.bucket_count() == bkts ); + } +} + +int main() +{ + test01(); + return 0; +} Index: testsuite/23_containers/unordered_multimap/modifiers/reserve.cc =================================================================== --- testsuite/23_containers/unordered_multimap/modifiers/reserve.cc (revision 0) +++ testsuite/23_containers/unordered_multimap/modifiers/reserve.cc (revision 0) @@ -0,0 +1,48 @@ +// { dg-options "-std=gnu++0x" } + +// Copyright (C) 2012 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 +// . + +#include +#include + +bool test __attribute__((unused)) = true; + +void test01() +{ + const int N = 1000; + + typedef std::unordered_multimap MMap; + MMap m; + m.reserve(N * 2); + + std::size_t bkts = m.bucket_count(); + for (int i = 0; i != N; ++i) + { + m.insert(std::make_pair(i, i)); + m.insert(std::make_pair(i, i)); + // As long as we insert less than the reserved number of elements we + // shouldn't experiment any rehash. + VERIFY( m.bucket_count() == bkts ); + } +} + +int main() +{ + test01(); + return 0; +} Index: testsuite/23_containers/unordered_set/modifiers/reserve.cc =================================================================== --- testsuite/23_containers/unordered_set/modifiers/reserve.cc (revision 0) +++ testsuite/23_containers/unordered_set/modifiers/reserve.cc (revision 0) @@ -0,0 +1,47 @@ +// { dg-options "-std=gnu++0x" } + +// Copyright (C) 2012 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 +// . + +#include +#include + +bool test __attribute__((unused)) = true; + +void test01() +{ + const int N = 1000; + + typedef std::unordered_set Set; + Set s; + s.reserve(N); + + std::size_t bkts = s.bucket_count(); + for (int i = 0; i != N; ++i) + { + s.insert(i); + // As long as we insert less than the reserved number of elements we + // shouldn't experiment any rehash. + VERIFY( s.bucket_count() == bkts ); + } +} + +int main() +{ + test01(); + return 0; +}