Add methods for hashing pairs of integer values.

Add methods for hashing pairs of integer values.

This will allow us to create hash_maps that are keyed off of std::pair objects
holding two integer values.

When both integers are at most 32-bits we can use 64-bit multiplication to
efficiently find the hash code. When one of the integers is 64-bit, then
we split the two values in the pair into 4 32-bit integers.

References to the algorithms used are contained in comments within the code.
These algorithms are similar to the hash function recently added to WebKit
in https://bugs.webkit.org/show_bug.cgi?id=96022, however since our hash codes
are of type size_t (theirs are unsigned) which is 64 bits large on some
platforms, we can be more efficient and not have to reduce the hash code to 32
bits on some platforms.

Tested by cc_unittests: HashPairTest.IntegerPairs.

BUG=149870
Committed: http://src.chromium.org/viewvc/chrome?view=rev&revision=158479

[jar (doing other things), 2012-09-17 22:01:12]

We don't generally add stuff to base until we see multiple uses of it, or have a
clear example of how it will be used broadly.

In addition, I had comments about this specific hash, that I'd like to better
understand (i.e., the code comments don't seem easy to justify).

https://codereview.chromium.org/10911330/diff/3003/base/hash_tables.h
File base/hash_tables.h (right):

https://codereview.chromium.org/10911330/diff/3003/base/hash_tables.h#newcode119
base/hash_tables.h:119: //   h64(x32, y32) = ((x32 + rand32) % 2^32)((y32 +
rand32) % 2^32) % 2^64
a) It appears that the second modulus operator (mod 2^64) is of no value, since
multiplying two 32 bit numbers (the result of a mod 2^32 operation) always
produces a result that is less than 2^64.

b) The distribution of the product of two numbers is, I believe, well known to
be very non-uniformly distributed, assuming the original numbers were uniformly
distributed.

For example: try multiplying all the numbers from 0-9 by all the numbers from
0-9. That is an example of multiplying all numbers up modulo 10^1 by all numbers
modulo 10^1, and getting a result that is reduced modular 10^2. The results are
VERY skewed toward low numbers.   Note that 10% of the results are zero, none
are over 90,  1% are over 80 (re: 81), and the mean is going to be a mere 12.96.
 Bottom line: This instigates a lot of collisions, and in a relatively poor
hash.

A **MUCH** better 64 bit hash of two 32 bits numbers in to concatenate them
(i.e., multiply one by 2^32, and add to the second).

https://codereview.chromium.org/10911330/diff/3003/base/hash_tables.h#newcode126
base/hash_tables.h:126: //   h32(x32, y32) = (h64(x32, y32) * randOdd64 + rand32
* 2^32) % 2^64 / 2^32
Here, the addition of rand32 * 2^32 is useless, for mixing purposes.  It does
not increase or decrease collisions.

Once you take that away, you can see that this has appears to do little more
than you'd get from taking only the upper 32 bits of a 64 bit hash.

What am I missing?

[danakj, 2012-09-18 23:09:24]

On Mon, Sep 17, 2012 at 6:01 PM,  <jar@chromium.org> wrote:
> We don't generally add stuff to base until we see multiple uses of it, or
> have a
> clear example of how it will be used broadly.

While this hasn't been used widely in Chromium (because the method
wasn't available?), this is something used in cc which is migrating
from the WebKit codebase to the Chromium codebase. Here's some
examples of where it is used in cc:

http://code.google.com/searchframe#OAMlx_jo-ck/src/cc/CCRenderPass.h&exact_pa...
http://code.google.com/searchframe#OAMlx_jo-ck/src/cc/CCDirectRenderer.h&exac...
http://code.google.com/searchframe#OAMlx_jo-ck/src/cc/CCLayerTilingData.h&exa...

As an argument for putting this in base, it is something used widely
in WebKit since the hash method was added, and might be of value to
the Chromium project at large. Here's some more examples of use in
WebKit:

