Rich Felker wrote:
On Fri, May 30, 2014 at 12:13:41PM +0100, Laurent Bercot wrote:
On 05/30/2014 10:16 AM, Bartosz Gołaszewski wrote:
I've checked the times just by looking up all the applets in a loop
and measuring the time using gettimeofday() - the results are: ~220
microseconds for bsearch and ~150 microseconds for hashtable on my
linux laptop. Is it significant? I think so. Is it noticeable?
Probably not. The idea came to me, when thinking about unifying the
hashtables used in busybox. I guess you're right and it isn't really
worth the size increase.
I think it would definitely be a worthwhile improvement if all busybox
is doing was looking up the applets in a loop. ;)
A more realistic test, however, would be to fork+exec a trivial applet
(true, for instance) in a loop, and measure the times with bsearch vs.
with the hash table. And I'm certain you'll find that the difference
becomes quite insignificant.
If there is a desire to change the way applet lookup is done, I would
suggest trying to make it optimal in both size and performance. 150µs
is not impressive at all. A perfect hash constructed at build time for
the list of busybox applet-name strings should make it possible to do
the applet lookup in ~1µs with trivial code/table size (all constant
in .text).
The original number was 220µs for "looking up *all* the applets in a
loop and measuring the time". So this is the time for an unspecified
number of applets (maybe allyesconfig) on an unspecified machine. So if
we assume that at least 50 applets were defined, the time for one applet
is 4µs or less.
I just built busybox with 373 applets, the time to call the lookup
1000000 times for APPLET_NAME(0) is 100ms on an AMD 4GHz CPU. An own
binary search implementation saves a few ms, probably because the
comparison function is inline which saves a call. It also adds a few
bytes. I choose APPLET_NAME(0) because it is the worst case for the
binary search. The best case is APPLET_NAME(NUM_APPLETS/2), which only
needs 18ms for 1000000 calls, or 13ms with own binary search.
As busybox has a focus on size and the difference is small I think it
doesn't make sense to change anything here.
_______________________________________________
busybox mailing list
busybox@busybox.net
http://lists.busybox.net/mailman/listinfo/busybox
