PID Allocator Performance Results (was: Re: [UPDATE] new pid alloc...)

I spent some time today benchmarking the various proposed pid
allocators.  The full results, along with pretty pictures and a
more complete analysis, are at:

	http://people.freebsd.org/~das/pbench/pbench.html  [1]

To summarize, the old allocator begins to perform poorly when
there are several thousand processes in the system.  Both the
NetBSD allocator and tjr's patch, which replaces the collision
detection step with a hash lookup, eliminate the scaling issue.[2]
Neither of the new approaches have measurable overhead over the
current approach when there are very few processes.

My inclination is to go for Tim's proposal because it is simpler
and it does not have an impact on which pids may be allocated.
Although the code you ported from NetBSD is more scalable in the
asymptotic sense, it does not appear to be better than Tim's hash
table in practice.  Ultimately, however, I think it ought to be
jhb's decision.  In any case, please understand that these sorts
of improvements are definitely welcome, and I'm grateful for your
time and effort.


[1] The web page also mentions a problem with wait4() I ran
    into that might explain why Tim didn't observe the
    performance improvement he was looking for.

[2] All of the algorithms presumably go exponential when you
    approach PID_MAX processes, but that isn't a reasonable
    situation, and if it was, we would need to bump PID_MAX
    as Solaris has done.