Date: Fri, 30 Jan 2004 00:04:43 -0800 From: David Schultz <das@FreeBSD.ORG> To: Tim Robbins <tjr@FreeBSD.ORG> Cc: current@FreeBSD.ORG Subject: Re: Call for testers: New PID allocator patch for -CURRENT Message-ID: <20040130080442.GA55977@VARK.homeunix.com> In-Reply-To: <20040130014308.GA21425@cat.robbins.dropbear.id.au> References: <20040129134121.GB53644@frontfree.net> <20040129200442.GA52780@VARK.homeunix.com> <20040130014308.GA21425@cat.robbins.dropbear.id.au>
next in thread | previous in thread | raw e-mail | index | archive | help
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?
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20040130080442.GA55977>