Messages in this thread | | | Date | Thu, 21 Jan 1999 18:09:33 +0000 | From | Alan Mimms <> | Subject | Re: 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/
| |