`On Fri, Apr 29, 2016 at 2:10 PM, Linus Torvalds<torvalds@linux-foundation.org> wrote:> On Thu, Apr 28, 2016 at 11:32 AM, Linus Torvalds> <torvalds@linux-foundation.org> wrote:>>>> hash_long/ptr really shouldn't care about the low bits being zero at>> all, because it should mix in all the bits (using a prime multiplier>> and taking the high bits).>> Looking at this assertion, it doesn't actually pan out very well at all.>> The 32-bit hash looks to be ok. Certainly not perfect, but not horrible.>> The 64-bit hash seems to be quite horribly bad with lots of values.Ok, I have tried to research this a bit more. There's a lot ofconfusion here that causes the fact that hash_64() sucks donkey balls.The basic method for the hashing method by multiplication is fairlysane. It's well-documented, and attributed to Knuth as the commentabove it says.However, there's two problems in there that degrade the hash, andparticularly so for the 64-bit case.The first is the confusion about multiplying with a prime number..That actually makes no sense at all, and is in fact entirely wrong.There's no reason to try to pick a prime number for themultiplication, and I'm not seeing Knuth having ever suggested that.Knuth's suggestion is to do the multiplication with a floating pointvalue A somewhere in between 0 and 1, and multiplying the integer withit, and then just taking the fractional part and multiply it up by 'm'and do the floor of that to get a number in the range 0..mAt no point are primes involved.And our multiplication really does approximate that - except it'sbeing done in fixed-point arithmetic (so the thing you multiply withis basically n./2**64, and the overflow is what gets rid of thefractional part - then getting the "high bits" of the result is reallyjust multiplying by a power of two and taking the floor of theresult).So the first mistake is thinking that the thing you should multiplywith should be prime. The primality matters for when you use adivision to get a modulus, which is presumably where the confusioncame from.Now, what value 'A' you use doesn't seem to really matter much. Knuthsuggested the fractional part of the golden ratio, but I suspect thatis purely because it's an irrational number that is not near to 0 or1. You could use anything, although since "random bit pattern" is partof the issue, irrational numbers are a good starting point. I suspectthat with our patterns, there's actually seldom a good reason to dolots of high-order bits, so you might as well pick something closer to0, but whatever - it's only going to matter for the overflow part thatgets thrown away anyway.The second mistake - and the one that actually causes the real problem- is to believe that the "bit sparseness" is a good thing. It's not.It's _very_ much not. If you don't mix the bits well in themultiplication, you get exactly the problem we hit: certain bitpatternsjust  will not mix up into the higher order bits.So if you look at what the actual golden ratio representation *should* have bee:  #define GOLDEN_RATIO_32 0x9e3779b9  #define GOLDEN_RATIO_64 0x9e3779b97f4a7c16and then compare it to the values we actually _use_ (bit-sparse primescloseish to those values):  #define GOLDEN_RATIO_PRIME_32 0x9e370001UL  #define GOLDEN_RATIO_PRIME_64 0x9e37fffffffc0001ULyou start to see the problem. The right set of values have roughly 50%of the bits set in a random pattern. The wrong set of values do not.But as far as I an tell, you might as well use the fractional part of'e' or 'pi' or just make random shit up that has a reasonable bitdistribution.So we could use the fractional part of the golden ratio (phi):  0x9e3779b9  0x9e3779b97f4a7c16or pi:  0x243f6a88  0x243f6a8885a308d3or e:  0xb7e15162  0xb7e151628aed2a6bor whatever. The constants don't have to be prime. They don't evenhave to be odd, because the low bits will always be masked off anyway.The whole "hash one integer value down to X bits" is very different inthis respect to things like string hashes, where you really do tend towant primes (because you keep all bits).But none of those are sparse. I think *some* amount of sparsenessmight be ok if it allows people with bad CPU's to do it usingshift-and-adds, it just must not be as sparse as the current number,the 64-bit one on particular.There's presumably a few optimal values from a "spread bits outevenly" standpoint, and they won't have anything to do with randomirrational constants, and will have everything to do with having nicebitpatterns.I'm adding Rik to the cc, because the original broken constants camefrom him long long ago (they go back to 2002, originally only used forthe waitqueue hashing. Maybe he had some other input that caused himto believe that the primeness actually mattered.                 Linus`