[PATCH] libbb: code shrink and speed up find_applet_by_name()

Denys Vlasenko vda.linux at googlemail.com
Tue Feb 2 13:17:27 UTC 2021


Applied, thanks!

On Fri, Jan 29, 2021 at 2:23 PM Ron Yorston <rmy at pobox.com> wrote:
>
> find_applet_by_name() determines the appropriate range of applet
> indices to check for the given name and performs a linear search in
> applet_names[].
>
> Revise the code so the index of the upper bound of the range, 'max',
> isn't calculated.  Instead check the value of the first non-matching
> character to see if we've reached the end of the range.
>
> This new code speeds up the time to find a valid applet name by 6%
> and halves the time to detect that a given name is invalid.  The
> average time to detect an invalid name is now the same as for a valid
> one.
>
> function                                             old     new   delta
> find_applet_by_name                                  155     133     -22
> ------------------------------------------------------------------------------
> (add/remove: 0/0 grow/shrink: 0/1 up/down: 0/-22)             Total: -22 bytes
>
> Signed-off-by: Ron Yorston <rmy at pobox.com>
> ---
>  libbb/appletlib.c | 40 +++++++++++++++++-----------------------
>  1 file changed, 17 insertions(+), 23 deletions(-)
>
> diff --git a/libbb/appletlib.c b/libbb/appletlib.c
> index 5f59f1273..2e61659fb 100644
> --- a/libbb/appletlib.c
> +++ b/libbb/appletlib.c
> @@ -176,7 +176,7 @@ void FAST_FUNC bb_show_usage(void)
>
>  int FAST_FUNC find_applet_by_name(const char *name)
>  {
> -       unsigned i, max;
> +       unsigned i;
>         int j;
>         const char *p;
>
> @@ -200,24 +200,21 @@ int FAST_FUNC find_applet_by_name(const char *name)
>  #endif
>
>         p = applet_names;
> -       i = 0;
>  #if KNOWN_APPNAME_OFFSETS <= 0
> -       max = NUM_APPLETS;
> +       i = 0;
>  #else
> -       max = NUM_APPLETS * KNOWN_APPNAME_OFFSETS;
> +       i = NUM_APPLETS * (KNOWN_APPNAME_OFFSETS - 1);
>         for (j = ARRAY_SIZE(applet_nameofs)-1; j >= 0; j--) {
>                 const char *pp = applet_names + applet_nameofs[j];
>                 if (strcmp(name, pp) >= 0) {
>                         //bb_error_msg("name:'%s' >= pp:'%s'", name, pp);
>                         p = pp;
> -                       i = max - NUM_APPLETS;
>                         break;
>                 }
> -               max -= NUM_APPLETS;
> +               i -= NUM_APPLETS;
>         }
> -       max /= (unsigned)KNOWN_APPNAME_OFFSETS;
>         i /= (unsigned)KNOWN_APPNAME_OFFSETS;
> -       //bb_error_msg("name:'%s' starting from:'%s' i:%u max:%u", name, p, i, max);
> +       //bb_error_msg("name:'%s' starting from:'%s' i:%u", name, p, i);
>  #endif
>
>         /* Open-coded linear search without strcmp/strlen calls for speed */
> @@ -276,25 +273,22 @@ int FAST_FUNC find_applet_by_name(const char *name)
>         }
>         return -1;
>  #else
> -       while (i < max) {
> -               char ch;
> -               j = 0;
> -               /* Do we see "name\0" in applet_names[p] position? */
> -               while ((ch = *p) == name[j]) {
> -                       if (ch == '\0') {
> +       while (*p) {
> +               /* Do we see "name\0" at current position in applet_names? */
> +               for (j = 0; *p == name[j]; ++j) {
> +                       if (*p++ == '\0') {
>                                 //bb_error_msg("found:'%s' i:%u", name, i);
>                                 return i; /* yes */
>                         }
> -                       p++;
> -                       j++;
>                 }
> -               /* No.
> -                * p => 1st non-matching char in applet_names[],
> -                * skip to and including NUL.
> -                */
> -               while (ch != '\0')
> -                       ch = *++p;
> -               p++;
> +               /* No.  Have we gone too far, alphabetically? */
> +               if (*p > name[j]) {
> +                       //bb_error_msg("break:'%s' i:%u", name, i);
> +                       break;
> +               }
> +               /* No.  Move to the start of the next applet name. */
> +               while (*p++ != '\0')
> +                       ;
>                 i++;
>         }
>         return -1;
> --
> 2.29.2
>
> _______________________________________________
> busybox mailing list
> busybox at busybox.net
> http://lists.busybox.net/mailman/listinfo/busybox


More information about the busybox mailing list