I'm currently hanging up on splay trees. I.e., I'm hacking one together
in my non-copious free time. Their theoretical properties sound great
(automatic cache-style migration of often used nodes + linear tree
building time for ordered builds + easy code for splicing). I've not
yet measured anything.
Who knows, might just work.
> Personally, _neither_ the fuzzy hash nor AVL's are going back right now,
> and if anything does make it into 2.2 it would probably be AVL's just
> because the code has been so well tested in 2.0.x.
The AVL code is messy and huge, but I do agree.
AVL + 1 VMA cache sounds like the best bet.
Fuzzy hash sounds like an interesting idea, but tests have shown it sucks :-)
-- Jaie
-
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/faq.html