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