Re: Port of Niels Provos's file descriptor allocation code

From: Dag-Erling Smørgrav <des_at_des.no>
Date: Sat, 29 Nov 2003 03:17:08 +0100
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
Received on Fri Nov 28 2003 - 17:17:21 UTC

This archive was generated by hypermail 2.4.0 : Wed May 19 2021 - 11:37:31 UTC