On Fri, May 30, 2014 at 08:19:29PM +0200, walter harms wrote: > > > Am 30.05.2014 20:07, schrieb Rich Felker: > > 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. > > > > The lowest time I've ever seen for exec (not even counting fork; > > measured from immediately before the exec syscall to entry into main) > > is over 200µs, and can easily exceed 1ms with dynamic linking. So even > > if the program did nothing but applet lookup and exit, I think we'd be > > looking at a performance increase of ~30% at best. > > > > Realistically, as soon as you throw in some actual work and other > > syscalls that actually do something, I suspect the difference to be > > less than 5%. > > > > 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). > > > > We should keep in mind that busybox is also about size reduction, so we need > a more flexible code that can be used on other places as well (e.g. shell). > From my experience i would not expect to much most times the hogs are > somewhere > else. Glibc has some hash functions (no idea, if POSIX or GNU or ...) > using them should not make a notable size difference.
I'm guessing you mean hcreate/hsearch/hdestroy in <search.h>, which are POSIX. I do note that there are a few limitations therein: -uses malloc -you must correctly estimate the size of the table at the start; it cannot grow, and you cannot remove entries. I'd think this would not be ideal for the startup code. HTH, Isaac Dunham _______________________________________________ busybox mailing list [email protected] http://lists.busybox.net/mailman/listinfo/busybox
