From patchwork Sun Jul 24 19:24:47 2011 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: 106567 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 26723B6F7E for ; Mon, 25 Jul 2011 05:25:16 +1000 (EST) Received: (qmail 25866 invoked by alias); 24 Jul 2011 19:25:13 -0000 Received: (qmail 25841 invoked by uid 22791); 24 Jul 2011 19:25:12 -0000 X-SWARE-Spam-Status: No, hits=-1.7 required=5.0 tests=AWL, BAYES_00, FREEMAIL_FROM, RCVD_IN_DNSWL_NONE X-Spam-Check-By: sourceware.org Received: from smtp6-g21.free.fr (HELO smtp6-g21.free.fr) (212.27.42.6) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Sun, 24 Jul 2011 19:24:56 +0000 Received: from localhost.localdomain (unknown [82.237.250.248]) by smtp6-g21.free.fr (Postfix) with ESMTP id 036EA82252; Sun, 24 Jul 2011 21:24:48 +0200 (CEST) Message-ID: <4E2C717F.6030301@free.fr> Date: Sun, 24 Jul 2011 21:24:47 +0200 From: =?ISO-8859-1?Q?Fran=E7ois_Dumont?= User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.2.18) Gecko/20110621 Mandriva/3.1.11-0.1mdv2010.2 (2010.2) Thunderbird/3.1.11 MIME-Version: 1.0 To: Paolo Carlini CC: "libstdc++@gcc.gnu.org" , gcc-patches@gcc.gnu.org Subject: Re: hash policy patch References: <4E2B2FB0.1080102@free.fr> <4E2B59CB.4010903@oracle.com> In-Reply-To: <4E2B59CB.4010903@oracle.com> 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 On 07/24/2011 01:31 AM, Paolo Carlini wrote: > On 07/23/2011 10:31 PM, François Dumont wrote: >> Hi >> >> While working on DR 41975 I realized a small issue in current >> rehash implementation that sometimes lead to load_factor being >> greater than max_load_factor. Here is a patch to fix that: > Ok, good. > > I think we could as well have everywhere: > > const unsigned long __p = *std::lower_bound... > > and then change the following *__p to __p. Isn't a tad cleaner? > > Thanks, > Paolo. > Attached patch applied, I have integrated your remark Paolo. 2011-07-24 François Dumont * include/bits/hashtable_policy.h (_Prime_rehash_policy): Use __builtin_floor rather than __builtin_ceil to compute next resize value. * testsuite/23_containers/unordered_set/hash_policy/load_factor.cc: New. For info, I will submit a proposal for DR 41975 tomorrow or the day after. Regards Index: include/bits/hashtable_policy.h =================================================================== --- include/bits/hashtable_policy.h (revision 176581) +++ include/bits/hashtable_policy.h (working copy) @@ -427,10 +427,10 @@ _Prime_rehash_policy:: _M_next_bkt(std::size_t __n) const { - const unsigned long* __p = std::lower_bound(__prime_list, __prime_list + const unsigned long __p = *std::lower_bound(__prime_list, __prime_list + _S_n_primes, __n); _M_next_resize = - static_cast(__builtin_ceil(*__p * _M_max_load_factor)); + static_cast(__builtin_floor(__p * _M_max_load_factor)); return *__p; } @@ -441,10 +441,10 @@ _M_bkt_for_elements(std::size_t __n) const { const float __min_bkts = __n / _M_max_load_factor; - const unsigned long* __p = std::lower_bound(__prime_list, __prime_list + const unsigned long __p = *std::lower_bound(__prime_list, __prime_list + _S_n_primes, __min_bkts); _M_next_resize = - static_cast(__builtin_ceil(*__p * _M_max_load_factor)); + static_cast(__builtin_floor(__p * _M_max_load_factor)); return *__p; } @@ -469,17 +469,17 @@ if (__min_bkts > __n_bkt) { __min_bkts = std::max(__min_bkts, _M_growth_factor * __n_bkt); - const unsigned long* __p = - std::lower_bound(__prime_list, __prime_list + _S_n_primes, - __min_bkts); + const unsigned long __p = + *std::lower_bound(__prime_list, __prime_list + _S_n_primes, + __min_bkts); _M_next_resize = static_cast - (__builtin_ceil(*__p * _M_max_load_factor)); + (__builtin_floor(__p * _M_max_load_factor)); return std::make_pair(true, *__p); } else { _M_next_resize = static_cast - (__builtin_ceil(__n_bkt * _M_max_load_factor)); + (__builtin_floor(__n_bkt * _M_max_load_factor)); return std::make_pair(false, 0); } } Index: testsuite/23_containers/unordered_set/hash_policy/load_factor.cc =================================================================== --- testsuite/23_containers/unordered_set/hash_policy/load_factor.cc (revision 0) +++ testsuite/23_containers/unordered_set/hash_policy/load_factor.cc (revision 0) @@ -0,0 +1,58 @@ +// Copyright (C) 2011 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++0x" } + +#include +#include + +void test01() +{ + bool test __attribute__((unused)) = true; + { + std::unordered_set us; + for (int i = 0; i != 100000; ++i) + { + us.insert(i); + VERIFY( us.load_factor() <= us.max_load_factor() ); + } + } + { + std::unordered_set us; + us.max_load_factor(3.f); + for (int i = 0; i != 100000; ++i) + { + us.insert(i); + VERIFY( us.load_factor() <= us.max_load_factor() ); + } + } + { + std::unordered_set us; + us.max_load_factor(.3f); + for (int i = 0; i != 100000; ++i) + { + us.insert(i); + VERIFY( us.load_factor() <= us.max_load_factor() ); + } + } +} + +int main() +{ + test01(); + return 0; +}