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

[Howard Hinnant]

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.

Howard