Messages in this thread | ![/](/images/icornerl.gif) | | Date | Tue, 30 Jul 1996 9:50:11 -0500 | From | "Ray Van Tassle-CRV004" <> | Subject | RE: Kernel profile |
| |
> 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 guessing.)
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. >
| ![\](/images/icornerr.gif) |