RE: Kernel profile

Ray Van Tassle-CRV004 (
Tue, 30 Jul 1996 9:50:11 -0500

> Address Function count density percentage
> 001224a8 get_empty_filp 1085911 4378.6734 14.50
> And guess what: get_empty_filp does a linear search. :(
> get_empty_filp() appears to do a linear search of the 'struct file's
> list, relying on a couple of simple heuristics to avoid worst cast
> behaviour. My guess is that if it instead:
> didn't move structs around on the list at all.
> started searching from where it left of last time for an empty
> struct.
> it would run a fair bit faster. Given that structures never get
> destroyed this would seem to be pretty easy to implement?
> Any ideas for dramatic speed improvements? :)

How about if an unused member (when f_count dropped to zero) got placed at
the front of the list?
As it is, the "found" one is moved to the end of the list, so wouldn't the
empty ones tend to bubble up? (I don't know the access pattern, so I'm just

FWIW, "get_request" (in ll_rw_blk.c) does a linear search, starting from
where it stopped last time. This bothers me. It seems like a linear search
for a free element is inherently inefficient.
find_buffer (fs/buffer.c) also does a linear search, but uses a ridiculously
large (hash) table of listheads.

However, I think that before mucking with this, it would be best to capture
the access pattern (alloc/free) of a running system, and use this to
experiment with different algorithms. Yup, this would be a HUGE amount of
data to collect.

-30- Ray

> Michael.