C++ compile and execution times

[Mike Stump]

On Thursday, November 21, 2002, at 07:38 PM, Roger Sayle wrote:
>> On Thursday, November 21, 2002, at 05:37 PM, Roger Sayle wrote:
>>> The problem I've noticed is that the recursion in "fold" appears
>>> to be O(n^2) instead of O(n).
>>
>> I don't believe it is.  Try it out.  I think one the first ply is
>> folded, thus limiting the amount of work done.
>
> I believe it really is O(n^2).

No, honest.  I don't think it is.  The typical fold code looks like 
this:

       else if (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<')
	return fold (build (COND_EXPR, type, arg0,
			    fold (build1 (code, type, integer_one_node)),
			    fold (build1 (code, type, integer_zero_node))));

In this case, notice that there is only one fold per pre-built node.
Three nodes, three folds, this is linear.

> Given a unary-tree, even if each level is actually transformed only 
> once,
> fold will still retraverse the levels below it confirming that nothing 
> can
> be done.  So in a tree/list N-levels deep, the leaf will be checked N 
> times
> (the level above that N-1 etc...).  It takes a synthetic example, such 
> as
> (((A+-B)+-C)+-D)+-E to show it, but big-O notation is for the worst 
> case.

In that case,  we have:

     case MINUS_EXPR:
       /* A - (-B) -> A + B */
       if (TREE_CODE (arg1) == NEGATE_EXPR)
	return fold (build (PLUS_EXPR, type, arg0, TREE_OPERAND (arg1, 0)));

Notice there can only be one extra call to fold per node, that's linear.

The cleaverness of fold, and why it isn't a problem comes from the fact 
the
folder does one ply of work on only the top most part of the tree.  It 
is
only ever necessary to play with the top, as we know that fold had 
_already_
been called while constructing the tree for lower layers, thus 
obviating any
need to search deeper into the tree.  If you were right, the code would 
look
like:

       else if (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<')
	return fold (build (COND_EXPR, type, fold(arg0),
			    fold (build1 (code, type, integer_one_node)),
			    fold (build1 (code, type, integer_zero_node))));
and

     case MINUS_EXPR:
       /* A - (-B) -> A + B */
       if (TREE_CODE (arg1) == NEGATE_EXPR)
	return fold (build (PLUS_EXPR, type, fold(arg0), fold(TREE_OPERAND 
(arg1, 0))));

but, it doesn't look like that, ever.  Also, if you were right, we'd 
never need
to fold as we build, just once after it was all built.  But, we 
_always_ fold
everytime we build, and any builder that doesn't, is a missed 
opportunity, never
to be re-visited.

And last, if you want, measure the worse case test case, and see if it 
is linear
(in fold), double the size, and see if fold takes twice as long, or 
four times as long.