From mboxrd@z Thu Jan 1 00:00:00 1970 From: Matthew Wilcox Date: Wed, 19 Aug 2020 16:24:03 +0000 Subject: Re: [PATCH 00/11] Introduce kernel_clone(), kill _do_fork() Message-Id: <20200819162403.GF17456@casper.infradead.org> List-Id: References: <20200818174447.GV17456@casper.infradead.org> <20200819074340.GW2674@hirez.programming.kicks-ass.net> <20200819084556.im5zfpm2iquzvzws@wittgenstein> <20200819111851.GY17456@casper.infradead.org> <87a6yq222c.fsf@x220.int.ebiederm.org> <20200819134629.mvd4nupme7q2hmtz@wittgenstein> <87mu2qznlv.fsf@x220.int.ebiederm.org> <20200819154521.GE17456@casper.infradead.org> In-Reply-To: MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit To: David Laight Cc: "'Eric W. Biederman'" , Christian Brauner , "peterz@infradead.org" , Christoph Hewllig , "linux-kernel@vger.kernel.org" , Linus Torvalds , "linux-arch@vger.kernel.org" , Jonathan Corbet , Yoshinori Sato , Tony Luck , Fenghua Yu , Geert Uytterhoeven , Ley Foon Tan , "David S. Miller" , Thomas Gleixner , Ingo Molnar , Borislav Petkov , "x86@kernel.org" , Arnd Bergmann , Steven Rostedt , Stafford Horne , Kars de Jong , Kees Cook , Greentime Hu , Mauro Carvalho Chehab , Alexandre Chartre , Masami Hiramatsu , Tom Zanussi , Xiao Yang , "linux-doc@vger.kernel.org" , "uclinux-h8-devel@lists.sourceforge.jp" , "linux-ia64@vger.kernel.org" , "linux-m68k@lists.linux-m68k.org" , "sparclinux@vger.kernel.org" , "kgdb-bugreport@lists.sourceforge.net" , "linux-kselftest@vger.kernel.org" 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.