[prev in list] [next in list] [prev in thread] [next in thread] 

List:       busybox
Subject:    Re: [PATCH v3] applet_tables: save space by removing applet name offsets
From:       Denys Vlasenko <vda.linux () googlemail ! com>
Date:       2016-03-29 12:41:23
Message-ID: CAK1hOcMLjHOjNMtuRyNcR7X6BFzZB5LjxQXYU_3R7HEeGYAdGw () mail ! gmail ! com
[Download RAW message or body]

On Tue, Mar 29, 2016 at 10:32 AM, Ron Yorston <rmy@pobox.com> wrote:
> Denys Vlasenko wrote:
>>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.
>
> Good point.  The number of iterations isn't the only cost, though.
> The binary search will only perform eight calls to strcmp() whereas the
> naive linear search requires NUM_APPLETS/2 calls on average.

It will probably run faster with open-coded search for applet name.
In this case, overhead of repeated function calls to strcmp
is likely significant.
_______________________________________________
busybox mailing list
busybox@busybox.net
http://lists.busybox.net/mailman/listinfo/busybox
[prev in list] [next in list] [prev in thread] [next in thread]