Re: Linux page cache issue?

["Xin Zhao" <uszhaoxin@gmail.com>]

You are right. If the device is very big, the radix tree could be huge
as well. Maybe the lookup it not that cheap. But the per-device tree
can be optimized too. A simple way I can immediately image is: evenly
split a device into N parts by the sector numbers. For each part, we
maintain a radix tree. Let's do a math. Suppose I have a 32G partition
(2^35 bytes) and each data block is 4K bytes (2^12).  So the partition
has 2^23 blocks. I divide the blocks into 1024 (2^12) groups. Each
group will only have 2^11 blocks. With radix tree, the average lookup
overhead for each tree would be log(2^11) steps. That is 11 in-memory
tree traverse to locate a page. This cost seems to be acceptable. I
don't really measure it though. As to the memory used for maintain the
radix trees, I believe it is trivial considering the memory size of
modern computers.

Xin

On 3/28/07, John Anthony Kazos Jr. <jakj@j-a-k-j.com> wrote:
> > The lookup of the per-device radix tree may incur some overhead. But
> > compared to the slow disk access, looking up an in-memory radix tree is
> > much cheaper and should be trivial, I guess.
>
> I would consider whether or not it really is trivial. You'd have to think
> hard about just how much of your filesystem is going to be sharing data
> blocks. If you fail to find in the per-file tree, then fail to find in the
> per-device tree, then still have to read the block from the device, and
> this is happening too often, then the additional overhead of the
> per-device tree check for non-cached items may end up cancelling the
> savings for cached items.
>