On Wed, 2006-03-15 at 22:07 -0500, jamal wrote: > Suppose you pick octet 3 of the dst IP address and we assume the full > range of that octet i.e a range of values 0-255 > (the details are a lot more complicated of where this byte belongs, > example this could be part of an IPV6 address and we take all the bits > and spread them horizontally in many hash tables): > Assume for a specific hash table you are interested in only 6 bits > so use a mask of 0xfc. > Now clearly it doesnt make sense to have anything more than 64 buckets. > So restrict your buckets to 64. > > Run the two algorithms. Derive using your equation how things look like. > I have a feeling that you may need to plot to see this. > Next try to make the hasn buckets > 64 say 128, 256. > Next try to vary the offset of this byte and therefore the mask within > a 32 bit;-> > And when you are done and things look odd then run the full test results > by varying the variables. I am certain that the values you picked for > hash buckets etc make the old hash look favorable; but that will be one > of the _very_ few cases where it would look good. > This is not hard - we need some scientific data;->
There is no need to run a test. Evidently, I didn't make myself clear in the previous email. Assume the value you are hashing on is: +-------------------------+ | B0 B1 B2 B3 B4 B5 B6 B7 | +-------------------------+ After masking it will be: +-------------------------+ | B0 B1 B2 B3 B4 B5 0 0 | +-------------------------+ After hashing it will be: 2.4: 2.6: +-------------------------+ +-------------------------+ | B0 B1 B2 B3 B4 B5 0 0 | | 0 0 B0 B1 B2 B3 B4 B5 | +-------------------------+ +-------------------------+ If the divisor is 256 both hashes will perform identically. If the divisor is 64, we save 768 bytes in the kernel. But now the hashes change to: 2.4: 2.6: +-------------------------+ +-------------------------+ | 0 0 B2 B3 B4 B5 0 0 | | 0 0 B0 B1 B2 B3 B4 B5 | +-------------------------+ +-------------------------+ With a divisor of 64 bytes, the 2.6 hash produces 6 bit quantity which enumerates to 64 unique values, and the 2.4 hash produces 4 bits which enumerates to 16 unique values. Ergo, each 2.4 bucket will hold 4 values (=64 / 16), whereas the 2.6 buckets will hold one each (=64 / 64). Thus in this case, we can say that either: 2.4 and 2.6 use the same amount of memory, but 2.4 runs slower. 2.4 and 2.6 run at the same speed, but 2.4 uses more memory. Take your pick. BTW, in this example, the new hash I suggested would be as good as the 2.6 case. Now lets take the case that we hashing a number of bytes with a 256 divisor (my case). If these bytes contain truly random values, then again 2.4 and 2.6 will be the same. This is because the hash value 2.6 uses, the low order byte is already perfectly random - so it can't be improved on. The 2.4 XOR's the two values together. XOR has the property that it "adds" the randomness of the bits together, unless they are correlated. So if you take two partially random bits, and XOR them together, then the resulting bit will be more random that the original two bits. An illustration of this from crypto is a stream cypher like rc4. rc4 effectively produces a random stream of bits. To use rc4, you XOR your plain text with this random stream. Even though your plain text is highly non-random, the cypher text is at least as random as the rc4 stream - and thus looks like gibberish. Anyway, the end result for 2.4 is that if you XOR two perfectly random bytes, the result is a perfectly random byte. So for random data 2.6 and 2.4 are the same. Now lets take non-random data - say a bunch of IPv6 addresses. Particularly in the mac address part, you know some bits are going to be highly non-random. Here 2.4 is going to do much better than 2.6. To illustrate, lets take the trivial case where there is only 1 non-random bit somewhere. The odds of that random bit being in the low order byte, which is what becomes 2.6's hash, is 1 in 4 (there being a 1 in 4 chance that bit will end up in the lower order byte - there being 4 bytes it could end up in with equal probability). So 2.6 has a 1 in 4 chance of 2.6 producing a good hash. In the case of 2.4, because the bytes are XOR'ed, the odds are 1 in 1 - ie it is a certain 2.4 will produce the best hash possible. If there are 2 random bits, then then best hash will have 2 bits of randomness. The odds of the 2.6 ending up with this hash are 1 in 17.71. (This is (8/32)*(7/32) - ie there are 8 ways in 32 the first bit can end up in the low order byte, and 7 ways in 31 the next bit can end up in the low order byte, and we need both these events to happen so we multiply. The odds of 2.4 ending up with it is 10.33. (Once the first bit is allocated, there are 3 ways in 31 the second bit would overlap it in an XOR.) The odds of 2.6 picking the next best hash, with 1 bit of randomness, is 5.16. The odds of 2.4 getting 1 random bit in the hash is a 1 in 1.11 (because the only other possibility is that it will get 2 bits, so the answer is (1 - 1/10.33).) The remaining possibly is that no bits of randomness end up in the hash. This isn't possible for 2.4, but for 2.6 there is a 1 in 1.3 chance. And you can go on, but the only cases where 2.6 will get a hash a good as 2.4 is when the entire value is perfectly random, or when it is fixed. Neither is very likely. I hope I haven't lost you in there somewhere. The bottom line is that unless there are correlated bits (and there haven't been in any real life examples either you or I have presented so far), the 2.4 hash will always be better than the 2.6 one for multibyte values. As you example demonstrated, for less than 8 bits the 2.4 algorithm may use more memory than the 2.6 one in some cases - if you take that option. Provided you do take the "more memory" option, it will _always_ run as fast as 2.6. But the new hash I suggested behaves as well as the 2.4 version on multibyte values, and as well as the 2.6 version in sub-byte values. Replacing the current hash function with it would may us both happy. - To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
