Messages in this thread | | | Date | Mon, 29 Nov 1999 18:38:25 +0100 | From | Manfred Spraul <> | Subject | Re: AVL trees vs. Red-Black trees |
| |
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/
| |