Re: [PATCH] module: Use binary search in lookup_symbol()

[Tim Bird <tim.bird@am.sony.com>]

On 05/18/2011 12:54 AM, Christoph Hellwig wrote:
> On Tue, May 17, 2011 at 04:33:07PM -0700, Tim Bird wrote:
>> That said, I can answer Greg's question.  This is to speed up
>> the symbol resolution on module loading.  The last numbers I
>> saw showed a reduction of about 15-20% for the module load
>> time, for large-ish modules.  Of course this is highly dependent
>> on the size of the modules, what they do at load time, and how many
>> symbols are looked up to link them into the kernel.
> 
> How large are these very large modules, and what are good examples for
> that?

usbcore seems to be a large-ish module whose
load time is improved by this.  More details follow:

I don't know the exact modules, but Alan Jenkins reported a .3
second reduction in overall boot time, on a EEE PC, presumably
running a stock Linux distribution, and loading 41 modules.

See http://lkml.org/lkml/2009/11/3/93

Carmelo Amoroso reported some good performance gains
in this presentation:
http://elinux.org/images/1/18/C_AMOROSO_Fast_lkm_loader_ELC-E_2009.pdf
(See slide 22).

He doesn't report the overall time savings, and
he was using a different method (hash tables as opposed to
binary search), but I believe the results are comparable
to what the binary search enhancement provides.

The biggest offenders in his testing were usbcore,
ehci_hcd and ohci_hcd.

> And why do people overly care for the load time?

To reduce overall boot time.
 -- Tim

=============================
Tim Bird
Architecture Group Chair, CE Workgroup of the Linux Foundation
Senior Staff Engineer, Sony Network Entertainment
=============================