From patchwork Wed May 25 20:48:01 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: 626457 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 3rFPWM0Q2Kz9sds for ; Thu, 26 May 2016 06:48:30 +1000 (AEST) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b=bT2hinjx; 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 :subject:to:references:cc:from:message-id:date:mime-version :in-reply-to:content-type; q=dns; s=default; b=WOMeEmbMy1bJLaedY xWdeDl3OdaOBqSQj0RpxHQ5PIRcumQwU/YwRe/I+swr6kBPYylQEefc1+jkJ0jgY kSd6NNRrDFigboYvwMMvVID6dRcJdMP3dOUNbwut2r9aNqZyzF1d3wtj339U0+LR 95UqfPhqPypa15PrtynYRDp2fk= 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 :subject:to:references:cc:from:message-id:date:mime-version :in-reply-to:content-type; s=default; bh=hS62gLUs2coo9sFe3D3VlyW rFDY=; b=bT2hinjxi+s09ww12hDRTIBGEVBDrJ15C9I7+TrzJ4oX8vweH1PPQHJ 3n8AX/T1bBxeFsRBz3+btcTGY4M7LsdTUc6nlTkd84ULEbvOnBLpBupI7RacI8vv 4l0OIe7gnVKhKnZ2hotcRaFiJo6VXYzv55U287IDN/H6a0WjYVvQ= Received: (qmail 47482 invoked by alias); 25 May 2016 20:48:20 -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 47458 invoked by uid 89); 25 May 2016 20:48:19 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.3 required=5.0 tests=AWL, BAYES_00, FREEMAIL_FROM, RCVD_IN_DNSWL_LOW, SPF_PASS autolearn=ham version=3.3.2 spammy=resize, max_load_factor, __builtin_ceil, respected X-Spam-User: qpsmtpd, 2 recipients X-HELO: mail-ig0-f174.google.com Received: from mail-ig0-f174.google.com (HELO mail-ig0-f174.google.com) (209.85.213.174) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-GCM-SHA256 encrypted) ESMTPS; Wed, 25 May 2016 20:48:06 +0000 Received: by mail-ig0-f174.google.com with SMTP id l10so35594792igk.0; Wed, 25 May 2016 13:48:06 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:subject:to:references:cc:from:message-id:date :user-agent:mime-version:in-reply-to; bh=LkNCNHYnXXVIox3xVHWf8YNERLDDWwVLjFXeLcRcrXc=; b=DJkLOsxqlbOZRDXsSuBScojldOKeY3/3O9nAJ1IjTCiMtpXAD11rFqh5+9awdtMIOU YCR/qP52uPKbkkbxGPSr0EOUBnN6Xt6mnk/h1wvV02rafOwuFZiINMlQRrQF7BIMVm7V 7IsFzl8KunWLgB6LLuSHnvqSGK2HS5F/62ThlqST5qllqarRWv8NxbnT5IxaY8sMPsv5 bNu6SJlqBRrCZqQdCITkmfwv0UA3cuL9XzFU6h2SGaNtTVjRP0MVSzZRl1WiA3cZO2xa gA0rwr5WlC6tdEwfFuHBA0kJ8rggbVurkyZUBh6LCy0bI8idyRmz33ZLEMOZPppnoonb bm3A== X-Gm-Message-State: ALyK8tICRgbUHucULLfKfcmxia9+0g2pBOnzUh6WGohxzkN5V309JCZpoWz9+4TyjTbKzQ== X-Received: by 10.194.173.42 with SMTP id bh10mr6499103wjc.150.1464209283847; Wed, 25 May 2016 13:48:03 -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 gk4sm10694773wjd.7.2016.05.25.13.48.02 (version=TLSv1/SSLv3 cipher=OTHER); Wed, 25 May 2016 13:48:02 -0700 (PDT) Subject: Re: PR 71181 Avoid rehash after reserve To: Jonathan Wakely References: <5741CD4E.4050104@gmail.com> <20160525140157.GK14158@redhat.com> Cc: "libstdc++@gcc.gnu.org" , gcc-patches From: =?UTF-8?Q?Fran=c3=a7ois_Dumont?= Message-ID: <57460F81.8050903@gmail.com> Date: Wed, 25 May 2016 22:48:01 +0200 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Thunderbird/38.7.2 MIME-Version: 1.0 In-Reply-To: <20160525140157.GK14158@redhat.com> On 25/05/2016 16:01, Jonathan Wakely wrote: > On 22/05/16 17:16 +0200, François Dumont wrote: >> 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. > > I don't think the change to __prime_list is safe. If you compile some > code with GCC 5 and then used a libstdc++.so with this change the old > code would still be looking for the sentinel in the array, and would > not find it. > > I think it would be safe to leave the old __prime_list unchanged (and > then not need to change anything in tr1/hashtable_policy.h?) and add a > new array with a different name. Existing code compiled with older > versions of GCC would still find __prime_list, but the new code would > use a different array. > > What about this version ? tr1 mode still limit search range as it should to make sure it doesn't need to check lower_bound result. And sentinel is only kept for backward compatibility and commented to make that clear. Maybe there is a clearer way to express that sentinel can be removed on a future version breaking abi ? François diff --git a/libstdc++-v3/include/tr1/hashtable_policy.h b/libstdc++-v3/include/tr1/hashtable_policy.h index 4ee6d45..2f70289 100644 --- a/libstdc++-v3/include/tr1/hashtable_policy.h +++ b/libstdc++-v3/include/tr1/hashtable_policy.h @@ -403,7 +403,8 @@ _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 }; + // Number of primes minus 1 to avoid check on lower_bound result. + 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..9cbca98 100644 --- a/libstdc++-v3/src/shared/hashtable-aux.cc +++ b/libstdc++-v3/src/shared/hashtable-aux.cc @@ -25,6 +25,7 @@ namespace __detail { _GLIBCXX_BEGIN_NAMESPACE_VERSION + // The sentinel value is only kept for backward compatibility. extern const unsigned long __prime_list[] = // 256 + 1 or 256 + 48 + 1 { 2ul, 3ul, 5ul, 7ul, 11ul, 13ul, 17ul, 19ul, 23ul, 29ul, 31ul,