[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]
Re: radix tree implementation for quota ?
On Sun, Nov 28, 2010 at 06:27:07PM +0100, Manuel Bouyer wrote:
> > Wouldn't a hash table work?
> I think it's too dependant on uid distribution, or even how much uid you
> have. a tree scales and adapts better.
I agree, hash tables often degenerate into a linear search.
This means that it is still linear, just 'n' times faster that a
simple linear search.
It might be worth using a simple hash to cache recent lookups into
OTOH it is worth remembering that there is already a 'per uid' structure
(IIRC currently hashed % MAXUSERS) used for counting processes per user.
Would seem relevant to hang the per-mount data of this structure.
(and maybe use a better lookup than the current hash - it is one of the
few uses of MXUSERS).
On disk, I'm not sure.
Once you've read a disk block, you might as well do a linear search!
This probably only happens at user login time.
More problematical is some kind of log so that you don't need to scan
the entire fs after a system crash...
David Laight: david%l8s.co.uk@localhost
Main Index |
Thread Index |