Re: [PATCH] Radix-tree pagecache for 2.5

[Momchil Velikov <velco@fadata.bg>]

>>>>> "Josh" == Josh MacDonald <jmacd@CS.Berkeley.EDU> writes:

Josh> Quoting Momchil Velikov (velco@fadata.bg):
>> >>>>> "John" == John Stoffel <stoffel@casc.com> writes:

Momchil>  The worst case would be very large file with a few cached
Momchil> pages with offsets uniformly distributed across the whole
Momchil> file, that is having deep tree with only one page hanging off
Momchil> each leaf node.

John> Isn't this a good place to use AVL trees then, since they balance
John> automatically?  Admittedly, it may be more overhead than we want in
John> the case where the tree is balanced by default anyway.  

>> The widespread opinion is that binary trees are generally way too deep
>> compared to radix trees, so searches have larger cache footprint.

Josh> I've posted this before -- my cache-optimized skip list solves the
Josh> problem of balanced-tree cache footprint.  It uses cacheline-sized

I don't think skip lists differ from the balanced trees w.r.t cache
line footprint.

Josh> nodes and per-node locking to avoid false-sharing and increase 

Whether there _is_ a (non-negligible) false sharing would be an open
question.

Josh> concurrency.  The memory usage for the skip list is also less than
Josh> the red-black tree for trees larger than several hundred nodes.

Yes. Skip list or (whatever) b-tree are sure to have less space
overhead in the worst case.  Therefore, I'd be curious to see
comparisons with the three pagecache implementations.  Note that in my
last patch you can do a drop-in replacement of the radix tree with a
skip list, since memory allocation issues are solved.

Regards,
-velco