From: "François Dumont" <frs.dumont@gmail.com>
To: "libstdc++@gcc.gnu.org" <libstdc++@gcc.gnu.org>,
gcc-patches <gcc-patches@gcc.gnu.org>
Subject: Enhance std::hash for pointers
Date: Wed, 06 May 2015 20:10:00 -0000 [thread overview]
Message-ID: <554A751E.9030009@gmail.com> (raw)
[-- Attachment #1: Type: text/plain, Size: 982 bytes --]
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 <fdumont@gcc.gnu.org>
* include/bits/functional_hash.h
(std::__detail::_Lowest_power_of_two<size_t>): New.
(std::hash<_Tp*>::operator()): Use latter.
* testsuite/20_util/hash/quality.cc (pointer_quality_test): New.
Tested under Linux x86_64.
François
[-- Attachment #2: pointer_hash.patch --]
[-- Type: text/x-patch, Size: 1782 bytes --]
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<size_t __n>
+ 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<size_t>(__p); }
+ {
+ return reinterpret_cast<size_t>(__p)
+ >> __detail::_Lowest_power_of_two<alignof(_Tp)>::__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<double*> dh;
+ VERIFY( dh(&d1) % sizeof(double) != dh(&d2) % sizeof(double) );
+}
+
int
main()
{
quality_test();
+ pointer_quality_test();
return 0;
}
next reply other threads:[~2015-05-06 20:10 UTC|newest]
Thread overview: 5+ messages / expand[flat|nested] mbox.gz Atom feed top
2015-05-06 20:10 François Dumont [this message]
2015-05-08 8:02 ` Richard Biener
2015-05-08 20:18 ` François Dumont
2015-05-08 22:11 ` Christopher Jefferson
2015-05-11 21:06 ` François Dumont
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=554A751E.9030009@gmail.com \
--to=frs.dumont@gmail.com \
--cc=gcc-patches@gcc.gnu.org \
--cc=libstdc++@gcc.gnu.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).