Messages in this thread | | | Date | Sun, 28 Nov 1999 17:44:22 +0100 | From | Jamie Lokier <> | Subject | Re: AVL trees vs. Red-Black trees |
| |
Oliver Xymoron wrote: > > The self-adjusting property > > should theoretically provide cache-like behaviour when most of the > > lookups are to relatively few nodes in the tree. The downside is that > > the tree is modified by lookups. > > Unfortunately, that means that there's no way it can even begin to scale > on SMP - all "readers" need exclusive locks unless you can somehow > guarantee that there'll only ever be one reader/writer. In some instances, > it might make sense to have completely unlocked per-processor trees > mapping onto shared structures, but it seems a little painful.
I didn't investigate, but I have a feeling it's possible to do shared readers on these trees if the pointer changes are done in the right order.
-- Jamie
- 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/
| |