[PATCH v3] applet_tables: save space by removing applet name offsets

Denys Vlasenko vda.linux at googlemail.com
Mon Mar 28 20:42:14 UTC 2016


On Mon, Mar 28, 2016 at 7:43 PM, Ron Yorston <rmy at pobox.com> wrote:
> The array applet_nameofs consumes two bytes per applet.  It encodes
>
>    nofork/noexec flags
>    suid flags
>    the offset of the applet name in the applet_name string
>
> Change the applet_table build tool to store the flags in two separate
> arrays (applet_flags and applet_suid) and remove the applet_nameofs
> array.  The name offsets are no longer stored.
>
> This requires changes to the macros APPLET_IS_NOFORK, APPLET_IS_NOEXEC
> and APPLET_SUID.  The APPLET_NAME macro is replaced by a function,
> get_applet_name, which uses a linear search though the applet_name
> string to find the applet name given its number.
>
> Speed up get_applet_name by:
>
>    storing the last applet number/name looked up;
>    storing the offset to the name of the applet in the middle of the
>    table.
>
> As well as starting the search from the beginning of the applet name
> string we can instead use the position of the last applet found or the
> middle applet if that reduces the number of iterations required.
>
> There are three cases where get_applet_name is used:
>
> 1) In install_links applets are processed in numerical order.  Every
>    time get_applet_name is called it is to search for the applet
>    number following the last stored value;
>
> 2) In find_applet_by_name a binary search is performed for the required
>    name.  With the default configuration this usually results in eight
>    calls to get_applet_name.  The first call always looks for the applet
>    in the middle of the table.  Executing find_applet_by_name for all
>    applets in the default configuration required a total of 2,918,246
>    iterations of the search loop without optimisation, 801,370 with.

find_applet_by_name() is the main use of applet name offset table.
It is used every time any applet is called. You optimize get_applet_name(i)
but find_applet_by_name() will still perform a binary search,
which is kinda pointless when the table is gone (can't do a binary search!):
with all optimizations in get_applet_name(i) you still are worse
than doing a simple linear search.

Convert find_applet_by_name() to do a linear search.


More information about the busybox mailing list