Date: Sat, 29 Nov 2003 03:17:08 +0100 From: des@des.no (Dag-Erling =?iso-8859-1?q?Sm=F8rgrav?=) To: Tim Robbins <tjr@freebsd.org> Cc: current@freebsd.org Subject: Re: Port of Niels Provos's file descriptor allocation code Message-ID: <xzp7k1j9avv.fsf@dwp.des.no> In-Reply-To: <20031129011658.GA1347@wombat.robbins.dropbear.id.au> (Tim Robbins's message of "Sat, 29 Nov 2003 12:16:58 %2B1100") References: <20031127070239.GA12950@wombat.robbins.dropbear.id.au> <xzpvfp4816m.fsf@dwp.des.no> <20031129011658.GA1347@wombat.robbins.dropbear.id.au>
next in thread | previous in thread | raw e-mail | index | archive | help
Tim Robbins <tjr@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 --=20 Dag-Erling Sm=F8rgrav - des@des.no
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?xzp7k1j9avv.fsf>