Andi Kleen wrote:
> MOLNAR Ingo <mingo@valerie.inf.elte.hu> writes:
> > AFAIK David has some very cool single-strategy scheme for this whole vma
> > problem.
>
> Does this strategy involve a skip list?
I would definitely recommend a skip list or splay tree. Both are very
fast. Both are very short code. (_Much_ shorter and simpler than the
AVL code was).
The skip list has the advantage that it's fairly simple to code and
nothing is written (cache advantage).
It has the gross disadvantage that it requires a random number
generator source which can keep up with the rate at which we can form
new vma's. This is why we won't be using this, I like skip lists too
for some of their beautiful properties, but the random number source
requirement completely annuls all the benefits.
Solaris uses skip lists, let them lose. (they in fact lose even
moreso because they dynamically switch from
single-list+one-behind-cache to skip lists depending upon the number
of mmaps an address space has, as Ingo has mentioned that has a lot of
problems).
I did a lot of research into this, and the fuzzy hash scheme was
superior to anything else I have ever seen on the planet. It is the
only hash scheme (to my knowledge) which is cheap to implement _and_
works when the search involves comparing two keys against an input key
for each object in the hash chains (ie. a range, no other hash scheme
can deal with ranges, traditional hashes can deal with only exact
single key 'equal' comparisons per object).
Later,
David S. Miller
davem@dm.cobaltmicro.com
-
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.altern.org/andrebalsa/doc/lkml-faq.html