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

From: Pete Zaitcev (
Date: Thu Nov 14 2002 - 20:45:39 EST

> > 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
More majordomo info at
Please read the FAQ at

This archive was generated by hypermail 2b29 : Fri Nov 15 2002 - 22:00:35 EST