[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