fdesc allocation optimization

Matthew Dillon dillon at apollo.backplane.com
Mon Aug 22 17:46:46 GMT 2005

:Alexey Dokuchaev <danfe at FreeBSD.org> writes:
:> i've been browsing some of dfbsd resources recently, and found this one
:> being pretty interesting:
:> http://leaf.dragonflybsd.org/mailarchive/commits/2005-06/msg00526.html
:> however, it seemingly did not get attention in our lists.  so i am
:> wondering if there are work/plans on porting hsu@'s work?  i remember
:> that at some point we adopted some openbsd-derived algorithm, but since
:> matt states that this is "far better algorithm then anything we or
:> freebsd thought up before", i figured it worth a look.
:Bollocks.  Our current algorithm (which I wrote) is so fast you don't
:even notice it's there.  It's actually simpler than the OpenBSD code
:from which it was inspired, and in theory it should be slower, but I
:discovered that the overhead of the "better" algorithm was so high
:that it consistently lost to the simpler one for reasonable amounts of
:file descriptors (up to about 100,000 per process).
:The source code for the microbenchmark I used, and selected graphs
:comparing my code to the previous implementation, are available at
:(the strange artifacts you see on the red graphs are the result of the
:file descriptor table overrunning the CPU cache)
:Dag-Erling Smørgrav - des at des.no
    Well, I expect that once you get past a pure linear search any algorithm
    will fast enough that it probably doesn't matter in real life.  But I 
    would not pooh-pooh Jeff's implementation of the Solaris algorithm so
    quickly.  It is the fastest, cleanest, most elegant implementation of
    a file descriptor handling algorithm that I've ever seen in my life.
    Anyone who actually reads the code will come away wondering why FreeBSD 
    is still screwing around with linear bitmaps.

					Matthew Dillon 
					<dillon at backplane.com>

More information about the freebsd-arch mailing list