Re: AVL trees vs. Red-Black trees

Andrea Arcangeli (andrea@suse.de)
Tue, 30 Nov 1999 17:18:30 +0100 (CET)


On Tue, 30 Nov 1999, Oliver Xymoron wrote:

>know what the lowest common denominator was. What is the weakest ordering
>model the kernel will support?

About stability: the weakest ordering supported right now is the Alpha
where both reads and writes can be reordered.

About performance: the most finegriend barriers we have exported to common
code are the most finegriend for the Alpha but according to the
spin_unlock thread on l-k, the IA32 SMP system could implement a barrier
that only avoids things to be moved from up to down but that would allow
further speculative reads to be moved before the barrier. Such kind of
barrier could be implemented by doing a dummy write on the next free stack
slot. I don't think it would make sense to export to common code such an
half barrier and I believe it worth to only use it for implementing the
spin_unlock internally as we are just doing since 2.3.30pre3.

So basically the current common denominator seems just fine to me.

Andrea

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