From owner-freebsd-arch@FreeBSD.ORG Mon Aug 22 17:46:46 2005 Return-Path: X-Original-To: arch@freebsd.org Delivered-To: freebsd-arch@FreeBSD.ORG Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 5F80016A41F; Mon, 22 Aug 2005 17:46:46 +0000 (GMT) (envelope-from dillon@apollo.backplane.com) Received: from apollo.backplane.com (apollo.backplane.com [216.240.41.2]) by mx1.FreeBSD.org (Postfix) with ESMTP id 234DD43D45; Mon, 22 Aug 2005 17:46:46 +0000 (GMT) (envelope-from dillon@apollo.backplane.com) Received: from apollo.backplane.com (localhost [127.0.0.1]) by apollo.backplane.com (8.12.9p2/8.12.9) with ESMTP id j7MHkfYk050609; Mon, 22 Aug 2005 10:46:41 -0700 (PDT) (envelope-from dillon@apollo.backplane.com) Received: (from dillon@localhost) by apollo.backplane.com (8.12.9p2/8.12.9/Submit) id j7MHkfgY050608; Mon, 22 Aug 2005 10:46:41 -0700 (PDT) (envelope-from dillon) Date: Mon, 22 Aug 2005 10:46:41 -0700 (PDT) From: Matthew Dillon Message-Id: <200508221746.j7MHkfgY050608@apollo.backplane.com> To: des@des.no (=?iso-8859-1?q?Dag-Erling_Sm=F8rgrav?=) References: <20050822100059.GA24626@FreeBSD.org> <863bp25c7t.fsf@xps.des.no> Cc: arch@freebsd.org, Alexey Dokuchaev Subject: Re: fdesc allocation optimization X-BeenThere: freebsd-arch@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Discussion related to FreeBSD architecture List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 22 Aug 2005 17:46:46 -0000 :Alexey Dokuchaev 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) : :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