Re: black_count

[Nathan Myers <ncm@best.com>]

Can it have escaped everyone that __black_count is not really 
a recursive function at all?  It is easily rewritten as a loop.

Here is how I rewrote it, once, and put it in the CVS tree:

inline int
__black_count(_Rb_tree_node_base* __node, _Rb_tree_node_base* __root,
              int __sum = 0)
{
  if (__node == 0)
    return __sum;
  __sum += (__node->_M_color == _S_rb_tree_black) ? 1 : 0;
  return (__node == __root) ?
    __sum : __black_count(__node->_M_parent, __root, __sum);
}

An ordinary loop would work better, as it wouldn't keep comparing 
__node to zero when we know already that it's not zero:

inline int
__black_count(_Rb_tree_node_base* __node, _Rb_tree_node_base* __root)
{
  if (__node == 0)
    return 0;
  int __sum = 0;
  do {
    if (__node->_M_color == _S_rb_tree_black) ++__sum;
    if (__node == __root) break;
    __node = __node->_M_parent;
  } while (1);
  return __sum;
}

Apparently my rewrite got washed out by an SGI update containing 
the original version.  I had sent it to Matt, but it appears he
tossed it.

This is not the limit of possible improvements.  It is only called 
from two places, both in one other function.  Only in the first use 
can __node be zero, so that test is better moved to the calling site.
After that change, the recursive and iterative versions should result 
in identical instruction sequences, given reasonably good optimization.

Either way, to me,
    if (__node->_M_color == _S_rb_tree_black) ++__sum;
is clearer than
    __sum += (__node->_M_color == _S_rb_tree_black) ? 1 : 0;
and depends less on the often-fractious optimizer.

Nathan Myers
ncm@cantrip.org

-------------------------
Benjamin wrote:
> I'm in favor of this patch, and will check it in, with the added argument,
> later today unless I hear strong objections.
> 
> On Tue, 6 Jul 1999, Nick Rasmussen wrote:
> Benjamin wrote:  

> > > Nick, can you please elaborate a bit more on your patch? Codegen
> > > snippets of this with and without the patch, with and without the arg
> > > would be welcome. ..
> > Here is the code generated in the three cases (without the patch, with
> > the patch using a default argument, with the patch using two functions).
> > 
> > I also put the patch and some source files showing the three cases at 
> > http://jive.org/~nick/black_count.tar.gz
> > 
> > The output here and on the website is from egcs-1.1.2 (my gcc-2.95 testing
> > box is at home).  Results with gcc-2.95 (from CVS two nights ago) were
> > similar, probably the same.
> > 
> > The real solution, of course, would be to improve the optimizer so that
> > all three cases produce the same code, but given my scanty knowledge
> > of the egcs codebase, it's a bit beyond my abilities.
> > [assembly output follows]
>