Proposition: use a hashtable instead of bsearch to locate applets

Laurent Bercot ska-dietlibc at skarnet.org
Fri May 30 11:13:41 UTC 2014


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.

-- 
  Laurent


More information about the busybox mailing list