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
