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

Dave Abrahams dave at boostpro.com
Thu Apr 5 11:12:02 PDT 2012

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.

Dave Abrahams
BoostPro Computing

More information about the cfe-dev mailing list