Re: [PATCH] make radix tree gang lookup faster by using a bitmap search

[James Bottomley <James.Bottomley@SteelEye.com>]

On Mon, 2005-08-29 at 13:37 +1000, Nick Piggin wrote:
> But the page tree is indexed by file offset rather than virtual
> address, and we try to span the file's pagecache with the smallest
> possible tree. So it will tend to make the trees taller.

Well, OK, I concede that one.

However, my contention that it's better to do it this way is rooted in
the simplicity argument:  a bitmap lookup obviously can move straight to
the slot you're looking for.  However, we've always had that loop (which
wastes time) because no-one could get the bitmap code right.  The reason
for this is that variable length bitmaps are hard to manage and
introduce a lot of complexity into what should really be simple code.

I think simplicity is better (for ease of understanding and maintenance)
unless it has an unacceptable cost.  In this case, that cost would be
shown by the benchmarks.  If what I've done is slower on 32 bits than
what we had previously then I'll recode it all with variable length
bitmaps so we can increase the 32 bin index bits to 6 again.

> > Well .. OK .. If the benchmarks say I've slowed us down on 32 bits, I'll
> > put the variable sizing back in the tag array.

> I'm curious: what do the benchmarks say about your gang lookup?

That's why I tried to cc the mm list; I'm not sure what you use for
benchmarks of this type of thing.  My guess would be a mmap of a file,
read followed by some writes, then munmap again?

James