[lkml]   [1999]   [Jan]   [21]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
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
> Please read the FAQ at

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.


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

 \ /
  Last update: 2005-03-22 13:49    [W:0.043 / U:3.844 seconds]
©2003-2018 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site