Re: [PATCH 00/11] Introduce kernel_clone(), kill _do_fork()

[Matthew Wilcox]

On Wed, Aug 19, 2020 at 03:55:47PM +0000, David Laight wrote:
> From: Matthew Wilcox
> > Sent: 19 August 2020 16:45
> > 
> > On Wed, Aug 19, 2020 at 03:41:48PM +0000, David Laight wrote:
> > > Does linux have an O(1) (or do I mean o(1)) pid allocator?
> > > Or does it have to do a linear scan to find a gap??
> > 
> > O(log(n)).  It uses the IDR allocator, so 'n' in this case is the
> > number of PIDs currently allocated, and it's log_64 rather than log_2
> > (which makes no difference to O() but does make a bit of a difference
> > to performance)
> 
> Still worse that O(1) - when that is just replacing a variable
> with a value read out of an array.
> Made pid lookup a trivial O(1) as well.

You'd be surprised.  We replaced the custom PID allocator with the
generic IDR allocator a few years ago and got a pretty decent speedup.

If you think you can do better, then submit patches.  You have to support
all the existing use cases, of course.