On Thu, 2006-16-03 at 12:37 +1000, Russell Stuart wrote: > On Wed, 2006-03-15 at 20:28 -0500, jamal wrote: > > The variables again are: > > a) the mask/mask size > > b) the size of the buckets available example if you are masking on 2 > > bits, then it doesnt matter if you have 256 buckets - only 4 get used. > > So creating more than 4 is a waste of memory. > > c) The offset within the 32 bit. I dont think this is a big factor if > > you keep shifting by increments of a byte. > > > > The last one is the range of values in your test data. Example if you > > have only 8 bits that you are masking on, then you dont need an input > > dataset of more than 256 - it adds no value. > > > > IIRC, the old 2.4.x hash is not only inefficient over a wide set of > > values it will be considered plain _buggy_ for lower values. > > > > I think over the weekend i will try to write a little program myself to > > simulate the different cases myself. > > Hmmm, you triggered an idea. You seem to be interested in > one byte values. I think you will have trouble proving > that 2.4 isn't better for multi byte values. >
Try this: 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;-> [Deleting the rest of your email because it is related to the above]. cheers, jamal - 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
