Proposition: use a hashtable instead of bsearch to locate applets

[Denys Vlasenko]

On Thursday 29 May 2014 13:18, Bartosz Golaszewski 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,

+2944 bytes in my test.

> 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.

Yes, this must not result in such significant growth.