> > One thing I didn't mention is that the old pid allocation code is
> > actually at least o(n^2) in the number of allocated pids.
> > The new code is o(1).
> 
> Do you actually mean little-o? If so, what's your k? (How many procs
> need to exist before the algorithm's o(1)?)

Somewhen in that last 20 years (since I did my maths degree) I seem
to have forgotten the difference between o(n) and O(n) :-(

In any case my new code has a constant (small) cost for allocating
a pid.  The existing code has an n^2 term so, for a sufficiently
large number of processes, the pid allocation will become the
dominant term in the cost of fork() (unless something else is worse).

These 'small' costs can get significant.  One Unix kernel used a
linked list for the fd -> file map for each process.  This meant
that the convertion was o(fd), which made poll o(fd^2) and setting
up a large poll list o(fd^3).  One particular test suffered badly :-)
(IIRC it had several thousand files in the list...)

	David
-- 
David Laight: david@l8s.co.uk