From: Eric Wong <normalperson@...>
Date: 2014-03-17T23:03:44+00:00
Subject: [ruby-core:61568] hash function for global method cache

I came upon this because I noticed existing st numtable worked poorly
with power-of-two hashes in [ruby-core:61243].

Global method cache is power-of-two-sized; so it should have a good hash
function.  In vm_method.c:

#define GLOBAL_METHOD_CACHE_KEY(c,m) ((((c)>>3)^(m))&GLOBAL_METHOD_CACHE_MASK)

Where c = klass; m = id (method ID)

I'm a bit puzzled by the existing hash, since:
1) low 3 (scope) bits of method ID are infrequently set
2) c is a heap address, where c % sizeof(RValue) == 0 is always true
3) high bits of ID are always zero
4) high bits of klass tend to not vary within the process

Has anybody else looked into improving the hash function?  So I think we
can do better (but I'm not an expert in hashing).

One thing I've also been meaning to do is use 21-bits of the
SipHash(sym) value to generate IDs, which ought to hash better in st
numtable than incrementing integers (but we will need to handle
resolving ID potential collisions).

This will be on my TODO list;