From patchwork Sun May 22 15:16:30 2016 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: 624955 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 3rCQJ85Y0sz9t3k for ; Mon, 23 May 2016 01:16:54 +1000 (AEST) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b=vvA9kfjM; 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:from :subject:to:message-id:date:mime-version:content-type; q=dns; s= default; b=DlfJgKyexJgjFc4GarO98Uhwh3NnUGjkbeBuNMW+XlIehq+e9mSJR YVNGEwXNDD1Ln5mIuVqK3KJlLBjDAVN3At02VxRAEdZ2NdnA3rznUajjLBlSRPbZ 5XSbmzZ5+gusgtpTA5X9mDw3GGoVhyws0wRqg9UIdcWVIBGH6NqusQ= 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:from :subject:to:message-id:date:mime-version:content-type; s= default; bh=aCWSkTd18KxucMxuTPLHdAwygB4=; b=vvA9kfjMZZb50aJN2RwO 8Cz9Q+Lg6hrO8eEXSLv6Lx5s4q/INOdU2RI2t/hQzSgUl5KHtSIMeOHI99827CKX mQvAInfMxym4EgY6GGNpKJCXtXhjfw+I2gdK3/VD9kZeSopW06GuA3jHLj6RIbXn GyucfBxaPpPo0AqUGIESS0E= Received: (qmail 129328 invoked by alias); 22 May 2016 15:16:46 -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 129307 invoked by uid 89); 22 May 2016 15:16:45 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.1 required=5.0 tests=AWL, BAYES_00, FREEMAIL_FROM, RCVD_IN_DNSWL_LOW, SPF_PASS autolearn=ham version=3.3.2 spammy=respected, integrated, adapt, long* X-Spam-User: qpsmtpd, 2 recipients X-HELO: mail-wm0-f45.google.com Received: from mail-wm0-f45.google.com (HELO mail-wm0-f45.google.com) (74.125.82.45) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-GCM-SHA256 encrypted) ESMTPS; Sun, 22 May 2016 15:16:35 +0000 Received: by mail-wm0-f45.google.com with SMTP id i142so43459558wmf.0; Sun, 22 May 2016 08:16:34 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:from:subject:to:message-id:date:user-agent :mime-version; bh=SAqeh7e+nXE+/Jlbb+Y2ZtWo8dm8NwWzHFl660dVZzk=; b=mgEhjWRyAz9jxl1SAgIGInTXvjdGC1a+dBJ5Ukq+QPjkBfarPUtqELNdpYFdfqOjL2 E352QZSgnS4lKKkWrO3HOtL/K8a3BrgH4xUkes+k5h/mJdYbQ+7O1Y8Fhkj42VwMNSF+ bePtYEcoZ9eyJg0yU8P8qePjvVWhykD7bG4pc4ykaCU59GWddGqWaXNsh0lSsbJDx1X3 5jJTMh4x9AOf1+0iNv0GXyfKpQEm4PmeYEQwBVGHVv5iOLr4ZU9Oj3IxwazLTfOMqCEy MZ70Q74bpgFXFqlozBFpRa8hTxKR79NHmfPjhgBWQquGWD8iAvOS2Yg4UWtiTrKvaOi9 6B0g== X-Gm-Message-State: AOPr4FW6n33tCWzvYPht1hHU8buiUUUqK+3zaDDlohXOK02PGBDg/Hiyw72e0WvumFo2Lw== X-Received: by 10.28.210.72 with SMTP id j69mr13295958wmg.12.1463930192309; Sun, 22 May 2016 08:16:32 -0700 (PDT) Received: from [192.168.0.22] (arf62-1-82-237-250-248.fbx.proxad.net. [82.237.250.248]) by smtp.googlemail.com with ESMTPSA id jq1sm30301834wjc.28.2016.05.22.08.16.30 (version=TLSv1/SSLv3 cipher=OTHER); Sun, 22 May 2016 08:16:31 -0700 (PDT) From: =?UTF-8?Q?Fran=c3=a7ois_Dumont?= Subject: PR 71181 Avoid rehash after reserve To: "libstdc++@gcc.gnu.org" , gcc-patches Message-ID: <5741CD4E.4050104@gmail.com> Date: Sun, 22 May 2016 17:16:30 +0200 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Thunderbird/38.7.2 MIME-Version: 1.0 Hi To fix 71181 problem I propose to change how we deal with reserve called with pivot values that is to say prime numbers. Now _M_next_bkt always return a value higher than the input value. This way when reverse(97) is called we end up with 199 buckets and so enough space to store 97 values without rehashing. I have integrated in this patch several other enhancements on the same subject. Improvement of _M_next_resize management when reaching highest bucket number. Remove sentinel value in __prime_list, just need to limit range when calling lower_bound. PR libstdc++/71181 * include/tr1/hashtable_policy.h (_S_n_primes): Minus 1 to avoid check on lower_bound call. * src/c++11/hashtable_c++0x.cc (_Prime_rehash_policy::_M_next_bkt): Always return a value greater than input value. Set _M_next_resize to value when reaching highest prime number. * src/shared/hashtable-aux.cc (__prime_list): Remove sentinel value. * testsuite/23_containers/unordered_set/hash_policy/71181.cc: New. * testsuite/23_containers/unordered_set/max_load_factor/robustness.cc: Adapt. Tested under Linux x86_64, ok to commit ? François diff --git a/libstdc++-v3/include/tr1/hashtable_policy.h b/libstdc++-v3/include/tr1/hashtable_policy.h index 4ee6d45..67a1339 100644 --- a/libstdc++-v3/include/tr1/hashtable_policy.h +++ b/libstdc++-v3/include/tr1/hashtable_policy.h @@ -403,7 +403,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt, std::size_t __n_ins) const; - enum { _S_n_primes = sizeof(unsigned long) != 8 ? 256 : 256 + 48 }; + enum { _S_n_primes = (sizeof(unsigned long) != 8 ? 256 : 256 + 48) - 1 }; float _M_max_load_factor; float _M_growth_factor; diff --git a/libstdc++-v3/src/c++11/hashtable_c++0x.cc b/libstdc++-v3/src/c++11/hashtable_c++0x.cc index a5e6520..dc0dab5 100644 --- a/libstdc++-v3/src/c++11/hashtable_c++0x.cc +++ b/libstdc++-v3/src/c++11/hashtable_c++0x.cc @@ -46,10 +46,10 @@ namespace __detail { // Optimize lookups involving the first elements of __prime_list. // (useful to speed-up, eg, constructors) - static const unsigned char __fast_bkt[12] - = { 2, 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11 }; + static const unsigned char __fast_bkt[13] + = { 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11, 13, 13 }; - if (__n <= 11) + if (__n <= 12) { _M_next_resize = __builtin_ceil(__fast_bkt[__n] * (long double)_M_max_load_factor); @@ -58,10 +58,22 @@ namespace __detail constexpr auto __n_primes = sizeof(__prime_list) / sizeof(unsigned long) - 1; + constexpr auto __prime_list_end = __prime_list + __n_primes; const unsigned long* __next_bkt = - std::lower_bound(__prime_list + 5, __prime_list + __n_primes, __n); - _M_next_resize = - __builtin_ceil(*__next_bkt * (long double)_M_max_load_factor); + std::lower_bound(__prime_list + 6, __prime_list_end, __n); + + if (*__next_bkt == __n && __next_bkt != __prime_list_end) + ++__next_bkt; + + if (__next_bkt == __prime_list_end) + // Set next resize to the max value so that we never try to rehash again + // as we already reach the biggest possible bucket number. + // Note that it might result in max_load_factor not being respected. + _M_next_resize = std::size_t(-1); + else + _M_next_resize = + __builtin_ceil(*__next_bkt * (long double)_M_max_load_factor); + return *__next_bkt; } diff --git a/libstdc++-v3/src/shared/hashtable-aux.cc b/libstdc++-v3/src/shared/hashtable-aux.cc index 081bb12..7623b46 100644 --- a/libstdc++-v3/src/shared/hashtable-aux.cc +++ b/libstdc++-v3/src/shared/hashtable-aux.cc @@ -25,7 +25,7 @@ namespace __detail { _GLIBCXX_BEGIN_NAMESPACE_VERSION - extern const unsigned long __prime_list[] = // 256 + 1 or 256 + 48 + 1 + extern const unsigned long __prime_list[] = // 256 or 256 + 48 { 2ul, 3ul, 5ul, 7ul, 11ul, 13ul, 17ul, 19ul, 23ul, 29ul, 31ul, 37ul, 41ul, 43ul, 47ul, 53ul, 59ul, 61ul, 67ul, 71ul, 73ul, 79ul, @@ -66,13 +66,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION 1259520799ul, 1362662261ul, 1474249943ul, 1594975441ul, 1725587117ul, 1866894511ul, 2019773507ul, 2185171673ul, 2364114217ul, 2557710269ul, 2767159799ul, 2993761039ul, 3238918481ul, 3504151727ul, 3791104843ul, - 4101556399ul, 4294967291ul, - // Sentinel, so we don't have to test the result of lower_bound, - // or, on 64-bit machines, rest of the table. -#if __SIZEOF_LONG__ != 8 - 4294967291ul -#else - 6442450933ul, 8589934583ul, 12884901857ul, 17179869143ul, + 4101556399ul, 4294967291ul +#if __SIZEOF_LONG__ >= 8 + ,6442450933ul, 8589934583ul, 12884901857ul, 17179869143ul, 25769803693ul, 34359738337ul, 51539607367ul, 68719476731ul, 103079215087ul, 137438953447ul, 206158430123ul, 274877906899ul, 412316860387ul, 549755813881ul, 824633720731ul, 1099511627689ul, @@ -86,7 +82,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION 288230376151711717ul, 576460752303423433ul, 1152921504606846883ul, 2305843009213693951ul, 4611686018427387847ul, 9223372036854775783ul, - 18446744073709551557ul, 18446744073709551557ul + 18446744073709551557ul #endif }; _GLIBCXX_END_NAMESPACE_VERSION diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/71181.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/71181.cc new file mode 100644 index 0000000..6bd88fa --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/71181.cc @@ -0,0 +1,51 @@ +// Copyright (C) 2016 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 + +template + void test(std::size_t max) + { + bool test __attribute__((unused)) = true; + _USet us; + auto nb_reserved = us.bucket_count(); + us.reserve(nb_reserved); + auto bkts = us.bucket_count(); + for (int i = 0; i != max; ++i) + { + if (i == nb_reserved) + { + nb_reserved = bkts; + us.reserve(nb_reserved); + bkts = us.bucket_count(); + } + + us.insert(i); + + VERIFY( us.bucket_count() == bkts ); + } + } + +int main() +{ + test>(150); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/max_load_factor/robustness.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/max_load_factor/robustness.cc index 95cc1cd..eb1ad5d 100644 --- a/libstdc++-v3/testsuite/23_containers/unordered_set/max_load_factor/robustness.cc +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/max_load_factor/robustness.cc @@ -41,7 +41,7 @@ void test01() std::size_t thrown_exceptions = 0; // Reduce max load factor. - us.max_load_factor(us.max_load_factor() / 2); + us.max_load_factor(us.max_load_factor() / 4); // At this point load factor is higher than max_load_factor because we can't // rehash in max_load_factor call. @@ -65,7 +65,7 @@ void test01() catch (const __gnu_cxx::forced_error&) { // max load factor doesn't change. - VERIFY( us.max_load_factor() == .5f ); + VERIFY( us.max_load_factor() == .25f ); ++thrown_exceptions; }