Re: AVL trees vs. Red-Black trees

Manfred Spraul (manfreds@colorfullife.com)
Mon, 29 Nov 1999 18:38:25 +0100


Jamie Lokier wrote:
>
> > Beware of compilers reordering things under your feet, though.
>
> cf. recent threads on reordering. Auch! I still don't understand the
> Intel rules.
>

I'll try to explain them (for cacheable memory):

1) writes are never reordered, ie if your asm code writes variable
A before writing B, then it's guaranteed that all CPU's see these write
operations in that order.

2) reads are reordered among themselves.
(ie "mov (%0),%%eax; mov(%1),%%ebx" could appear in reverse order on the
memory bus)

3) "read A, store B" is always executed in order, ie the "store B"
is not visible on the memory bus before the "read A" has finished.
(*)

4) "store B,read A" can (and will) be executed in reverse order.
(**)

5) if the CPU sees a "lock;", "xchg", "in", "out" or any serializing
instruction, then it reevaluates all speculative reads that the cpu
has made.

You can find the details in the Intel Software Developer's Manual,
Vol 3, Chapter "7.2.2" (Memory Ordering in the P6 Family Processors)
and Vol 1, 2.5.5 (Retirement Unit: Intel found the least obvious place
to document one important detail ;)

But: DO NOT USE THESE RULES. Aways use spinlock() to synchronize your
data, because RISC cpu's use a weaker ordering.

Cheers,
Manfred

(*) This means that we can use a normal "mov" during "spin_unlock()".
(**) This means that we need the memory barrier in set_current_state().

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