[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