From: Eric Wong <e@80x24.org>
To: spew@80x24.org
Subject: [PATCH] hash.c: improve integer hashing
Date: Wed, 29 Jul 2015 19:58:39 +0000 [thread overview]
Message-ID: <1438199919-20862-1-git-send-email-e@80x24.org> (raw)
The low bits of Ruby object IDs are rarely populated in the current
implementation, so ensure the get used.
* hash.c (rb_num_hash_start): extract from rb_ident_hash
(rb_objid_hash): call rb_num_hash_start
(rb_ident_hash): ditto
---
hash.c | 36 +++++++++++++++++++++++-------------
1 file changed, 23 insertions(+), 13 deletions(-)
diff --git a/hash.c b/hash.c
index 4d5b4c6..062805b 100644
--- a/hash.c
+++ b/hash.c
@@ -177,10 +177,30 @@ rb_any_hash(VALUE a)
return any_hash(a, obj_any_hash);
}
+static st_index_t
+rb_num_hash_start(st_index_t n)
+{
+ /*
+ * This hash function is lightly-tuned for Ruby. Further tuning
+ * should be possible. Notes:
+ *
+ * - (n >> 3) alone is great for heap objects and OK for fixnum,
+ * however symbols perform poorly.
+ * - (n >> (RUBY_SPECIAL_SHIFT+3)) was added to make symbols hash well,
+ * n.b.: +3 to remove ID scope, +1 worked well initially, too
+ * - (n << 3) was finally added to avoid losing bits for fixnums
+ * - avoid expensive modulo instructions, it is currently only
+ * shifts and bitmask operations.
+ */
+ return (n >> (RUBY_SPECIAL_SHIFT + 3) | (n << 3)) ^ (n >> 3);
+}
+
long
rb_objid_hash(st_index_t index)
{
- st_index_t hnum = rb_hash_start(index);
+ st_index_t hnum = rb_num_hash_start(index);
+
+ hnum = rb_hash_start(hnum);
hnum = rb_hash_uint(hnum, (st_index_t)rb_any_hash);
hnum = rb_hash_end(hnum);
return hnum;
@@ -215,28 +235,18 @@ static const struct st_hash_type objhash = {
static st_index_t
rb_ident_hash(st_data_t n)
{
+#ifdef USE_FLONUM /* RUBY */
/*
- * This hash function is lightly-tuned for Ruby. Further tuning
- * should be possible. Notes:
- *
- * - (n >> 3) alone is great for heap objects and OK for fixnum,
- * however symbols perform poorly.
- * - (n >> (RUBY_SPECIAL_SHIFT+3)) was added to make symbols hash well,
- * n.b.: +3 to remove ID scope, +1 worked well initially, too
- * - (n << 3) was finally added to avoid losing bits for fixnums
- * - avoid expensive modulo instructions, it is currently only
- * shifts and bitmask operations.
* - flonum (on 64-bit) is pathologically bad, mix the actual
* float value in, but do not use the float value as-is since
* many integers get interpreted as 2.0 or -2.0 [Bug #10761]
*/
-#ifdef USE_FLONUM /* RUBY */
if (FLONUM_P(n)) {
n ^= (st_data_t)rb_float_value(n);
}
#endif
- return (st_index_t)((n>>(RUBY_SPECIAL_SHIFT+3)|(n<<3)) ^ (n>>3));
+ return (st_index_t)rb_num_hash_start((st_index_t)n);
}
static const struct st_hash_type identhash = {
--
EW
next reply other threads:[~2015-07-29 19:58 UTC|newest]
Thread overview: 4+ messages / expand[flat|nested] mbox.gz Atom feed top
2015-07-29 19:58 Eric Wong [this message]
-- strict thread matches above, loose matches on Subject: below --
2015-07-29 22:46 [PATCH] hash.c: improve integer hashing Eric Wong
2015-07-29 22:20 Eric Wong
2015-07-28 21:16 Eric Wong
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=1438199919-20862-1-git-send-email-e@80x24.org \
--to=e@80x24.org \
--cc=spew@80x24.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).