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...).