[cfe-dev] libc++ red-black tree: halving the branches

[Joerg Sonnenberger]

On Sat, Apr 07, 2012 at 03:28:05PM +0200, Matthieu Monrocq wrote:
> If we are speaking alternative implementations of std::map and co, does
> anyone know if a Skip List has ever been used to implement those ? They are
> in theory equivalent to red-black trees and avl trees, but use randomness
> instead of rebalancing which make them *much* simpler: you don't need a
> book to code them.
> 
> I have never heard about any performance comparison between the two though,
> and I am not really I could come up with an optimized implementation...

Skip list tend to be fairly bad for modern memory architectures,
especially in multi-threaded applications. The problem is that they result
in a lot of cache trashing, so they are only beneficial if you have a
really small hot set.

Joerg