From owner-freebsd-current@FreeBSD.ORG Fri Jan 30 00:05:03 2004 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 1B44516A4CE; Fri, 30 Jan 2004 00:05:03 -0800 (PST) Received: from VARK.homeunix.com (adsl-68-122-7-9.dsl.pltn13.pacbell.net [68.122.7.9]) by mx1.FreeBSD.org (Postfix) with ESMTP id 8BF2143D55; Fri, 30 Jan 2004 00:05:01 -0800 (PST) (envelope-from das@FreeBSD.ORG) Received: from VARK.homeunix.com (localhost [127.0.0.1]) by VARK.homeunix.com (8.12.10/8.12.10) with ESMTP id i0U84hf5056262; Fri, 30 Jan 2004 00:04:43 -0800 (PST) (envelope-from das@FreeBSD.ORG) Received: (from das@localhost) by VARK.homeunix.com (8.12.10/8.12.10/Submit) id i0U84hJv056261; Fri, 30 Jan 2004 00:04:43 -0800 (PST) (envelope-from das@FreeBSD.ORG) Date: Fri, 30 Jan 2004 00:04:43 -0800 From: David Schultz To: Tim Robbins Message-ID: <20040130080442.GA55977@VARK.homeunix.com> Mail-Followup-To: Tim Robbins , Xin LI , current@FreeBSD.ORG, hackers@FreeBSD.ORG, junsu@delphij.net References: <20040129134121.GB53644@frontfree.net> <20040129200442.GA52780@VARK.homeunix.com> <20040130014308.GA21425@cat.robbins.dropbear.id.au> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20040130014308.GA21425@cat.robbins.dropbear.id.au> cc: junsu@delphij.net cc: hackers@FreeBSD.ORG cc: current@FreeBSD.ORG Subject: Re: Call for testers: New PID allocator patch for -CURRENT 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: Fri, 30 Jan 2004 08:05:03 -0000 On Fri, Jan 30, 2004, Tim Robbins wrote: > [...] > > [1] That shouldn't be hard, given that the present algorithm takes > > O(N) amortized time in the worst case, and can examine as many > > as PID_MAX^2 pids if the number of processes in the system is > > close to PID_MAX. > [...] > > In my testing, the current pid allocator turned out to be more efficient > than I had expected. Even after reducing PID_MAX to 10,000 and > fragmenting the pid-space by having sleeping processes at every N'th > pid, it didn't run much slower than the hash-based alternative I was > testing it against. > > This is the hash-based pid allocator, if anyone's interested: The current allocator might have to scan the entire allproc list for each pid it allocates, so your results surprise me. In any case, I like your hash-based approach, and I was thinking of something similar myself. The other proposed patch could be faster in theory, since there are never any hash chains due to collisions, and free space in the table is used to form a linked list of free pids. Collisions are avoided by choosing to allocate pids that don't conflict (mod the table size), and by increasing the table size when necessary. Unfortunately, this approach completely changes which pids can be reused and when. That's why I expressed reservations in my earlier response, and why it would be a significant amount of work just to figure out if there are any problems on busy systems. Ultimately, I actually prefer the simplicity of your approach, Tim, given that I can just look at the code and see that there are no big surprises. Does anyone have performance numbers or other reasons why the NetBSD patches are better?