Re: [BK PATCH 1/2] Remove NGROUPS hardlimit (resend w/o qsort)

[Pete Zaitcev <zaitcev@redhat.com>]

> > 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