--NHeczCl9PClrEofy
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

On Mon, Mar 17, 2003 at 02:33:00PM -0500, der Mouse wrote:
> Not quite.  As you point out elsewhere, it depends on the constant
> factors.  Indeed, since there is a fixed maximum PID, theoretically,
> any way is O(1) because it is dominated by whatever the worst case is
> over the (finite!) set of all possible used/unused PID distributions.

Heh. True.

As I said, *assuming* that c & k for both algorithms are vaguely
congruent, then o(1) beats o(n^2), and David's not too likely to
have made the comparison if they weren't somewhat close.

Having slightly larger constants is probably acceptable. That is,
the current scheme seems to be running around with mostly 5-digit
PIDs on a system that's been up for a month now. One presumes it's
within its constraints at this point, though I guess I don't really
know that. If David's system behaves about the same for a week and
then significantly better, it's better. If it takes more than a
month's worth of PID allocations to hit its o(1) state, then we're
maybe not so happy (show me a production system running *any* OS
that hasn't been rebooted in a month or two and I'll show you a
security nightmare).

--=20
gabriel rosenkoetter
gr@eclipsed.net

--NHeczCl9PClrEofy
Content-Type: application/pgp-signature
Content-Disposition: inline

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.1 (NetBSD)

iD8DBQE+dig+9ehacAz5CRoRAgU0AJ9/29tOSYZMEYLSrkMk/FOVzoxaeQCfU7U1
b644ReHwlj/gE0pQYeit8/4=
=uUuV
-----END PGP SIGNATURE-----

--NHeczCl9PClrEofy--