Red Hat Bugzilla – Bug 10218
"depmod -a" should be faster
Last modified: 2008-05-01 11:37:54 EDT
it is important to make "depmod -a" faster because it is run during the
boot process of the computer from the init scripts, and it takes several
seconds which are a lot of time relative to the whole boot time.
I think I have an idea how to make it faster:
First, the current situation is this:
in the file depmod.c where the dependency checking is done, the program
goes over all object files and for each object file over all the symbols
and tries to resolve each symbol(see in which object file it is declared).
for each symbol it tries to resolve, it goes again over all object files
and tries to find the symbol in each object file until it is found in one
of them. the algorithm can take O(N^2) where N is the number of object
files in the system. In my Linux 6.1 system N=~400 .
I think a better approach than making a hash table for each object file
like it is today, would be to put all symbols from all objects in one hash
table. that will make finding a symbol and the object file in which it is
declared much faster.
This is improved in modutils-2.3.10, which has a flag
to only create a new modules.dep if needed (i.e., timestamp
on modules >= timestamp on modules.dep).