On Tue, Aug 18, 2015 at 4:26 PM, Andrew Mcgregor <[email protected]> wrote: > Memory access on modern CPUs is astonishingly expensive as well, so the > pendulum is well over on the 'just calculate it' side; only in very low-end > embedded devices would there be any benefit to a lookup table (for > perspective, a Raspberry Pi probably loses from the lookup table, and that's > a $35 device; the common MIPS chips found in home routers are very likely > about even on the two approaches, although I admit I have not benchmarked > them). The reasons to do tables these days are 1) if the calculation would > touch a lot more memory (for example, Minstrel rate table construction) or > 2) if it is very hard to do accurately in integer arithmetic (Jonathan's > case here).
Accuracy here means two things, btw. One is the right number obtained... the other is that the newton sqrt estimation method does not run well in reverse. I can certainly see compiling the cache out (and doing more serious profiling of cake in the near future, in general) - but at the moment we are just making sure the code is as correct, and as big an advance on the current state of the art (3 tiers of htb + fq_codel in the sqm-scripts) as possible. There will probably be many optimization opportunities - some of which, like hashing and locking improvements in upcoming linux-en are pretty important also. Jonathon has got a technical overview of cake in a pretty good state now, that document is at: http://www.bufferbloat.net/projects/codel/wiki/CakeTechnical > On 11 August 2015 at 23:05, Jeff Weeks <[email protected]> wrote: >> >> Indeed, the microsec granularity means the lookup table would be quite >> large, or would need to use a reduced index into a smaller table. >> After looking at modern cycle counts for integer multiply, I'm realizing >> that they're not nearly as expensive as I remember them to be, so the Linux >> implementation's approach is likely more efficient. >> >> --Jeff >> ________________________________________ >> From: Agarwal, Anil [[email protected]] >> Sent: Monday, August 10, 2015 2:38 PM >> To: Jeff Weeks; [email protected] >> Subject: RE: avoiding the sqrt >> >> Jeff, >> >> Did you mean - >> pre-calculate a set of interval/sqrt(count) for some range of count -- >> probably (1..interval^2), >> and for any count > interval^2, the next interval can just be set to >> t+1 >> >> Also, interval is generally kept in microseconds, hence a nominal value >> for interval is 100000. >> >> The current Codel Linux implementation of 1/sqrt(count) uses 4 >> multiplications. >> >> Anil >> >> -----Original Message----- >> From: aqm [mailto:[email protected]] On Behalf Of Jeff Weeks >> Sent: Monday, August 10, 2015 12:18 PM >> To: [email protected] >> Subject: [aqm] avoiding the sqrt >> >> The CoDel control_law is defined as 't + interval/sqrt(count)' >> >> The sample implementation >> (https://urldefense.proofpoint.com/v2/url?u=http-3A__queue.acm.org_appendices_codel.html&d=BQICAg&c=jcv3orpCsv7C4ly8-ubDob57ycZ4jvhoYZNDBA06fPk&r=FyvaklKYrHaSCPjbBTdviWIW9uSbnxdNSheSGz1Jvq4&m=Mwm2-08h6DG8dG8A8i_FAQ9gIL67_jeiZA_pVQpEnIU&s=dMb61gcX82gBDxDv3nIAN4_lJma52tJT57lEdcXrVko&e= >> ) suggests that sqrt(count) can be calculated using only integer >> multiplication, but I'm wondering if it even needs to be calculated. >> >> Would it not be more efficient to pre-calculate a set of 1/sqrt(count) for >> some range -- probably (1..interval), and for any count > interval, the >> next interval can just be set to t+1. >> >> Is there any reason to not use this approach (assuming sufficient memory >> exists, of course)? >> >> --Jeff >> >> ________________________________ >> /dev/jeff_weeks.x2936 >> Sandvine Incorporated >> >> _______________________________________________ >> aqm mailing list >> [email protected] >> >> https://urldefense.proofpoint.com/v2/url?u=https-3A__www.ietf.org_mailman_listinfo_aqm&d=BQICAg&c=jcv3orpCsv7C4ly8-ubDob57ycZ4jvhoYZNDBA06fPk&r=FyvaklKYrHaSCPjbBTdviWIW9uSbnxdNSheSGz1Jvq4&m=Mwm2-08h6DG8dG8A8i_FAQ9gIL67_jeiZA_pVQpEnIU&s=guSznYIkwKsTZpoAOLCaLdhlKa4GUMNrO7mu4sv3nMM&e= >> >> _______________________________________________ >> aqm mailing list >> [email protected] >> https://www.ietf.org/mailman/listinfo/aqm > > > > > -- > Andrew McGregor | SRE | [email protected] | +61 4 1071 2221 > > _______________________________________________ > aqm mailing list > [email protected] > https://www.ietf.org/mailman/listinfo/aqm > -- Dave Täht worldwide bufferbloat report: http://www.dslreports.com/speedtest/results/bufferbloat And: What will it take to vastly improve wifi for everyone? https://plus.google.com/u/0/explore/makewififast _______________________________________________ aqm mailing list [email protected] https://www.ietf.org/mailman/listinfo/aqm
