> 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/