Bug 10218 - "depmod -a" should be faster
Summary: "depmod -a" should be faster
Alias: None
Product: Red Hat Linux
Classification: Retired
Component: modutils
Version: 6.1
Hardware: All
OS: Linux
Target Milestone: ---
Assignee: Michael K. Johnson
QA Contact:
Keywords: FutureFeature
Depends On:
TreeView+ depends on / blocked
Reported: 2000-03-17 13:39 UTC by niv_twig
Modified: 2008-05-01 15:37 UTC (History)
0 users

Clone Of:
Last Closed: 2000-03-20 15:38:47 UTC

Attachments (Terms of Use)

Description niv_twig 2000-03-17 13:39:44 UTC
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.

Comment 1 Bill Nottingham 2000-03-20 15:38:59 UTC
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).

Note You need to log in before you can comment on or make changes to this bug.