Does this provided a noticeable performance increase? Do you have benchmarks?
J On May 29, 2014 7:17 AM, "Bartosz Golaszewski" <[email protected]> wrote: > Hi! > > Busybox uses bsearch() to locate the applet's main function in > find_applet_by_name(). Running 'make defconfig' results in 355 applets > being built and this in turn results in 8-9 calls to strcmp() on average > per busybox execution. > > Maybe we should switch to using a simple static hashtable? The following > patch is a simple & dirty proof of concept to show what I mean. It modifies > applet_tables.c to generate a static hashtable containing indicies of > fields > in applet_nameofs. I used a simple and fast hash function taken from > Robert Jenkins. > > With this patch, on each execution and after the hash computation, the > number of calls to strcmp() has been limited to four at most, and mostly > it's just one or two. There are no calls to applet_name_compare() too. > > The patch results in bigger code, but there's room for improvement as > we could probably get rid of some of the arrays generated by applet_tables > and unify the hashtables used in busybox applets. > > If there's any interest, I can prepare a better, more memory-wise optimized > version. > > Best regards, > Bartosz Golaszewski > > --- > applets/applet_tables.c | 58 > ++++++++++++++++++++++++++++++++++++++++++++++++- > libbb/appletlib.c | 45 ++++++++++++++++++++++++++++++++------ > 2 files changed, 95 insertions(+), 8 deletions(-) > > diff --git a/applets/applet_tables.c b/applets/applet_tables.c > index 94b974e..9656b5c 100644 > --- a/applets/applet_tables.c > +++ b/applets/applet_tables.c > @@ -14,6 +14,7 @@ > #include <string.h> > #include <stdio.h> > #include <unistd.h> > +#include <stdint.h> > > #undef ARRAY_SIZE > #define ARRAY_SIZE(x) ((unsigned)(sizeof(x) / sizeof((x)[0]))) > @@ -42,6 +43,26 @@ enum { NUM_APPLETS = ARRAY_SIZE(applets) }; > > static int offset[NUM_APPLETS]; > > +#define MAX_BUCKET_SIZE 16 > +static int applet_hashtable[NUM_APPLETS][16]; > + > +static unsigned jenkins_hash(const char *key, size_t len) > +{ > + unsigned hash, i; > + > + for(hash = i = 0; i < len; ++i) { > + hash += key[i]; > + hash += (hash << 10); > + hash ^= (hash >> 6); > + } > + > + hash += (hash << 3); > + hash ^= (hash >> 11); > + hash += (hash << 15); > + > + return hash; > +} > + > static int cmp_name(const void *a, const void *b) > { > const struct bb_applet *aa = a; > @@ -51,7 +72,7 @@ static int cmp_name(const void *a, const void *b) > > int main(int argc, char **argv) > { > - int i; > + int i, j; > int ofs; > // unsigned MAX_APPLET_NAME_LEN = 1; > > @@ -129,6 +150,41 @@ int main(int argc, char **argv) > } > printf("};\n"); > #endif > + > + // Initialize local hashtable > + for (i = 0; i < NUM_APPLETS; i++) { > + for (j = 0; j < MAX_BUCKET_SIZE; j++) > + applet_hashtable[i][j] = -1; > + } > + > + // For each applet - place it in appropriate bucket > + for (i = 0; i < NUM_APPLETS; i++) { > + unsigned ind = jenkins_hash(applets[i].name, > + strlen(applets[i].name)) % > NUM_APPLETS; > + > + for (j = 0; j < MAX_BUCKET_SIZE; j++) { > + if (applet_hashtable[ind][j] < 0) { > + applet_hashtable[ind][j] = i; > + break; > + } > + } > + } > + > + // Create a static array for each bucket > + for (i = 0; i < NUM_APPLETS; i++) { > + printf("const int16_t bucket%d[] = { ", i); > + for (j = 0; applet_hashtable[i][j] >= 0; j++) { > + printf("%d, ", applet_hashtable[i][j]); > + } > + printf(" -1 };\n"); > + } > + > + // Create a static array of pointers to the buckets > + printf("\nconst int16_t *applet_hashtab[] = {\n"); > + for (i = 0; i < NUM_APPLETS; i++) > + printf("\tbucket%d,\n", i); > + printf("};\n"); > + > //printf("#endif /* SKIP_definitions */\n"); > // printf("\n"); > // printf("#define MAX_APPLET_NAME_LEN %u\n", MAX_APPLET_NAME_LEN); > diff --git a/libbb/appletlib.c b/libbb/appletlib.c > index f7c416e..6be536d 100644 > --- a/libbb/appletlib.c > +++ b/libbb/appletlib.c > @@ -52,7 +52,6 @@ > > #include "usage_compressed.h" > > - > #if ENABLE_SHOW_USAGE && !ENABLE_FEATURE_COMPRESS_USAGE > static const char usage_messages[] ALIGN1 = UNPACKED_USAGE; > #else > @@ -140,23 +139,55 @@ void FAST_FUNC bb_show_usage(void) > } > > #if NUM_APPLETS > 8 > -static int applet_name_compare(const void *name, const void *idx) > +static unsigned jenkins_hash(const char *key, size_t len) > { > - int i = (int)(ptrdiff_t)idx - 1; > - return strcmp(name, APPLET_NAME(i)); > + unsigned hash, i; > + > + for(hash = i = 0; i < len; ++i) { > + hash += key[i]; > + hash += (hash << 10); > + hash ^= (hash >> 6); > + } > + > + hash += (hash << 3); > + hash ^= (hash >> 11); > + hash += (hash << 15); > + > + return hash; > } > + > +//static int applet_name_compare(const void *name, const void *idx) > +//{ > +// int i = (int)(ptrdiff_t)idx - 1; > +// return strcmp(name, APPLET_NAME(i)); > +//} > #endif > int FAST_FUNC find_applet_by_name(const char *name) > { > #if NUM_APPLETS > 8 > /* Do a binary search to find the applet entry given the name. */ > - const char *p; > - p = bsearch(name, (void*)(ptrdiff_t)1, ARRAY_SIZE(applet_main), 1, > applet_name_compare); > + //const char *p; > + //p = bsearch(name, (void*)(ptrdiff_t)1, ARRAY_SIZE(applet_main), > 1, applet_name_compare); > + > + unsigned ind; > + int ret = -1, i = 0; > + > + ind = jenkins_hash(name, strlen(name)) % NUM_APPLETS; > + while (applet_hashtab[ind][i] != -1) { > + if (strcmp(name, APPLET_NAME(applet_hashtab[ind][i])) == > 0) { > + ret = applet_hashtab[ind][i]; > + break; > + } > + ++i; > + } > + > + return ret; > + > /* > * if (!p) return -1; > * ^^^^^^^^^^^^^^^^^^ the code below will do this if p == NULL :) > */ > - return (int)(ptrdiff_t)p - 1; > + //return (int)(ptrdiff_t)p - 1; > #else > /* A version which does not pull in bsearch */ > int i = 0; > -- > 1.9.1 > > _______________________________________________ > busybox mailing list > [email protected] > http://lists.busybox.net/mailman/listinfo/busybox >
_______________________________________________ busybox mailing list [email protected] http://lists.busybox.net/mailman/listinfo/busybox
