[PATCH] libbb: code shrink and speed up find_applet_by_name()
Ron Yorston
rmy at pobox.com
Fri Jan 29 13:22:48 UTC 2021
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
More information about the busybox
mailing list