On Sun, 2006-03-19 at 11:32 -0500, jamal wrote: > Conclusion > ---------- > > Other than fixing a bug, then new hash is at least equal to the old > hash in about 16% of the cases and better in the rest(>80% of the > time). > This is true in the case of both memory abuse and worst case lookups. > > I believe there is room for improvement but it has absolutely > nothing to do with the old hash (and for that matter not the new one > either, even though the new one is a lot better).
>From what I can see, you are not testing a "real" data set here. Is that the case? If so I am not sure how to respond to this, other than to say it is possible to construct datasets that show either hash (2.4 or 2.6) to be better. I am not sure if you understand what I mean when I say this, but perhaps my data analysis will make it clearer where I am coming from. By the by, I feel more comfortable with metrics than graphs. Once you agree on them they take much less time to discuss: either the single number is better, or it isn't. The "Norm" metric I introduced in the analysis is meant to be a crude measure of the actual runtime of the hash. I am hoping you will be more comfortable with it than the least squares one I proposed earlier. On Sun, 2006-03-19 at 12:28 -0500, jamal wrote: > I am not so certain now you can do better than the current algorithm in > optimizing for lookup as well as memory use. > The key is for the user to look at the mask length used and conclude on > what the divisor should be. The "new" algorithm can emulate 2.4 or 2.6 "at will" through a suitable choice of mask. If there are cases where 2.4 hash will run faster, then it will always be a better choice than either 2.4 or 2.6. If there is no time when 2.4 runs faster, then we should stick with the 2.6 algorithm. As I said in earlier post, it is possible to come up with fake datasets that make 2.4 run faster than 2.6. If you want one just ask. In my mind that should settle the issue as there is potential for any real dataset to approximate the fake one, but as the datasets are obviously fake and you don't accept my arguments about random data, perhaps it doesn't. My analysis presents a real live data set where 2.4 is faster - well I think it does anyway. One other point which occurred to me while I was hacking away on the weekend. As the new hash emulates the 2.4 hash exactly for any sane choice of mask (ie one where the lsb of the mask falls on a byte boundary), it is close to being backwards compatible with the old one. For example, had the 2.6 kernel used the new hash, and tc still computed the old one - I would never of noticed. The new hash also emulates the current 2.6 hash for any sane choice of mask - ie one no larger than 8 bits. Again that means the change would be almost invisible to current 2.6 hash users - even you. - 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
