Date: Mon, 22 Aug 2005 10:46:41 -0700 (PDT) From: Matthew Dillon <dillon@apollo.backplane.com> To: des@des.no (=?iso-8859-1?q?Dag-Erling_Sm=F8rgrav?=) Cc: arch@freebsd.org, Alexey Dokuchaev <danfe@freebsd.org> Subject: Re: fdesc allocation optimization Message-ID: <200508221746.j7MHkfgY050608@apollo.backplane.com> References: <20050822100059.GA24626@FreeBSD.org> <863bp25c7t.fsf@xps.des.no>
next in thread | previous in thread | raw e-mail | index | archive | help
:Alexey Dokuchaev <danfe@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 :<URL:http://people.freebsd.org/~des/fdbench/>. : :(the strange artifacts you see on the red graphs are the result of the :file descriptor table overrunning the CPU cache) : :DES :-- :Dag-Erling Smørgrav - des@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. -Matt Matthew Dillon <dillon@backplane.com>
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200508221746.j7MHkfgY050608>