lkml.org 
[lkml]   [1999]   [Jan]   [21]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    SubjectRe: arca-vm-26
    Andrea Arcangeli wrote:

    > On Thu, 21 Jan 1999, Heinz Mauelshagen wrote:
    >
    > > - buffermem is 200M of my 256M system afterwards
    > > - minimum swap.
    > > - lots of system time searching the buffer cache with
    > > commands afterwards.
    >
    > so the problem is just only the ~O(n) search in the buffer cache right?
    >
    > > - commands running 50 to 100!!! times slower than before filling buffercache
    >
    > No this is a workaround of the problem I think that right now I should
    > enlarge the buffer hash table of the buffer headers for high memory
    > machines.
    >
    > Really I think that for the long run I should start dropping the cache and
    > buffer hashes replacing them with RB-trees to work fine everywhere without
    > waste some base memory with fuzzy hash tables. I think that doing that
    > everything should scale _far_ better also under the scenario you are
    > describing.
    >
    > Comments from David? (note RB-trees != AVL ;).
    >
    > Andrea Arcangeli
    >
    > -
    > To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    > the body of a message to majordomo@vger.rutgers.edu
    > Please read the FAQ at http://www.tux.org/lkml/

    Andrea, et al,

    I do not wish to start a religious war about data structures. Have you considered
    the relatively new data structure called a 'skip list'? I have replaced several
    subsystems in our system at work that would have been ready candidates for AVL or
    RB trees (or any of a cast of thousands of others) with skiplists to very good
    effect in insertion, deletion and search speed. I would be happy to supply
    pointers if you're interested. The code is trivial compared to any other tree
    management scheme I know. Skiplists maintain balance and give O(log2 N)
    performance for insert, delete AND search. There are variants that have no
    pathologically bad performance under any circumstances. However, I believe it's
    pretty safe to use the statistically "good" versions rather than slighly slower
    overall and more complicated but garanteed behavior ones for the purposes you're
    talking about.

    a



    -
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.rutgers.edu
    Please read the FAQ at http://www.tux.org/lkml/

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