[lkml]   [2002]   [Jan]   [31]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
    SubjectRe: [PATCH] Radix-tree pagecache for 2.5
    >>>>> "Josh" == Josh MacDonald <jmacd@CS.Berkeley.EDU> writes:

    Josh> Quoting Momchil Velikov (
    >> >>>>> "John" == John Stoffel <> 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

    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.

    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to
    More majordomo info at
    Please read the FAQ at

     \ /
      Last update: 2005-03-22 13:16    [W:0.023 / U:2.616 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site