Re: Results WAS(Re: [PATCH] TC: bug fixes to the "sample" clause
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
Re: Results WAS(Re: [PATCH] TC: bug fixes to the "sample" clause
On Mon, 2006-20-03 at 14:46 +1000, Russell Stuart wrote: > On Sun, 2006-03-19 at 11:32 -0500, jamal wrote: > From what I can see, you are not testing a "real" data > set here. Is that the case? Its a worst case scenario test setup - You lookup at all possible data values. Normally it is the best way to produce a metric for a classifier (actually i left out the best case scenario which would complete this - but it doesnt make a difference for us). > 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 have to say i am scratching my head - now that i was forced to run the tests - to see if there is infact a scenario where you could show 2.4 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. > I cant access your page - it is timing out. However, again, as i stated in my email after this (yesterday after looking at the 16 bit masks); i dont see a scenario where the 2.4.x could ever produce something better than 2.6.x in terms of lookup + memory use. > 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. > The least squares is not bad - only issue is it missed the criteria i had for looking at the number of buckets selected. I think if we had no choice on changing the hash table, it would have been perfect. > 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. > I dont think there is ever a time where 2.4.x does better; there are times where it does equal. From what i saw in those tests (and probably not emphasized enough), the issue is in the "possible values" of a selected mask. If you ever had data-values which will end up using less than 256 buckets (eg in the case of 0xfe,0xfc00 or 0xf8) then the 2.4.x will never be better - ever. Under normal circumstances they will be equal. > 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. I would love to see one. > 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. > The data randomness doesnt matter. If i was forced to use a mask of 0xf8, 0xf800 etc, there is no way this random data is going to help me suddenly have better distribution. And under normal circumstances, there will be no difference between the two (random or not). The only thing randomness would do is favor some buckets over others - but that would be very specific to an environment and if you did move to a different environment, different buckets will be favored etc. So you dont use that to judge a classifier. > 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. Ok now, give it up Russell ;-> We are not just gonna add a couple new instructions in the datapath for an obscure feature that more than likely is used by less than a handful of people. I certainly would not agree to it as i take performance very seriously. The backward compatibility (for people using 256 buckets, 0xff) already exists. Unless you have some data where 2.6.x looks worse we could use the time to discuss more productive things (perhaps related to u32) instead and move on away from this topic. OTOH, I
Re: Results WAS(Re: [PATCH] TC: bug fixes to the "sample" clause
On Mon, 2006-03-20 at 10:00 -0500, jamal wrote: > I have to say i am scratching my head - now that i was forced to run the > tests - to see if there is infact a scenario where you could show 2.4 to > be better... So that is the underlying reason you are resisting - you just can't see that it could be so. Sorry ... it has taken me this long to figure that out. Anyway the analysis has a real life example. > I cant access your page - it is timing out. Jeezz, that pisses me off. What is it with the bloody internet? This isn't the first time this has happened. The page you are accessing is in the US for gods sake. It seems like the internet has walled off islands on occasions. I have mirrored it: http://www.stuart.id.au/tc/hash-analysis http://www.lubemobile.com.au/tc/hash-analysis http://adsl-brisbane.lubemobile.com.au/tc/hash-analysis http://iexec-brisbane.lubemobile.com.au/tc/hash-analysis http://adsl2-sydney.lubemobile.com.au/tc/hash-analysis http://cable-meblourne.lubemobile.com.au/tc/hash-analysis http://adsl-perth.lubemobile.com.au/tc/hash-analysis One of these must work, (surely ?!?). All bar the first one may disappear within the next 24 hours due to cron jobs cleaning up. > The least squares is not bad - only issue is it missed the criteria > i had for looking at the number of buckets selected. I think if we had > no choice on changing the hash table, it would have been perfect. The source a couple of metrics is up on the web site. I find myself using the average lookup time over the least squares, even though I think on a theoretical level least squares is a better metric. This is because the average lookup time measures something "real". > Ok now, give it up Russell ; Yeah, I agree with the sentiment. I am tiring of this too. I have another patch I would like you to look at completely unrelated to u32, and definitely more important. The sticking point seems to be that you don't believe 2.4 can't run faster. It can, and it is in incredibly frustrating to me that I have not been able to put a coherent argument together to demonstrate it. Hopefully the analysis does that. Please look at it. Once I have managed to demonstrate to you that 2.4 can run faster I will accept your decision on the matter without a whimper - I promise. By the way, with the analysis I didn't go out of my way to find a dataset where 2.4 ran faster - it was just the second one I tried. There are pathological "fake" datasets that perform much worse than the one in the analysis, and presumably real ones too. - 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
Re: Results WAS(Re: [PATCH] TC: bug fixes to the "sample" clause
On Tue, 2006-21-03 at 09:35 +1000, Russell Stuart wrote: > Jeezz, that pisses me off. What is it with the bloody > internet? This isn't the first time this has happened. > The page you are accessing is in the US for gods sake. > It seems like the internet has walled off islands on > occasions. I have mirrored it: Thanks - I accessed it. [..] > By the way, with the analysis I didn't go out of my > way to find a dataset where 2.4 ran faster - it was > just the second one I tried. There are pathological > "fake" datasets that perform much worse than the one > in the analysis, and presumably real ones too. sorry Russell - that still doesnt cut it. When you design something like a route lookup algorithm, for example, you dont pick one over another based on a set of IP addresses you have. A worst case scenario is acceptable, always. An observation of "this is going to run on the edge/core of a network therefore i will optimize for that case" is also acceptable. Yours doesnt fit this. I havent run your test data but i am willing to bet (unenthusiastic to try for sure since we've spent too much time on this), the "better" results you are getting are due to biasing so that the "better" algorithm gets things in some buckets more than others i.e it has nothing to do with the hash selection. The environment changes and such results will change as well. Nothing is ever gonna save you from 25-75% of your buckets never ever being used in the case of 2.4; and at the expense of sounding like a broken record: i dont see anything the 2.4 algorithm brings of value other than in the case of 256 buckets with masks which ensure all 256 buckets get used - so as a performance bigot i equally dont value adding those extra computations; trust me if i was semi-convinced i would have supported the change. The impression i have is you are an energetic, resourceful person - lets move on (drop this) to that other thing you said you wanted to talk about. I could look at the way you have arranged your tables and offer opinion. 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
Re: Results WAS(Re: [PATCH] TC: bug fixes to the "sample" clause
Back to the original question... What should the iproute2 utilities contain? Does it have to have the utsname hack to work? - 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
Re: Results WAS(Re: [PATCH] TC: bug fixes to the "sample" clause
On Tue, 2006-03-21 at 09:57 -0500, jamal wrote: > I accessed them - unfortunately, though i am trying to, I dont > see anything outstanding that would justify any changes to the > hash. Lets just drop this. We can talk about other things if you want. If you still are not convinced, then I don't see that I can convince you. Fair enough. Yes - I would like to discuss other things. I will take me some days to prepare them so you will have a little peace and quiet (from me anyway) for a short while. I would like to take the opportunity to thank you for giving me such a fair hearing. You have been polite throughout, despite my persistence. And you have always responded quickly. - 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
Re: Results WAS(Re: [PATCH] TC: bug fixes to the "sample" clause
On Tue, 2006-03-21 at 14:39 -0800, Stephen Hemminger wrote: > Back to the original question... > > What should the iproute2 utilities contain? > > Does it have to have the utsname hack to work? Hi Stephen, I think the resolution was: - No to the utsname hack. Ergo the "tc" sample clause won't work on 2.4. Maybe "tc" using ustname to check the kernel version and print out a warning / error if "sample" is used on 2.4 is acceptable? I regard failing silently and producing incorrect results as a terrible thing to do to. I could produce another patch if this is OK. - Put the 2.6 hash algorithm in "tc". That is what my previous patch did. Jamal didn't like the patch description though. Perhaps he would prefer something along the lines of "Changed u32 hashing algorithm used by the 'sample clause' to the 2.6 kernel algorithm. Currently its uses the 2.4 algorithm, which computes the wrong result under some circumstances on 2.6 kernels. This means tc sample will no longer work on 2.4." - 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
Re: Results WAS(Re: [PATCH] TC: bug fixes to the "sample" clause
On Wed, 2006-22-03 at 09:01 +1000, Russell Stuart wrote: > On Tue, 2006-03-21 at 14:39 -0800, Stephen Hemminger wrote: > > Back to the original question... > > > > What should the iproute2 utilities contain? > > > > Does it have to have the utsname hack to work? > > Hi Stephen, > > I think the resolution was: > > - No to the utsname hack. Ergo the "tc" sample clause > won't work on 2.4. > This is what is what i was objecting to in your text description. sample works fine using current 2.6 hash in user space on a 2.4 kernel - as long as it is the well known usage (255 buckets, mask of 0xff). 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
