<div dir="ltr">although REC_INV_SQRT_CACHE can just be pulled from the const size rather than a define...<div><br></div><div>Acked-By: Dave Taht <<a href="mailto:dave.taht@gmail.com">dave.taht@gmail.com</a>></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, Sep 4, 2024 at 3:05 AM Toke Høiland-Jørgensen <<a href="mailto:toke@redhat.com">toke@redhat.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">From: Dave Taht <<a href="mailto:dave.taht@gmail.com" target="_blank">dave.taht@gmail.com</a>><br>
<br>
sch_cake uses a cache of the first 16 values of the inverse square root<br>
calculation for the Cobalt AQM to save some cycles on the fast path.<br>
This cache is populated when the qdisc is first loaded, but there's<br>
really no reason why it can't just be pre-populated. So change it to be<br>
pre-populated with constants, which also makes it possible to constify<br>
it.<br>
<br>
This gives a modest space saving for the module (not counting debug data):<br>
.text: -224 bytes<br>
.rodata: +80 bytes<br>
.bss: -64 bytes<br>
Total: -192 bytes<br>
<br>
Signed-off-by: Dave Taht <<a href="mailto:dave.taht@gmail.com" target="_blank">dave.taht@gmail.com</a>><br>
[ fixed up comment, rewrote commit message ]<br>
Signed-off-by: Toke Høiland-Jørgensen <<a href="mailto:toke@redhat.com" target="_blank">toke@redhat.com</a>><br>
---<br>
net/sched/sch_cake.c | 53 +++++++++++++++-----------------------------<br>
1 file changed, 18 insertions(+), 35 deletions(-)<br>
<br>
diff --git a/net/sched/sch_cake.c b/net/sched/sch_cake.c<br>
index 9602dafe32e6..a51c43bde0de 100644<br>
--- a/net/sched/sch_cake.c<br>
+++ b/net/sched/sch_cake.c<br>
@@ -361,8 +361,24 @@ static const u8 besteffort[] = {<br>
static const u8 normal_order[] = {0, 1, 2, 3, 4, 5, 6, 7};<br>
static const u8 bulk_order[] = {1, 0, 2, 3};<br>
<br>
+/* There is a big difference in timing between the accurate values placed in the<br>
+ * cache and the approximations given by a single Newton step for small count<br>
+ * values, particularly when stepping from count 1 to 2 or vice versa. Hence,<br>
+ * these values are calculated using eight Newton steps, using the implementation<br>
+ * below. Above 16, a single Newton step gives sufficient accuracy in either<br>
+ * direction, given the precision stored.<br>
+ *<br>
+ * The magnitude of the error when stepping up to count 2 is such as to give<br>
+ * the value that *should* have been produced at count 4.<br>
+ */<br>
+<br>
#define REC_INV_SQRT_CACHE (16)<br>
-static u32 cobalt_rec_inv_sqrt_cache[REC_INV_SQRT_CACHE] = {0};<br>
+static const u32 inv_sqrt_cache[REC_INV_SQRT_CACHE] = {<br>
+ ~0, ~0, 3037000500, 2479700525,<br>
+ 2147483647, 1920767767, 1753413056, 1623345051,<br>
+ 1518500250, 1431655765, 1358187914, 1294981364,<br>
+ 1239850263, 1191209601, 1147878294, 1108955788<br>
+};<br>
<br>
/* <a href="http://en.wikipedia.org/wiki/Methods_of_computing_square_roots" rel="noreferrer" target="_blank">http://en.wikipedia.org/wiki/Methods_of_computing_square_roots</a><br>
* new_invsqrt = (invsqrt / 2) * (3 - count * invsqrt^2)<br>
@@ -388,47 +404,14 @@ static void cobalt_newton_step(struct cobalt_vars *vars)<br>
static void cobalt_invsqrt(struct cobalt_vars *vars)<br>
{<br>
if (vars->count < REC_INV_SQRT_CACHE)<br>
- vars->rec_inv_sqrt = cobalt_rec_inv_sqrt_cache[vars->count];<br>
+ vars->rec_inv_sqrt = inv_sqrt_cache[vars->count];<br>
else<br>
cobalt_newton_step(vars);<br>
}<br>
<br>
-/* There is a big difference in timing between the accurate values placed in<br>
- * the cache and the approximations given by a single Newton step for small<br>
- * count values, particularly when stepping from count 1 to 2 or vice versa.<br>
- * Above 16, a single Newton step gives sufficient accuracy in either<br>
- * direction, given the precision stored.<br>
- *<br>
- * The magnitude of the error when stepping up to count 2 is such as to give<br>
- * the value that *should* have been produced at count 4.<br>
- */<br>
-<br>
-static void cobalt_cache_init(void)<br>
-{<br>
- struct cobalt_vars v;<br>
-<br>
- memset(&v, 0, sizeof(v));<br>
- v.rec_inv_sqrt = ~0U;<br>
- cobalt_rec_inv_sqrt_cache[0] = v.rec_inv_sqrt;<br>
-<br>
- for (v.count = 1; v.count < REC_INV_SQRT_CACHE; v.count++) {<br>
- cobalt_newton_step(&v);<br>
- cobalt_newton_step(&v);<br>
- cobalt_newton_step(&v);<br>
- cobalt_newton_step(&v);<br>
-<br>
- cobalt_rec_inv_sqrt_cache[v.count] = v.rec_inv_sqrt;<br>
- }<br>
-}<br>
-<br>
static void cobalt_vars_init(struct cobalt_vars *vars)<br>
{<br>
memset(vars, 0, sizeof(*vars));<br>
-<br>
- if (!cobalt_rec_inv_sqrt_cache[0]) {<br>
- cobalt_cache_init();<br>
- cobalt_rec_inv_sqrt_cache[0] = ~0;<br>
- }<br>
}<br>
<br>
/* CoDel control_law is t + interval/sqrt(count)<br>
-- <br>
2.46.0<br>
<br>
</blockquote></div><br clear="all"><div><br></div><span class="gmail_signature_prefix">-- </span><br><div dir="ltr" class="gmail_signature"><div dir="ltr"><div>Artists/Musician Campout Aug 9-11</div><div><a href="https://www.eventbrite.com/e/healing-arts-event-tickets-928910826287" target="_blank">https://www.eventbrite.com/e/healing-arts-event-tickets-928910826287</a><br></div><div>Dave Täht CSO, LibreQos<br></div></div></div>