Messages in this thread |  | | Subject | Re: Kernel profile | Date | Fri, 02 Aug 1996 09:41:25 +0800 | From | "Michael O'Reilly" <> |
| |
Hmm. On average you'd expect it to be slower. Assuming an even distribution, you expect to examine N/M elements to find a free one (where N is the total number, and M is the number of free elements). This is actually independant of the order in which you search (as long as it's a deterministic, non-repeating search). So you'd still (on average) examine as many elements, but you've got the overhead in tracking two pointers instead of one.
In actuality, the distribution isn't even. You expect there to be more used elements behind the pointer than there are ahead of it (because you just told the kernel to use those ones behind the pointer), and thus you'd probably expect to search about 50-100% more elements.
The major difference between the old routine, and my routine as far as I can see, is not the number of elements examined for 'freeness', but the overhead in making a free element useable. The old routine made 3 function calls, moved 8 pointers, and cleared the entire structure. When you add in cache effects, one could easily see a 50 times difference in timings. (at least, I can. :)
Michael, playing at theory.
In message <199608020114.EAA00420@nerd.uwasa.fi>, Johnny Stenback writes: > Hi! > > Here's a patch I made that changes the get_empty_filp function to walk > the file table list in both directions while it searches for an empty > structure. This patch is otherwise the same as the patch posted a few > days ago by Michael O'Reilly (ie uses a static pointer so that a > search starts where the last ended...). The fact that it walks the > list in both directions of-course makes the walk a bit slower > (even-though it only walks half the way) but IMO it might give better > over all performance (I don't know because I newer got my home > computer to uses get_empty_filp intensively, when I turned on > profiling I saw that it is much faster than the original search but I > don't know if it's faster or slower than Michaels patch, anyone know > how to stress-test this or anyone wants test this on a computer that > has shown to use much time in get_empty_filp and show us some > results...).
|  |