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

Howard Hinnant hhinnant at apple.com
Thu Apr 5 11:40:20 PDT 2012


On Apr 5, 2012, at 2:12 PM, Dave Abrahams wrote:

> 
> on Thu Apr 05 2012, Howard Hinnant <hhinnant-AT-apple.com> wrote:
> 
>> On Apr 5, 2012, at 12:00 PM, Dave Abrahams wrote:
>> 
>>> 
>>> on Wed Apr 04 2012, Howard Hinnant <hhinnant-2kanFRK1NckAvxtiuMwx3w-AT-public.gmane.org> wrote:
>>> 
>>>> I don't believe code size is going to be a driver on this one as the
>>>> potential savings tops out in the neighborhood of 30 instructions
>>>> (which is small compared to the entire R/B tree container code).  The
>>>> bottom line is going to be performance.  Your rewrite is interesting,
>>>> but for me, significantly harder to read.  So it will have to motivate
>>>> with significant performance wins.  And if it does, I think
>>>> __tree_remove would benefit from the same treatment.  However if we're
>>>> looking at zero or marginal performance wins, then I favor the current
>>>> code: it is easier to reason about and maintain.
>>> 
>>> Really, even with the duplication of left/right logic?  Seems to me that
>>> if the code size reduction isn't a win and there are performance costs
>>> you could still improve maintainability while maintaining the current
>>> generated code structure by passing the member pointers as template arguments to a
>>> helper function template.
>> 
>> The libc++ code base is open source and I am happy to review patches.
> 
> Awww... I'm not trying to get you to change anything.  My question is
> whether you think it's better for maintainability (in this case?) to
> write out two totally symmetric branches with duplicated logic than it
> is to eliminate that duplication, and if so, why.  I could also take
> your response to mean "I really don't have time to deal with questions
> like that," which would be fine, too.

When I design code I often evaluate two or more versions of working, testable code, and then (hopefully) develop a favorite. When I have only one version of working and tested code in front of me, and if there are not customer complaints against that code, I generally tend to leave it alone (if it isn't broken don't fix it).

Even if I'm exploring hypothetical code, such as for teaching/presentation purposes, I generally write actual code to test my hypotheses.  I'm just not smart enough to fully evaluate different designs without testing, or relying on closely related tests that I've already performed.

To properly answer your question I would have to write an alternative version of the code in question.  So I'm asking you to pose your question in terms of alternative code I can study, instead of taking on the job myself of crafting that alternative.  Not only will this save me time.  It will also save you time when you have to review what I've tested only to discover that I misunderstood your English.  The compiler will ensure that your C++ is unambiguous.

Howard




More information about the cfe-dev mailing list