From owner-freebsd-current@FreeBSD.ORG Fri Nov 28 18:17:21 2003 Return-Path: Delivered-To: freebsd-current@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id C007816A4CE; Fri, 28 Nov 2003 18:17:21 -0800 (PST) Received: from smtp.des.no (flood.des.no [217.116.83.31]) by mx1.FreeBSD.org (Postfix) with ESMTP id 8EC4743F85; Fri, 28 Nov 2003 18:17:20 -0800 (PST) (envelope-from des@des.no) Received: by smtp.des.no (Pony Express, from userid 666) id 44C825309; Sat, 29 Nov 2003 03:17:19 +0100 (CET) Received: from dwp.des.no (des.no [80.203.228.37]) by smtp.des.no (Pony Express) with ESMTP id 66A8C5308; Sat, 29 Nov 2003 03:17:09 +0100 (CET) Received: by dwp.des.no (Postfix, from userid 2602) id 2903133C8C; Sat, 29 Nov 2003 03:17:09 +0100 (CET) To: Tim Robbins References: <20031127070239.GA12950@wombat.robbins.dropbear.id.au> <20031129011658.GA1347@wombat.robbins.dropbear.id.au> From: des@des.no (Dag-Erling =?iso-8859-1?q?Sm=F8rgrav?=) Date: Sat, 29 Nov 2003 03:17:08 +0100 In-Reply-To: <20031129011658.GA1347@wombat.robbins.dropbear.id.au> (Tim Robbins's message of "Sat, 29 Nov 2003 12:16:58 +1100") Message-ID: User-Agent: Gnus/5.090024 (Oort Gnus v0.24) Emacs/21.3 (berkeley-unix) MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: quoted-printable X-Spam-Checker-Version: SpamAssassin 2.60 (1.212-2003-09-23-exp) on flood.des.no X-Spam-Level: ss X-Spam-Status: No, hits=2.6 required=5.0 tests=RCVD_IN_DYNABLOCK, RCVD_IN_SORBS autolearn=no version=2.60 cc: current@freebsd.org Subject: Re: Port of Niels Provos's file descriptor allocation code X-BeenThere: freebsd-current@freebsd.org X-Mailman-Version: 2.1.1 Precedence: list List-Id: Discussions about the use of FreeBSD-current List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 29 Nov 2003 02:17:21 -0000 Tim Robbins 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