[Cake] [PATCH net-next] sch_cake: constify inverse square root cache

[Dave Taht]

although REC_INV_SQRT_CACHE can just be pulled from the const size rather
than a define...

Acked-By: Dave Taht <dave.taht at gmail.com>

On Wed, Sep 4, 2024 at 3:05 AM Toke Høiland-Jørgensen <toke at redhat.com>
wrote:

> From: Dave Taht <dave.taht at gmail.com>
>
> sch_cake uses a cache of the first 16 values of the inverse square root
> calculation for the Cobalt AQM to save some cycles on the fast path.
> This cache is populated when the qdisc is first loaded, but there's
> really no reason why it can't just be pre-populated. So change it to be
> pre-populated with constants, which also makes it possible to constify
> it.
>
> This gives a modest space saving for the module (not counting debug data):
> .text:  -224 bytes
> .rodata: +80 bytes
> .bss:    -64 bytes
> Total:  -192 bytes
>
> Signed-off-by: Dave Taht <dave.taht at gmail.com>
> [ fixed up comment, rewrote commit message ]
> Signed-off-by: Toke Høiland-Jørgensen <toke at redhat.com>
> ---
>  net/sched/sch_cake.c | 53 +++++++++++++++-----------------------------
>  1 file changed, 18 insertions(+), 35 deletions(-)
>
> diff --git a/net/sched/sch_cake.c b/net/sched/sch_cake.c
> index 9602dafe32e6..a51c43bde0de 100644
> --- a/net/sched/sch_cake.c
> +++ b/net/sched/sch_cake.c
> @@ -361,8 +361,24 @@ static const u8 besteffort[] = {
>  static const u8 normal_order[] = {0, 1, 2, 3, 4, 5, 6, 7};
>  static const u8 bulk_order[] = {1, 0, 2, 3};
>
> +/* There is a big difference in timing between the accurate values placed
> in the
> + * cache and the approximations given by a single Newton step for small
> count
> + * values, particularly when stepping from count 1 to 2 or vice versa.
> Hence,
> + * these values are calculated using eight Newton steps, using the
> implementation
> + * below. Above 16, a single Newton step gives sufficient accuracy in
> either
> + * direction, given the precision stored.
> + *
> + * The magnitude of the error when stepping up to count 2 is such as to
> give
> + * the value that *should* have been produced at count 4.
> + */
> +
>  #define REC_INV_SQRT_CACHE (16)
> -static u32 cobalt_rec_inv_sqrt_cache[REC_INV_SQRT_CACHE] = {0};
> +static const u32 inv_sqrt_cache[REC_INV_SQRT_CACHE] = {
> +               ~0,         ~0, 3037000500, 2479700525,
> +       2147483647, 1920767767, 1753413056, 1623345051,
> +       1518500250, 1431655765, 1358187914, 1294981364,
> +       1239850263, 1191209601, 1147878294, 1108955788
> +};
>
>  /* http://en.wikipedia.org/wiki/Methods_of_computing_square_roots
>   * new_invsqrt = (invsqrt / 2) * (3 - count * invsqrt^2)
> @@ -388,47 +404,14 @@ static void cobalt_newton_step(struct cobalt_vars
> *vars)
>  static void cobalt_invsqrt(struct cobalt_vars *vars)
>  {
>         if (vars->count < REC_INV_SQRT_CACHE)
> -               vars->rec_inv_sqrt =
> cobalt_rec_inv_sqrt_cache[vars->count];
> +               vars->rec_inv_sqrt = inv_sqrt_cache[vars->count];
>         else
>                 cobalt_newton_step(vars);
>  }
>
> -/* There is a big difference in timing between the accurate values placed
> in
> - * the cache and the approximations given by a single Newton step for
> small
> - * count values, particularly when stepping from count 1 to 2 or vice
> versa.
> - * Above 16, a single Newton step gives sufficient accuracy in either
> - * direction, given the precision stored.
> - *
> - * The magnitude of the error when stepping up to count 2 is such as to
> give
> - * the value that *should* have been produced at count 4.
> - */
> -
> -static void cobalt_cache_init(void)
> -{
> -       struct cobalt_vars v;
> -
> -       memset(&v, 0, sizeof(v));
> -       v.rec_inv_sqrt = ~0U;
> -       cobalt_rec_inv_sqrt_cache[0] = v.rec_inv_sqrt;
> -
> -       for (v.count = 1; v.count < REC_INV_SQRT_CACHE; v.count++) {
> -               cobalt_newton_step(&v);
> -               cobalt_newton_step(&v);
> -               cobalt_newton_step(&v);
> -               cobalt_newton_step(&v);
> -
> -               cobalt_rec_inv_sqrt_cache[v.count] = v.rec_inv_sqrt;
> -       }
> -}
> -
>  static void cobalt_vars_init(struct cobalt_vars *vars)
>  {
>         memset(vars, 0, sizeof(*vars));
> -
> -       if (!cobalt_rec_inv_sqrt_cache[0]) {
> -               cobalt_cache_init();
> -               cobalt_rec_inv_sqrt_cache[0] = ~0;
> -       }
>  }
>
>  /* CoDel control_law is t + interval/sqrt(count)
> --
> 2.46.0
>
>

-- 
Artists/Musician Campout Aug 9-11
https://www.eventbrite.com/e/healing-arts-event-tickets-928910826287
Dave Täht CSO, LibreQos
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.bufferbloat.net/pipermail/cake/attachments/20240904/b2d13c33/attachment-0001.html>