Re: AVL trees vs. Red-Black trees

Oliver Xymoron (oxymoron@waste.org)
Mon, 29 Nov 1999 21:52:49 -0600 (CST)


On Tue, 30 Nov 1999, Andrea Arcangeli wrote:

> On Tue, 30 Nov 1999, Gerard Roudier wrote:
>
> >> "movl $0,%0\n\t"
> >> "movl $0,%1\n\t"
> >> "lock; addl $0,(%%esp)\n\t" /* flush our write buffers*/
> >
> >The 'lock' flushes write buffers of CPU2 to the cache, but:
>
> The lock there make no difference, I suggest to delete such last line as
> it's misleading IMHO.

The comment should instead read "memory barrier". It's there because it's
modeling existing code. It should arguably be modified there to a barrier
that is a non-existent on x86 if it actually needs a barrier at all. It
should only make a difference in timing, which will become less
deterministic - buffers get flushed opportunistically.

I've just tried it - the crash point does indeed become more sporadic.

At any rate, we have to figure out the rules we're going to use for the
portable kernel and not focus so much on the x86 details. It's not
immediately obvious where memory barriers should go on the generic system
so it might be nice if someone laid down the minimum ordering assumptions
for potential target machines.

Do we assume that processors always see their own local writes in program
order (locally fully ordered)? Does the bus always see writes in order
(write ordered)? Other processors (processor ordered)? Do we try to hide
all the interprocessor races inside a small set of macros like
set_current_state?

--
 "Love the dolphins," she advised him. "Write by W.A.S.T.E.." 

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