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

[Dave Abrahams]

on Thu Apr 05 2012, Howard Hinnant <hhinnant-AT-apple.com> wrote:

> 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.
>
> 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.  

Well, I wasn't looking for an answer that's any more "proper" than your
statement above that the current code is easier to reason about and
maintain.  It's OK with me if you don't feel like sticking your neck out
further on this one without something more solid to look at, but while
that project does sound like a lot of fun, it was a mostly-idle question
and I don't have time to take it on at the moment.

Cheers,

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com