19 Aug
2020
19 Aug
'20
3:55 p.m.
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.
David
- Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK Registration No: 1397386 (Wales)