Re: C++ compile and execution times

[Roger Sayle <roger at eyesopen dot com>]

Hi Mike,
> Please see my previous email on the topic.
> http://gcc.gnu.org/ml/gcc/2002-08/msg00717.html  Net result, 0.03%
> speedup.  Not worth it, in general.  Feel free to update the patches
> and try it on your benchmark.  Maybe you can find code that shows a
> much better improvement.

Oopps!  Yep, that's exactly the sort of patch I was thinking of.
All credit to Mike, it looks like this isn't performance critical
after all.  At least I can sleep easier knowing that my numerous
constant folding improvements haven't been the source of the slow
down :>


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

Fortunately, your timings show that this happens so infrequently in
practice that it isn't an issue.  Must be something else going on in
expand.  Many thanks again for easing my pangs of guilt.

Roger
--