[webkit-dev] Hashing pairs in WTF

[Dana Jansens]

Hello WebKittens,

I noticed the other day that our hashing method in wtf/HashFunctions.h
for hashing of pairs can be improved.

We have a hash method (WTF::intHash) for a single integer that takes
32 bits as input and produces a key of 32 bits. This works well enough
for hashing an integer, as it is a reversible function.

To hash a pair (A, B) of 32 bits, we hash each of A and B with the
above method, to produce (A', B'). Then concatenate the two and hash
the result to produce a 64 bit hash code. This whole process is
reversible. However, as a final step we truncate the hash code to 32
bits, which destroys the properties of the hashing method. The result
is a hash function that collides more than it should for typical
inputs.

I am proposing a patch [1] to improve the hash method for keys
composed of pairs. The new method [2][3][4] is both almost-universal
and efficient for machines to compute.

To demonstrate the difference I inserted pairs of integers into a
WTF::HashMap. A good hash method will populate the HashMap more
densely. Whereas a bad hash method does not and will cause the HashMap
to require more space and more calls to realloc(), which is a costly
function and will be slower in the end.

In testing, the new hash method reduced the time to insert integer
pair keys into a WTF::HashMap by between 23% and 49% for different
sized input sets. For example, with various input set sizes, the time
to insert into the WTF::HashMap, across multiple runs, was reduced by:

8192 elements: 32% 31% 30% 34% 34% 33%
4096 elements: 47% 48% 48% 47% 47% 49%
1024 elements: 43% 43% 39% 42% 35%
256 elements: 25% 39% 33% 41% 23%

Lookup times into an empty HashMap were also improved, incidentally.
For example, with the old intHash method, making 8192 queries requires
approximately 129ms on my machine while the new method takes less than
1ms. All testing was done on a 64-bit x86 machine. The tests I ran are
attached to the bug [1] for those who may be interested in repeating
the experiment [5].

I want to repeat that the reason the new hash method is faster is
because of better hashing behaviour - ie, fewer collisions and a
denser resulting hash table. I am not comparing the time to do the
hash() itself.

Any feedback would be welcome on the bug!

Thanks,
Dana

[1] https://bugs.webkit.org/show_bug.cgi?id=96022
[2] http://opendatastructures.org/versions/edition-0.1d/ods-java/node33.html#SECTION00832000000000000000
[3] http://pages.cpsc.ucalgary.ca/~woelfel/paper/efficient_strongly/efficient_strongly.pdf
[4] http://pages.cpsc.ucalgary.ca/~woelfel/paper/diss/diss.pdf
[5] https://bugs.webkit.org/attachment.cgi?id=162804