Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1756166AbYHMVpq (ORCPT ); Wed, 13 Aug 2008 17:45:46 -0400 Received: (majordomo@vger.kernel.org) by vger.kernel.org id S1751655AbYHMVpf (ORCPT ); Wed, 13 Aug 2008 17:45:35 -0400 Received: from one.firstfloor.org ([213.235.205.2]:35033 "EHLO one.firstfloor.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752539AbYHMVpe (ORCPT ); Wed, 13 Aug 2008 17:45:34 -0400 Date: Wed, 13 Aug 2008 23:46:50 +0200 From: Andi Kleen To: Andrew Morton Cc: Andi Kleen , mingo@elte.hu, drepper@redhat.com, arjan@infradead.org, hugh@veritas.com, linux-mm@kvack.org, linux-kernel@vger.kernel.org, briangrant@google.com, cgd@google.com, mbligh@google.com, torvalds@linux-foundation.org, tglx@linutronix.de, hpa@zytor.com Subject: Re: pthread_create() slow for many threads; also time to revisit 64b context switch optimization? Message-ID: <20080813214650.GS1366@one.firstfloor.org> References: <20080813104445.GA24632@elte.hu> <20080813063533.444c650d@infradead.org> <48A2EE07.3040003@redhat.com> <20080813142529.GB21129@elte.hu> <48A2F157.7000303@redhat.com> <20080813151007.GA8780@elte.hu> <87fxp8zlx3.fsf@basil.nowhere.org> <20080813135633.dcb8d602.akpm@linux-foundation.org> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20080813135633.dcb8d602.akpm@linux-foundation.org> User-Agent: Mutt/1.4.2.1i Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 1287 Lines: 28 > Yes, the free_area_cache is always going to have failure modes - I > think we've been kind of waiting for it to explode. > > I do think that we need an O(log(n)) search in there. It could still > be on the fallback path, so we retain the mostly-O(1) benefits of > free_area_cache. The standard dumb way to do that would be to have two parallel trees, one to index free space (similar to e.g. the free space btrees in XFS) and the other to index the objects (like today). That would increase the constant factor somewhat by bloating the VMAs, increasing cache overhead etc, and also would be more brute force than elegant. But it would be simple and straight forward. Perhaps the combined data structure experience of linux-kernel can come up with something better and some data structure that allows to look up both efficiently? This would be also an opportunity to reevaluate rbtrees for the object index. One drawback of them is that they are not really optimized to be cache friendly because their nodes are too small. -Andi -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/