From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 58412 invoked by alias); 21 Sep 2018 16:10:55 -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 58390 invoked by uid 89); 21 Sep 2018 16:10:54 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-26.9 required=5.0 tests=BAYES_00,FREEMAIL_FROM,GIT_PATCH_0,GIT_PATCH_1,GIT_PATCH_2,GIT_PATCH_3,RCVD_IN_DNSWL_NONE,SPF_PASS autolearn=ham version=3.3.2 spammy=HX-Received:sk:g4-v6mr X-HELO: mail-wr1-f68.google.com Received: from mail-wr1-f68.google.com (HELO mail-wr1-f68.google.com) (209.85.221.68) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Fri, 21 Sep 2018 16:10:52 +0000 Received: by mail-wr1-f68.google.com with SMTP id u12-v6so13389074wrr.4; Fri, 21 Sep 2018 09:10:51 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=subject:to:cc:references:from:message-id:date:user-agent :mime-version:in-reply-to:content-language; bh=PlIIivIAlWqzCLq60uAPBofbqecmSs/725p5N4JH/MA=; b=BkWrFwmDuK3EotAfqNy1Un/YkjhBmk9uV7g25b0M1oZ4Cu/+xL2Nb+SKpeUFK1E7eH IIbWFdAQE38bf2ytnrEvQV0LJjXs/Q5jxms4hojn5lBsK8RSRhoyddzmtwOWYN3F+cUZ Jj3W3TPPJNnvZnnnOTq16JthBs++8AO7NWUXlknowJVBC3MeYI+sZG69aVU/2+N4KORX pczfg/64QlV0M4mBebz7zRvhSoPLmxg4s0tu2dAjMmEMWs+tf5Ck4dmz+YCDL0KL3c68 HvINqOLQOVF+c4PUmEqXIg6jI5BWUMn8OfFTHIbCT/Xq82BHoUEORcLlhorHaq/32GEQ noEg== Return-Path: Received: from [10.16.8.93] ([109.190.253.11]) by smtp.googlemail.com with ESMTPSA id 127-v6sm7181581wmb.30.2018.09.21.09.10.47 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 21 Sep 2018 09:10:48 -0700 (PDT) Subject: Re: [PATCH] PR libstdc++/87135 Rehash only when necessary (LWG2156) To: Jonathan Wakely Cc: "libstdc++@gcc.gnu.org" , gcc-patches References: <1ad7ad86-0f0c-e8b0-8f29-2b5303718988@gmail.com> <20180918084159.GV23172@redhat.com> <712c7e85-fd7b-5849-85b6-14784266d567@gmail.com> <20180919110724.GC23172@redhat.com> From: =?UTF-8?Q?Fran=c3=a7ois_Dumont?= Message-ID: Date: Fri, 21 Sep 2018 16:17:00 -0000 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.9.1 MIME-Version: 1.0 In-Reply-To: <20180919110724.GC23172@redhat.com> Content-Type: multipart/mixed; boundary="------------4EB16991B5957CB08DE7E901" X-SW-Source: 2018-09/txt/msg01243.txt.bz2 This is a multi-part message in MIME format. --------------4EB16991B5957CB08DE7E901 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Content-length: 4034 Here is the patch complement. load_factor.cc failure revealed a bug in load factor management. Now computation of _M_next_resize is consistent throughout the different places where it is set. The 2 other tests only have to be adapted.     PR libstdc++/87135     * src/c++11/hashtable_c++0x.cc (_Prime_rehash_policy::_M_next_bkt):     Use __builtin_floor to compute _M_next_resize.     * testsuite/23_containers/unordered_set/hash_policy/71181.cc: Adapt.     * testsuite/23_containers/unordered_set/hash_policy/prime_rehash.cc:     Adapt. Now fully tested under x86_64. Ok to commit ? François On 09/19/2018 01:07 PM, Jonathan Wakely wrote: > On 18/09/18 22:39 +0200, François Dumont wrote: >> On 09/18/2018 10:41 AM, Jonathan Wakely wrote: >>> On 13/09/18 07:49 +0200, François Dumont wrote: >>>> All changes limited to hashtable_c++0x.cc file. >>>> >>>> _Prime_rehash_policy::_M_next_bkt now really does what its comment >>>> was declaring that is to say: >>>>   // Return a prime no smaller than n. >>>> >>>> _Prime_rehash_policy::_M_need_rehash rehash only when _M_next_size >>>> is exceeded, not only when it is reach. >>>> >>>>     PR libstdc++/87135 >>>>     * src/c++11/hashtable_c++0x.cc: >>>>     (_Prime_rehash_policy::_M_next_bkt): Return a prime no smaller >>>> than >>>>     requested size, but not necessarily greater. >>>>     (_Prime_rehash_policy::_M_need_rehash): Rehash only if target >>>> size is >>>>     strictly greater than next resize threshold. >>>>     * testsuite/23_containers/unordered_map/modifiers/reserve.cc: >>>> Adapt test >>>>     to validate that there is no rehash as long as number of >>>> insertion is >>>>     lower or equal to the reserved number of elements. >>>> >>>> unordered_map tests successful, ok to commit once all other tests >>>> completed ? >>>> >>>> François >>> >>>> diff --git a/libstdc++-v3/src/c++11/hashtable_c++0x.cc >>>> b/libstdc++-v3/src/c++11/hashtable_c++0x.cc >>>> index a776a8506fe..ec6031b3f5b 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[13] >>>> -      = { 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11, 13, 13 }; >>>> +    static const unsigned char __fast_bkt[] >>>> +      = { 2, 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11, 13, 13 }; >>>> >>>> -    if (__n <= 12) >>>> +    if (__n < sizeof(__fast_bkt) / sizeof(unsigned char)) >>> >>> sizeof(unsigned char) is defined to be 1, always. >> >> I also though it was overkill but there are so many platforms that I >> prefer to be caution. Good to know that it can't be otherwise. >> >>> >>> I think this should be just sizeof(__fast_bkt), or if you're trying to >>> guard against the type of __fast_bkt changing, then use >>> sizeof(__fast_bkt) / sizeof(__fast_bkt[0])) >> >> I committed with simply sizeof(__fast_bkt) > > > This caused some testsuite regressions: > > FAIL: 23_containers/unordered_set/hash_policy/71181.cc execution test > /home/jwakely/src/gcc/gcc/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/71181.cc:42: > void test(int) [with _USet = std::unordered_set]: Assertion > 'us.bucket_count() == bkts' failed. > > FAIL: 23_containers/unordered_set/hash_policy/load_factor.cc execution > test > /home/jwakely/src/gcc/gcc/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/load_factor.cc:50: > void test() [with _USet = std::unordered_set]: Assertion > 'us.load_factor() <= us.max_load_factor()' failed. > > FAIL: 23_containers/unordered_set/hash_policy/prime_rehash.cc > execution test > /home/jwakely/src/gcc/gcc/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/prime_rehash.cc:37: > void test01(): Assertion 'nxt == policy._M_next_bkt(mx)' failed. > > > --------------4EB16991B5957CB08DE7E901 Content-Type: text/x-patch; name="87135.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="87135.patch" Content-length: 2456 diff --git a/libstdc++-v3/src/c++11/hashtable_c++0x.cc b/libstdc++-v3/src/c++11/hashtable_c++0x.cc index 462767612f0..b9b11ff4385 100644 --- a/libstdc++-v3/src/c++11/hashtable_c++0x.cc +++ b/libstdc++-v3/src/c++11/hashtable_c++0x.cc @@ -52,7 +52,7 @@ namespace __detail if (__n < sizeof(__fast_bkt)) { _M_next_resize = - __builtin_ceil(__fast_bkt[__n] * (long double)_M_max_load_factor); + __builtin_floor(__fast_bkt[__n] * (long double)_M_max_load_factor); return __fast_bkt[__n]; } @@ -75,7 +75,7 @@ namespace __detail _M_next_resize = std::size_t(-1); else _M_next_resize = - __builtin_ceil(*__next_bkt * (long double)_M_max_load_factor); + __builtin_floor(*__next_bkt * (long double)_M_max_load_factor); return *__next_bkt; } 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 index 0270ea52b9c..ba783d26847 100644 --- a/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/71181.cc +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/71181.cc @@ -30,7 +30,7 @@ template auto bkts = us.bucket_count(); for (int i = 0; i != threshold; ++i) { - if (i == nb_reserved) + if (i >= nb_reserved) { nb_reserved = bkts; us.reserve(nb_reserved); diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/prime_rehash.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/prime_rehash.cc index 7110a3afb39..916c5ad702c 100644 --- a/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/prime_rehash.cc +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/prime_rehash.cc @@ -26,20 +26,22 @@ void test01() { std::__detail::_Prime_rehash_policy policy; - for (std::size_t i = 1;;) + // Starts at 4 because 2 & 3 are two consecutives primes that make this test + // fail. + for (std::size_t i = 4;;) { auto nxt = policy._M_next_bkt(i); - if (nxt == i) + if (nxt <= i) { - // Equals only when reaching max. - constexpr auto mx = std::numeric_limits::max() - 1; + // Lower or equals only when reaching max prime. + constexpr auto mx = std::numeric_limits::max(); VERIFY( nxt == policy._M_next_bkt(mx) ); break; } VERIFY( nxt > i ); - i = nxt; + i = nxt + 1; } } --------------4EB16991B5957CB08DE7E901--