Re: Call for testers: New PID allocator patch for -CURRENT

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?