From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 9514 invoked by alias); 6 May 2015 20:10:13 -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 9495 invoked by uid 89); 6 May 2015 20:10:13 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.6 required=5.0 tests=AWL,BAYES_00,FREEMAIL_FROM,RCVD_IN_DNSWL_LOW,SPF_PASS autolearn=ham version=3.3.2 X-Spam-User: qpsmtpd, 2 recipients X-HELO: mail-wi0-f180.google.com Received: from mail-wi0-f180.google.com (HELO mail-wi0-f180.google.com) (209.85.212.180) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-GCM-SHA256 encrypted) ESMTPS; Wed, 06 May 2015 20:10:11 +0000 Received: by wiun10 with SMTP id n10so35543137wiu.1; Wed, 06 May 2015 13:10:08 -0700 (PDT) X-Received: by 10.194.172.130 with SMTP id bc2mr749071wjc.85.1430943008498; Wed, 06 May 2015 13:10:08 -0700 (PDT) Received: from [192.168.0.22] (arf62-1-82-237-250-248.fbx.proxad.net. [82.237.250.248]) by mx.google.com with ESMTPSA id 14sm4315077wjv.0.2015.05.06.13.10.07 (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 06 May 2015 13:10:07 -0700 (PDT) Message-ID: <554A751E.9030009@gmail.com> Date: Wed, 06 May 2015 20:10:00 -0000 From: =?UTF-8?B?RnJhbsOnb2lzIER1bW9udA==?= User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.6.0 MIME-Version: 1.0 To: "libstdc++@gcc.gnu.org" , gcc-patches Subject: Enhance std::hash for pointers Content-Type: multipart/mixed; boundary="------------060703080005070309010005" X-SW-Source: 2015-05/txt/msg00499.txt.bz2 This is a multi-part message in MIME format. --------------060703080005070309010005 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Content-length: 978 Hi Following Marc Glisse comment #4 on:https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65641 I would like to propose this enhancement to the hash functor for pointers. It simply gets rid of the irrelevant bits on pointers hash code based on memory alignment of the pointed type. The only drawback I can think of is that the type needs to be complete at std::hash instantiation time but is it really an issue ? IMO it is quite obvious that the resulting hash code will be better but if anyone has a good method to prove it I can try to implement it. The test I have added in quality.cc is very basic and just reflect enhancement following Marc's comment. 2015-05-05 François Dumont * include/bits/functional_hash.h (std::__detail::_Lowest_power_of_two): New. (std::hash<_Tp*>::operator()): Use latter. * testsuite/20_util/hash/quality.cc (pointer_quality_test): New. Tested under Linux x86_64. François --------------060703080005070309010005 Content-Type: text/x-patch; name="pointer_hash.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="pointer_hash.patch" Content-length: 1782 diff --git a/libstdc++-v3/include/bits/functional_hash.h b/libstdc++-v3/include/bits/functional_hash.h index d94843f..a217f8a 100644 --- a/libstdc++-v3/include/bits/functional_hash.h +++ b/libstdc++-v3/include/bits/functional_hash.h @@ -36,6 +36,29 @@ namespace std _GLIBCXX_VISIBILITY(default) { +namespace __detail +{ +_GLIBCXX_BEGIN_NAMESPACE_VERSION + + // Compute highest power of 2 lower or equal to __n. + template + struct _Lowest_power_of_two + { + static const size_t __val + = _Lowest_power_of_two< (__n >> 1) >::__val + 1; + }; + + template<> + struct _Lowest_power_of_two<1> + { static const size_t __val = 0; }; + + template<> + struct _Lowest_power_of_two<0> + { static const size_t __val = 0; }; + +_GLIBCXX_END_NAMESPACE_VERSION +} + _GLIBCXX_BEGIN_NAMESPACE_VERSION /** @defgroup hashes Hashes @@ -63,7 +86,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { size_t operator()(_Tp* __p) const noexcept - { return reinterpret_cast(__p); } + { + return reinterpret_cast(__p) + >> __detail::_Lowest_power_of_two::__val; + } }; // Explicit specializations for integer types. diff --git a/libstdc++-v3/testsuite/20_util/hash/quality.cc b/libstdc++-v3/testsuite/20_util/hash/quality.cc index af417ed..d9c72c7 100644 --- a/libstdc++-v3/testsuite/20_util/hash/quality.cc +++ b/libstdc++-v3/testsuite/20_util/hash/quality.cc @@ -164,9 +164,20 @@ quality_test() } } +void +pointer_quality_test() +{ + bool test __attribute__((unused)) = true; + + double d1, d2; + std::hash dh; + VERIFY( dh(&d1) % sizeof(double) != dh(&d2) % sizeof(double) ); +} + int main() { quality_test(); + pointer_quality_test(); return 0; } --------------060703080005070309010005--