>>>>> "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/
This archive was generated by hypermail 2b29 : Thu Jan 31 2002 - 21:01:34 EST