http://code.google.com/searchframe#OAMlx_jo-ck/src/third_party/WebKit/Source/...
http://code.google.com/searchframe#OAMlx_jo-ck/src/third_party/WebKit/Source/...
http://code.google.com/searchframe#OAMlx_jo-ck/src/third_party/WebKit/Source/...
http://code.google.com/searchframe#OAMlx_jo-ck/src/third_party/WebKit/Source/...
http://code.google.com/searchframe#OAMlx_jo-ck/src/third_party/WebKit/Source/...
http://code.google.com/searchframe#OAMlx_jo-ck/src/third_party/WebKit/Source/...
http://code.google.com/searchframe#OAMlx_jo-ck/src/third_party/WebKit/Source/...
http://code.google.com/searchframe#OAMlx_jo-ck/src/third_party/WebKit/Source/...
http://code.google.com/searchframe#OAMlx_jo-ck/src/third_party/WebKit/Source/...
http://code.google.com/searchframe#OAMlx_jo-ck/src/third_party/WebKit/Source/...
http://code.google.com/searchframe#OAMlx_jo-ck/src/third_party/WebKit/Source/...

> In addition, I had comments about this specific hash, that I'd like to
> better
> understand (i.e., the code comments don't seem easy to justify).

Sure!

> https://codereview.chromium.org/10911330/diff/3003/base/hash_tables.h
> File base/hash_tables.h (right):
>
>
https://codereview.chromium.org/10911330/diff/3003/base/hash_tables.h#newcode119
> base/hash_tables.h:119: //   h64(x32, y32) = ((x32 + rand32) %
> 2^32)((y32 + rand32) % 2^32) % 2^64
> a) It appears that the second modulus operator (mod 2^64) is of no
> value, since multiplying two 32 bit numbers (the result of a mod 2^32
> operation) always produces a result that is less than 2^64.

Yes, it's more a statement that the multiplication is happening in 64
bits rather than 32.

> b) The distribution of the product of two numbers is, I believe, well
> known to be very non-uniformly distributed, assuming the original
> numbers were uniformly distributed.
>
> For example: try multiplying all the numbers from 0-9 by all the numbers
> from 0-9. That is an example of multiplying all numbers up modulo 10^1
> by all numbers modulo 10^1, and getting a result that is reduced modular
> 10^2. The results are VERY skewed toward low numbers.   Note that 10% of
> the results are zero, none are over 90,  1% are over 80 (re: 81), and
> the mean is going to be a mere 12.96.  Bottom line: This instigates a
> lot of collisions, and in a relatively poor hash.

Thanks for the challenge and making me think more about this. You're
right and I'm overthinking the problem here. When we have essentially
a 64-bit input and a 64-bit key space, we don't need to apply a
function for hashing an arbitrary number of 32 values into 64 bits.

>
https://codereview.chromium.org/10911330/diff/3003/base/hash_tables.h#newcode126
> base/hash_tables.h:126: //   h32(x32, y32) = (h64(x32, y32) * randOdd64
> + rand32 * 2^32) % 2^64 / 2^32
> Here, the addition of rand32 * 2^32 is useless, for mixing purposes.  It
> does not increase or decrease collisions.
> Once you take that away, you can see that this has appears to do little
> more than you'd get from taking only the upper 32 bits of a 64 bit hash.
>
> What am I missing?

Thank you for reading this through. This was a bad translation from
the thesis (which is in German
http://pages.cpsc.ucalgary.ca/~woelfel/paper/diss/diss.pdf).

I'll spell out the theorem carefully here for the both of us. (Note we
have p=2 throughout if you're following the thesis.)

On page 55 we see V* defined as the set of odd integers in {0,...,2^n}.

Then on page 56:

Let r = 2^m = hash result space => m = 32, r=2^32.
Let v = kr = 2^n = working space => n = 64, k=2^32.

Then the Theorem 4.3.3 (b) is:

Let T = 2^t where:
  0 <= t <= ceil( (n-m)/2 ).
  0 <= t <= 32/2 = 16
So let's have t = 16 and T=2^16.

Let B = { iT | 0 <= i < k/T }
For us k=2^32, so from our choice of T,
B = { iT | 0 <= i < 2^16 } = { 0, 2^16, 2^17, 2^18, ... 2^31 }

Let a be randomly chosen from V* (odd value in {0,...,2^64}).
And let b be randomly chosen from B.

Then ((ax+b) mod (2^64)) div 2^32 is 1-universal.

Clearly the b we're choosing the CL I submitted is not from this set
B, so I will fix this.

Intuitively, what this means is that once both keys end up in a
bucket, they are still randomly positioned within the bucket, and by
shifting them to the right, we may cause one to jump out of the bucket
but not the other.

[danakj, 2012-09-19 00:04:14]

I still need to make windows compile with its confusing hash_map implementation,
but PTAL at the new version. Thanks.

[danakj, 2012-09-21 02:14:04]

On 2012/09/19 00:04:14, danakj wrote:
> I still need to make windows compile with its confusing hash_map
implementation,
> but PTAL at the new version. Thanks.

Got windows working too now!

[jar (doing other things), 2012-09-24 20:52:21]

Although it is plausible that we should add such a hash, I don't think it makes
sense to attempt to construct constants based on a theoretical paper.  Much
better is to use an existing, and tested hash, with *EXACTLY* the constants that
were used in testing.

Details below.

https://codereview.chromium.org/10911330/diff/27004/base/hash_tables.h
File base/hash_tables.h (right):

https://codereview.chromium.org/10911330/diff/27004/base/hash_tables.h#newcod...
base/hash_tables.h:156: uint64 oddRandom = 885644242649267641LL; \
FWIW: This is a strange odd number: about 2^56, hence the first 8 bits are zero.
 I don't know if it is singnificant... but it is surprising.

https://codereview.chromium.org/10911330/diff/27004/base/hash_tables.h#newcod...
base/hash_tables.h:195: uint32 shortRandom3 = 29379286U; \
This was a strange choice for a random odd number.  The range of choices is
0-(2^32 - 1).  You chose a number that is about 2^25.  Hence you chose to have
the first 7 bits set at zero.   I guess "every number" is a random number, but
it is generally only a 1 in 128 chance that you'd have so many leading zeros. 
The consequence of this is that when you do the multiply (by a 32 bit number),
that the high order 7 bits of the 64-bit result will always be zero.  Since the
next step in your process is close to discarding the low order 32 bits, you've
effectively started your hashing by mapping 32 bits to 25 bits.  As a result, I
think your hash will tend to drop a lot of the distinction in the item
multiplied, which means it will have a lot of collisions (right out of the gate,
and not caused by the limitation of the resulting hash size).

This is the second CL that has me concerned about the quality of the hash you
are proposing.  Can you look to find an actual hash, rather than a theoretical
paper that asks you to "choose a random number," and use that as a basis?  An
"actual" hash, with specific constants, will have been analyzed, and have
presumably better properties.

[danakj, 2012-09-24 21:09:03]

https://codereview.chromium.org/10911330/diff/27004/base/hash_tables.h
File base/hash_tables.h (right):

https://codereview.chromium.org/10911330/diff/27004/base/hash_tables.h#newcod...
base/hash_tables.h:195: uint32 shortRandom3 = 29379286U; \
All the random numbers were generated using random.org.

There are lots of "hashes" around that do not use random seeds and are not
provably good, but I don't really understand the resistance to a random seed in
the algorithm.

[danakj, 2012-09-24 22:10:09]

I've moved the hash pair code into cc/ to unblock GTFO, and marked enne as
reviewer. By eir request, I've regenerated the random values in the methods.

[enne (OOO), 2012-09-24 22:12:02]

Do you need to add hash_pair.h to some gyp file too?

[danakj, 2012-09-24 22:14:26]

On 2012/09/24 22:12:02, enne wrote:
> Do you need to add hash_pair.h to some gyp file too?

Good idea, I'll add it to cc.gyp

[enne (OOO), 2012-09-24 22:17:20]

lgtm

[commit-bot: I haz the power, 2012-09-24 22:28:03]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/danakj@chromium.org/10911330/40002

[commit-bot: I haz the power, 2012-09-25 01:05:02]

Change committed as 158479