Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id ; Thu, 14 Nov 2002 20:38:54 -0500 Received: (majordomo@vger.kernel.org) by vger.kernel.org id ; Thu, 14 Nov 2002 20:38:54 -0500 Received: from nat-pool-rdu.redhat.com ([66.187.233.200]:60617 "EHLO devserv.devel.redhat.com") by vger.kernel.org with ESMTP id ; Thu, 14 Nov 2002 20:38:53 -0500 Date: Thu, 14 Nov 2002 20:45:39 -0500 From: Pete Zaitcev To: William Lee Irwin III , Tim Hockin , Pete Zaitcev , linux-kernel@vger.kernel.org Subject: Re: [BK PATCH 1/2] Remove NGROUPS hardlimit (resend w/o qsort) Message-ID: <20021114204539.A15162@devserv.devel.redhat.com> References: <200211150006.gAF06JF01621@devserv.devel.redhat.com> <3DD43C65.80103@sun.com> <20021114193156.A2801@devserv.devel.redhat.com> <3DD443EC.2080504@sun.com> <20021115011947.GP23425@holomorphy.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.2.5.1i In-Reply-To: <20021115011947.GP23425@holomorphy.com>; from wli@holomorphy.com on Thu, Nov 14, 2002 at 05:19:47PM -0800 Sender: linux-kernel-owner@vger.kernel.org X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 1620 Lines: 34 > > Offer an alternative? :) Linked list costs us as much or MORE for > > ->next as the gid_t. kmalloc() doesn't work for previous reasoning. I > > considered a list of gid arr[256] or similar. A voice reminds me that > > it doesn't impact us noticably in real use. Now, maybe other > > architectures will find a good reason to switch to kmalloc() list of > > smaller arrays, and the associated complextities or something else more > > clever. > > Well, there are always B-trees; nice low arrival rates to the allocator > owing to elements/node and O(lg(n)) searches with low constants due to > big fat branching factors. Not my call though. This sounds intriguing. Bill, if I may borrow from your data structure expertise, what would you do if you wanted gid_t's indexed by two criteria? Obviously, we want them them indexed by value (to look them up for access checking), but NFS also needs them sorted by usage, to fit the last 3 into the RPC parameters. This looks like something requiring two overlaying trees who share leafs, and every leaf being a single gid_t, with nightmarish overhead. Before Tim came to the scene, the hope was that lookups would do exhaustive search of arrays, sorted by LRU, while RPC picked N leading elements of said sorted array. Tim busts this scheme to pieces, because he sorts arrays by value (if I read it right). -- Pete - 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/