Re: AVL trees vs. Red-Black trees

David Wragg (dpw@doc.ic.ac.uk)
29 Nov 1999 20:29:04 +0000


Jamie Lokier <lkd@tantalophile.demon.co.uk> writes:
> Olivier Galibert wrote:
> > On Sun, Nov 28, 1999 at 05:44:22PM +0100, Jamie Lokier wrote:
> > > 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.
> >
> > Beware of compilers reordering things under your feet, though.
>
> cf. recent threads on reordering. Auch! I still don't understand the
> Intel rules.

The Intel rules don't really matter for core kernel code. We still
have to support architectures with more weakly ordered memory models,
such as Alpha (and the publically released info on IA64 suggests it
falls into this category too). So to ensure things happen in the right
order you need to put in the memory barriers, and these tend to be
about as expensive as spinlocks without contention.

What would be neat: A compiler that understood the memory model of the
target architecture, and could automatically insert memory barriers
where needed based on simple annotations of variables.

David Wragg

-
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/