[ovs-discuss] [PATCH] hash: Improve 128-bit hash to 32-bit output.

[Alex Wang]

Hey All,

I'm helping Joe to look at this issue.

Here is excerpt of Joe's comment on his original patch:
"""
My thoughts are converging towards this: The test is very strict,
particularly for inputs that have little variance (eg, single bit set
in the whole input). The hash function itself has been thoroughly
tested by the original developers at Google, and I shouldn't have done
anything to decrease the hash quality. I'm inclined to push the
testsuite change that modifies the seed to something which passes on
both big- and little-endian systems.
"""

Seems to me that the hash function is meant to compute hash for very long
words (longer than 128 bits, e.g. struct flow).  And we already have test
for
checking the 1-bit set case for hash of 16*128-bit word.  So, could we just
remove the this failing test that uses uint32_t as input and add comment to
warn users (that the function should only be called with > 128-bit word)?

The patch is sent out here:
http://openvswitch.org/pipermail/dev/2015-February/051727.html

Thanks,
Alex Wang,

On Tue, Dec 30, 2014 at 10:28 AM, Andrew Mann <andrew at divvycloud.com> wrote:

> For what it's worth, Bob Jenkins has some good discussion around this, and
> some code that can help measure such properties of hashes:
>
> http://burtleburtle.net/bob/hash/index.html
>
> Specifically the "tests" section may offer a good start for measuring the
> characteristics of the hash output with quantitative results.
>
> On Mon, Dec 29, 2014 at 3:08 PM, Ben Pfaff <blp at nicira.com> wrote:
>
>> On Mon, Dec 22, 2014 at 03:35:22PM -0800, Joe Stringer wrote:
>> > Previously, when using the 128-bit hash in conjunction with the 32-bit
>> > hash tables, we would ignore the upper 96 bits rather than attempting to
>> > redistribute the hash across the 32-bit output space. This patch adds a
>> > new function to translate the hash down from 128 bits to 32 bits for
>> > this use case.
>>
>> Suppose that we had 128-bit random numbers instead of 128-bit hashes.
>> Then, if combining the 32-bit pieces of that random number gave us a
>> higher-quality random 32-bit number than just taking any one 32-bit
>> piece, it would mean that the random numbers weren't very random.
>>
>> By analogy, I think that this patch (without reading it) should only
>> make a difference if the 128-bit hash isn't very high-quality.  If so,
>> it might be better to consider improving our 128-bit hash function,
>> instead of the approach taken here.
>> _______________________________________________
>> discuss mailing list
>> discuss at openvswitch.org
>> http://openvswitch.org/mailman/listinfo/discuss
>>
>
>
>
> --
> Andrew Mann
> DivvyCloud Inc.
> www.divvycloud.com
>
> _______________________________________________
> discuss mailing list
> discuss at openvswitch.org
> http://openvswitch.org/mailman/listinfo/discuss
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://openvswitch.org/pipermail/ovs-discuss/attachments/20150226/2e6d44ea/attachment-0002.html>