I've got a little bit for everybody:<div><br></div><div>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.</div>
<div><br></div><div>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...</div>
<div><br></div><div>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.<br>
<div><br></div><div>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.</div><div><br></div><div>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)".</div>
<div><br></div><div>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...<br>
<br><div class="gmail_quote">On Fri, Apr 6, 2012 at 1:01 PM, Dave Abrahams <span dir="ltr"><<a href="mailto:dave@boostpro.com">dave@boostpro.com</a>></span> wrote:<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"><br>
on Thu Apr 05 2012, Howard Hinnant <hhinnant-AT-apple.com> wrote:<br>
<br>
> On Apr 5, 2012, at 2:12 PM, Dave Abrahams wrote:<br>
><br>
>><br>
>> on Thu Apr 05 2012, Howard Hinnant <hhinnant-AT-apple.com> wrote:<br>
>><br>
>>> On Apr 5, 2012, at 12:00 PM, Dave Abrahams wrote:<br>
>>><br>
>>>><br>
>>>> on Wed Apr 04 2012, Howard Hinnant <<a href="http://hhinnant-2kanFRK1NckAvxtiuMwx3w-AT-public.gmane.org" target="_blank">hhinnant-2kanFRK1NckAvxtiuMwx3w-AT-public.gmane.org</a>> wrote:<br>
>>>><br>
>>>>> I don't believe code size is going to be a driver on this one as the<br>
>>>>> potential savings tops out in the neighborhood of 30 instructions<br>
>>>>> (which is small compared to the entire R/B tree container code).  The<br>
>>>>> bottom line is going to be performance.  Your rewrite is interesting,<br>
>>>>> but for me, significantly harder to read.  So it will have to motivate<br>
>>>>> with significant performance wins.  And if it does, I think<br>
>>>>> __tree_remove would benefit from the same treatment.  However if we're<br>
>>>>> looking at zero or marginal performance wins, then I favor the current<br>
>>>>> code: it is easier to reason about and maintain.<br>
>>>><br>
>>>> Really, even with the duplication of left/right logic?  Seems to me that<br>
>>>> if the code size reduction isn't a win and there are performance costs<br>
>>>> you could still improve maintainability while maintaining the current<br>
>>>> generated code structure by passing the member pointers as template arguments to a<br>
>>>> helper function template.<br>
>>><br>
>>> The libc++ code base is open source and I am happy to review patches.<br>
>><br>
>> Awww... I'm not trying to get you to change anything.  My question is<br>
>> whether you think it's better for maintainability (in this case?) to<br>
>> write out two totally symmetric branches with duplicated logic than it<br>
>> is to eliminate that duplication, and if so, why.  I could also take<br>
>> your response to mean "I really don't have time to deal with questions<br>
>> like that," which would be fine, too.<br>
><br>
</div></div><div class="im">> To properly answer your question I would have to write an alternative<br>
> version of the code in question.  So I'm asking you to pose your<br>
> question in terms of alternative code I can study, instead of taking<br>
> on the job myself of crafting that alternative.<br>
<br>
</div>Well, I wasn't looking for an answer that's any more "proper" than your<br>
statement above that the current code is easier to reason about and<br>
maintain.  It's OK with me if you don't feel like sticking your neck out<br>
further on this one without something more solid to look at, but while<br>
that project does sound like a lot of fun, it was a mostly-idle question<br>
and I don't have time to take it on at the moment.<br>
<br>
Cheers,<br>
<div class="im HOEnZb"><br>
--<br>
Dave Abrahams<br>
BoostPro Computing<br>
<a href="http://www.boostpro.com" target="_blank">http://www.boostpro.com</a><br>
</div><div class="HOEnZb"><div class="h5">_______________________________________________<br>
cfe-dev mailing list<br>
<a href="mailto:cfe-dev@cs.uiuc.edu">cfe-dev@cs.uiuc.edu</a><br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev</a><br>
</div></div></blockquote></div><br></div></div>