Re: module: Speed up symbol resolution during module loading

Re: module: Speed up symbol resolution during module loading

[Alan Jenkins]

[CC to lkml fixed :-/]

Rusty Russell wrote:
> On Tue, 22 Sep 2009 10:58:28 pm Alan Jenkins wrote:
>   
>> The following series applies against v2.6.31. It sorts the tables of builtin
>> symbols, so the module loader can resolve them using a binary search.
>>
>> The kbuild changes to achieve this are less scary than I expected.  I'm
>> optimistic that they can be accepted without radical alteration :-).
>>
>> Quoting from the last patch in this series:
>>
>> "On my EeePC 701, coldplug is mainly cpu bound and takes 1.5 seconds
>> during boot. perf showed this change eliminated 20% of cpu cycles during
>> coldplug, saving 0.3 seconds of real time.
>>     
>
> Hi Alan,
>
>    This seems useful, but wouldn't it be simpler to just sort at boot time?
> The same could be done for modules, possibly reducing code.
>
> Alternately, there's a standard way of hashing ELF symbols, but I'm not sure
> we can convince the linker to generate it for vmlinux (I haven't looked
> though).
>
> Thanks!
> Rusty.
>   

I'm concerned that people would object to the extra overhead at boot
time.  I've hacked up a prototype to sort at boot time and it takes 7ms
on the same hardware.  That's just under than the average time saved
loading one of my modules.  But the comparison is dodgy because it
doesn't include side-effects (on cache) for the sort.  The break-even
point will depend on the specific modules used.

That 7ms will be pure overhead in some cases - i.e. if your config is
"localyesconfig" (build in all currently used modules), but you keep
modules enabled to allow some flexibility.  I'm not happy about that myself.

Hash tables have a similar disadvantage.  They would add more
unswappable pages, in order to optimise a function which is only
significant at boot time.  Binary search already brings symbol
resolution down from ~60% of modprobe's time to ~7%.  The nice thing
about using sorted tables that they stay the same size.

Regards
Alan

Re: module: Speed up symbol resolution during module loading

[Rusty Russell]

On Thu, 24 Sep 2009 02:22:15 am Alan Jenkins wrote:
> [CC to lkml fixed :-/]
> 
> Rusty Russell wrote:
> > On Tue, 22 Sep 2009 10:58:28 pm Alan Jenkins wrote:
> >   
> >> The following series applies against v2.6.31. It sorts the tables of builtin
> >> symbols, so the module loader can resolve them using a binary search.
> >>
> >> The kbuild changes to achieve this are less scary than I expected.  I'm
> >> optimistic that they can be accepted without radical alteration :-).
> >>
> >> Quoting from the last patch in this series:
> >>
> >> "On my EeePC 701, coldplug is mainly cpu bound and takes 1.5 seconds
> >> during boot. perf showed this change eliminated 20% of cpu cycles during
> >> coldplug, saving 0.3 seconds of real time.
> >>     
> >
> > Hi Alan,
> >
> >    This seems useful, but wouldn't it be simpler to just sort at boot time?
> > The same could be done for modules, possibly reducing code.
> >
> > Alternately, there's a standard way of hashing ELF symbols, but I'm not sure
> > we can convince the linker to generate it for vmlinux (I haven't looked
> > though).
> >
> > Thanks!
> > Rusty.
> >   
> 
> I'm concerned that people would object to the extra overhead at boot
> time.  I've hacked up a prototype to sort at boot time and it takes 7ms
> on the same hardware.

OK, that seems a lot to me.  Fair enough; if Sam acks the build parts, I'll
put it in my tree.  A bit late for this merge window though.

Thanks!
Rusty.

module: Speed up symbol resolution during module loading

[Alan Jenkins]

[Apologies for duplicate messages. It's debatable whether I should be trusted
 with commands called names like "guilt-patchbomb". ]

The following series applies against v2.6.31. It sorts the tables of builtin
symbols, so the module loader can resolve them using a binary search.

The kbuild changes to achieve this are less scary than I expected.  I'm
optimistic that they can be accepted without radical alteration  :-) .

Quoting from the last patch in this series:

"On my EeePC 701, coldplug is mainly cpu bound and takes 1.5 seconds
during boot. perf showed this change eliminated 20% of cpu cycles during
coldplug, saving 0.3 seconds of real time.

These savings may not be representative since my config is not very well
tuned.  The numbers above represent the loading of 35 modules,
referencing a total of 441 symbols.  Nevertheless, it shows why I think
this is worth doing."

Alan