gawk bug

[John H. DuBois III]

$ time gawk 'BEGIN{j=1; j^=-1; print j}'
1

real 0m9.62s
user 0m9.60s
sys 0m0.01s

$ time gawk 'BEGIN{j=1; j=j^-1; print j}'
1

real 0m0.00s
user 0m0.00s
sys 0m0.00s

Note the large amount of cpu time consumed in the ^= case. These numbers are
from gawk-3.1.4k built with gcc 2.95.3 under SCO OpenServer 5.0.6a on a Xeon
system. Similar results occur with all versions of gawk back through at least
2.15. Similar results also obtained with gawk 3.1.3 and 3.1.4k built with gcc
3.3.5 under Gentoo Linux on a Pentium III.

John

[Andrew J. Schorr]

Post by John H. DuBois III
$ time gawk 'BEGIN{j=1; j^=-1; print j}'
1
user 0m9.60s
$ time gawk 'BEGIN{j=1; j=j^-1; print j}'
1
user 0m0.00s

Interesting. The difference is in the Node_assign_exp vs. Node_exp
code in eval.c.

For Node_exp, it says:

case Node_exp:
if ((lx = x2) == x2 && lx >= 0) { /* integer exponent */
if (lx == 0)
x = 1;
else if (lx == 1)
x = x1;
else {
/* doing it this way should be more precise */
for (x = x1; --lx; )
x *= x1;
}
} else
x = pow((double) x1, (double) x2);
return tmp_number(x);

Whereas for Node_assign_exp, it says:

if ((ltemp = rval) == rval) { /* integer exponent */
if (ltemp == 0)
*lhs = make_number((AWKNUM) 1);
else if (ltemp == 1)
*lhs = make_number(lval);
else {
/* doing it this way should be more precise */
for (t1 = t2 = lval; --ltemp; )
t1 *= t2;
*lhs = make_number(t1);
}
} else
*lhs = make_number((AWKNUM) pow((double) lval, (double) rval));


The difference is that Node_exp checks for a non-negative exponent, whereas
Node_assign_exp omits that check. So the 'for' loop takes quite some time
to run.

Note that using a large integer exponent also takes a lot of time:

bash-2.05b$ time gawk 'BEGIN{j=1; j=j^2000000000; print j}'
1

real 0m4.120s
bash-2.05b$ time gawk 'BEGIN{j=1; j^=2000000000; print j}'
1

real 0m4.133s

A quick patch for the original problem would be to change the Node_assign_exp
code to check for a non-negative exponent.

But beyond that, I think there are 2 issues here: 1. the same function should
be used in both places; and 2. the exponentiation algorithm is not very good,
instead exponentiation by squaring should be used:

http://en.wikipedia.org/wiki/Exponentiation_by_squaring

Regards,
Andy

[Andrew J. Schorr]

Post by Andrew J. Schorr
But beyond that, I think there are 2 issues here: 1. the same function should
be used in both places; and 2. the exponentiation algorithm is not very good,
http://en.wikipedia.org/wiki/Exponentiation_by_squaring

Give the attached patch a try. It uses exponentiation by squaring for
all integral exponents. And it does so without recursion.

Regards,
Andy

[John H. DuBois III]

Looks good - in all of the tests I've run it works perfectly!

John

Post by Andrew J. Schorr

Post by Andrew J. Schorr
But beyond that, I think there are 2 issues here: 1. the same function should
be used in both places; and 2. the exponentiation algorithm is not very good,
http://en.wikipedia.org/wiki/Exponentiation_by_squaring

Give the attached patch a try. It uses exponentiation by squaring for
all integral exponents. And it does so without recursion.
Regards,
Andy

[Aharon Robbins]

-=-=-=-=-=-

Post by Andrew J. Schorr
But beyond that, I think there are 2 issues here: 1. the same function should
be used in both places; and 2. the exponentiation algorithm is not very good,
http://en.wikipedia.org/wiki/Exponentiation_by_squaring

Give the attached patch a try. It uses exponentiation by squaring for
all integral exponents. And it does so without recursion.
Regards,
Andy

I've applied the patch, after some minor edits. In the future, please
also supply a ChangeLog entry with your patches; that makes my life
easier.

Thanks!

Thanks also to John for pointing out the bug in the first place.

Arnold