Messages in this thread | | | Subject | Re: [PATCH] Radix-tree pagecache for 2.5 | From | Momchil Velikov <> | Date | 31 Jan 2002 16:21:48 +0200 |
| |
>>>>> "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 - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |