[lkml]   [1998]   [Sep]   [18]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
SubjectRe: AVL and hash in memory management
   Date: Thu, 17 Sep 1998 21:19:43 +0200 (CEST)
From: Rik van Riel <>

On Tue, 15 Sep 1998, David S. Miller wrote:

> It is an interesting data structure, thanks for presenting it.
> But it still has one of the fundamental problems we were trying to
> remove by going to a non-tree mechanism, the balancing cost.

Now that I think of it, is the balancing cost important
in the common case? When we have only 4 to 6 VMAs, we
won't be balancing that much.

The current fork+exit latency is humming close to ~200usec on the
UltraSparc, every cycle counts at this point.

And when we have hundreds of VMAs, doesn't the lookup
cost completely dwarf the balancing cost? The benchmarks
we've seen the last few weeks seem to suggest so...

Research work shows that only at around 1000 entires does the lookup
speed make up for the balancing cost of a tree.

David S. Miller

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:44    [W:0.068 / U:0.964 seconds]
©2003-2018 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site