Re: [PATCH] Radix-tree pagecache for 2.5

[Momchil Velikov <velco@fadata.bg>]

>>>>> "John" == John Stoffel <stoffel@casc.com> writes:

Momchil> Memory overhead due to allocator overhead is of no concern with the
Momchil> slab allocator. What matters most is probably the overhead of the
Momchil> radix tree nodes themselves, compared to the two pointers in struct
Momchil> page with the hash table approach. rat-4 variant ought to have less
Momchil> overhead compared to rat-7 at the expense of deeper/higher tree. I
Momchil> have no figures for the actual memory usage though. For small files it
Momchil> should be negligible, i.e. one radix tree node, 68 or 516 bytes for
Momchil> rat-4 or rat-7, for a file of size up to 65536 or 524288 bytes.  The
Momchil> worst case would be very large file with a few cached pages with
Momchil> offsets uniformly distributed across the whole file, that is having
Momchil> deep tree with only one page hanging off 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.

John> Again, benchmarks would be the good thing to see either way.

I've posted some with 2.4.