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

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



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)




[Index of Archives]     [Linux Wireless]     [Linux Kernel]     [ATH6KL]     [Linux Bluetooth]     [Linux Netdev]     [Kernel Newbies]     [Share Photos]     [IDE]     [Security]     [Git]     [Netfilter]     [Bugtraq]     [Yosemite News]     [MIPS Linux]     [ARM Linux]     [Linux Security]     [Linux RAID]     [Linux ATA RAID]     [Samba]     [Device Mapper]

  Powered by Linux