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.
