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

[Matthieu Monrocq]

Le 7 avril 2012 14:03, Philip Ashmore <contact at philipashmore.com> a écrit :

> On 07/04/12 03:42, Sean Silva wrote:
> > I've got a little bit for everybody:
> >
> > Howard: I completely understand your points. By no means did I intend
> > this code in its current form to get into libc++, it was mostly just
> > an experiment. I would not myself advocate this code change without
> > clear evidence of a performance win.
> >
> > Chandler: perf is a really good tool for monitoring this stuff. There
> > are a lot of low-level performance considerations, and measuring is
> > the only way to really evaluate this kind of change. Also I think
> > there are more "macro" optimizations to be made to the rebalancing
> > code to reduce branches and branch mispredicts, bringing me to...
> >
> > Joerg: wow, that code is insane. the author really groks the red-black
> > tree algorithms like nothing that I've ever seen before (not even
> > CLRS). For example in the insert rebalancing, they put the Case 1
> > recoloring in the loop by itself. Case 2 and 3 for are put *outside*
> > the loop, which makes so much sense since Case 2 and 3 only execute
> > exactly once (if at all), since the tree is balanced after that code
> > runs. Also, their use of an array to hold the left and right nodes is
> > beautiful! I though I was clever with the pointer-to-members, but the
> > array version is simpler, and to boot they can use the result of
> > comparisons like (father == grandpa->rb_right) directly to index which
> > one to use.
> >
> > Yet another case in the field of computing where a more-complicated
> > solution (pointer to members to determine left and right) has a
> > better, simpler solution.
> >
> > Dave: from the point of view of code understandability, the current
> > code is probably about as good as it gets, since it is essentially a
> > mirror image in code in the CLRS algorithms book, which to my
> > knowledge is where pretty much everybody learns how red-black trees
> > work (and uses as a reference for the rb-tree algorithms).
> > Unfortunately, the CLRS code is more theoretically oriented and their
> > "programming language" for the algorithms lacks many of the more
> > powerful capabilities that real computers have, such as dynamically
> > choosing offsets for member access. Actually, my original inspiration
> > for this was the "else" branch in RB-Insert-Fixup, which simply says
> > "(same as then branch but with left and right reversed)".
> >
> > I have to say, that netbsd red-black tree has really piqued my
> > interest. Two other red-black trees I have seen "in the wild"---the
> > linux one and the nginx one---also follow the more to-the-book
> > implementation like libc++'s; perhaps this is because the netbsd-like
> > code has no significant advantage? Or maybe it is simply obscurity of
> > this approach? idk, but I think I'm going to end up writing at least a
> > couple red-black trees in order to test this.... fun...
> If that's not enough fun, have you considered comparing your red-black
> tree implementations with other tree implementations, say avl-trees?
>
> I'm on Debian amd64 if you need to run your tests on different hardware.
>
> I'll even give writing the avl-tree performance tests a whirl, once you
> show me how you run the perf tests with red-black trees - a tar ball I
> can unpack and "make check" with is all I need.
>
> Yes, I've got a vested interest in this - my treedb project in
> SourceForge uses avl-trees and I'd like to add red-black-trees in at
> some stage :)
>
>
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...

--Matthieu.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20120407/de030b3b/attachment.html>