Port of Niels Provos's file descriptor allocation code

[Dag-ErlingSmørgrav]

Tim Robbins <tjr at freebsd.org> writes:
> It's also the NetBSD fdalloc code. They started with code similar to ours,
> in that it did a linear search of the file descriptor array to find an
> empty slot and used hints to speed up some common allocation patterns,
> then recently switched over to using the multi-level bitmap allocator.
> I can't think of any reason why we wouldn't see improvements similar to
> what they saw:
> 	http://www.citi.umich.edu/u/provos/benchmark/netbsd-fdalloc.jpg

Having looked at the code, I believe that the graph is the result of
an improperly designed benchmark.  FreeBSD's performance *with a
properly designed benchmark* should be similar to the red line (it's
not as bad as it looks; the sharp rise caused by cache trashing occurs
around 30k fds which is a pretty respectable number).  The same
benchmark would show a similar but less steep curve for the "multi-
level bitmap" (which is just a fancy way of saying "micro-optimized
trie").  A proper trie would result in a logarithmic curve.

DES
-- 
Dag-Erling Smørgrav - des at des.no