Two problems with the comparison:
Port numbers can be collected into a 32 bit register in network
byte order directly from the TCP packet without taking two 16 bit
values and shifting and or'ing them.
Worse: he folded the jenkins algorith result with
h ^= h >> 16;
h ^= h >> 8;
Destroying the coverage of the function.
I, for one, am not suprised that artifacts appeared in the comparison
as a result of this destruction of the coverage of the hashing function.
Two problems with the comparison:
Port numbers can be collected into a 32 bit register in network
byte order directly from the TCP packet without taking two 16 bit
values and shifting and or'ing them.
Worse: he folded the jenkins algorith result with
h ^= h >> 16;
h ^= h >> 8;
Destroying the coverage of the function.
It was done to simulate socket code which uses the same folding.
Leaving 32bit space is just wrong, consider hash table size with that
index.
I, for one, am not suprised that artifacts appeared in the comparison
as a result of this destruction of the coverage of the hashing function.
It is comparison of the approach used in TCP hashing code, it is not full
mathematical analysis. And in that case jenkins hash already not good.
I'm sure it can be tuned, but it does require a lot of iterations, while
XOR one "just works".
--
Evgeniy Polyakov
Two problems with the comparison:
Port numbers can be collected into a 32 bit register in network
byte order directly from the TCP packet without taking two 16 bit
values and shifting and or'ing them.
Using network or host byte order does not affect hash distribution,
that shifting was coded to simulate other types of mixing ports,
which actually never showed different results.
quoted
Worse: he folded the jenkins algorith result with
h ^= h >> 16;
h ^= h >> 8;
Destroying the coverage of the function.
It was done to simulate socket code which uses the same folding.
Leaving 32bit space is just wrong, consider hash table size with that
index.
quoted
I, for one, am not suprised that artifacts appeared in the comparison
as a result of this destruction of the coverage of the hashing function.
It is comparison of the approach used in TCP hashing code, it is not full
mathematical analysis. And in that case jenkins hash already not good.
I'm sure it can be tuned, but it does require a lot of iterations, while
XOR one "just works".
Two problems with the comparison:
Port numbers can be collected into a 32 bit register in network
byte order directly from the TCP packet without taking two 16 bit
values and shifting and or'ing them.
Using network or host byte order does not affect hash distribution,
that shifting was coded to simulate other types of mixing ports,
which actually never showed different results.
quoted
quoted
Worse: he folded the jenkins algorith result with
h ^= h >> 16;
h ^= h >> 8;
Destroying the coverage of the function.
It was done to simulate socket code which uses the same folding.
Leaving 32bit space is just wrong, consider hash table size with that
index.
Btw, that probably requires some clarification.
Since hash table size is definitely less than returned hash value, so
higher bits are removed, for that case above folding is done both in
XOR hash and my test case.
It is possible to just remove higher bits, but fairly ditributed parts
being xored produce still fairly distributed value.
--
Evgeniy Polyakov
On Wed, May 31, 2006 at 03:51:24AM -0600, Brian F. G. Bidulock (bidulock@openss7.org) wrote:
quoted
Worse: he folded the jenkins algorith result with
h ^= h >> 16;
h ^= h >> 8;
Destroying the coverage of the function.
It was done to simulate socket code which uses the same folding.
Leaving 32bit space is just wrong, consider hash table size with that
index.
You absolutely show not do this shifting on the jenkins hash
result, you destroy the distribution entirely. Just mask
it with the hash mask and that's all you need to do.
Brian is right, this is absolutely critical to using the Jenkins hash
correctly. You're "unmixing" the bits it worked so hard to mix.
On Wed, May 31, 2006 at 11:41:27AM -0700, David Miller (davem@davemloft.net) wrote:
quoted
quoted
Worse: he folded the jenkins algorith result with
h ^= h >> 16;
h ^= h >> 8;
Destroying the coverage of the function.
It was done to simulate socket code which uses the same folding.
Leaving 32bit space is just wrong, consider hash table size with that
index.
You absolutely show not do this shifting on the jenkins hash
result, you destroy the distribution entirely. Just mask
it with the hash mask and that's all you need to do.
Brian is right, this is absolutely critical to using the Jenkins hash
correctly. You're "unmixing" the bits it worked so hard to mix.
That is wrong. And I have a code and picture to show that,
and you dont - prove me wrong :)
Attached code and picture which shows _exactly_ the same distribution for
folded and not folded Jenkins hash distribution, and it's artifact
compared to XOR hash.
Fairly distributed values being XORed produce still fairly distributed
value.
--
Evgeniy Polyakov