[GiNaC-devel] [PATCH] {add, power}::eval(): convert terms into primitive polynomials when possible.

[Richard B. Kreckel]

Hi!

Sheplyakov Alexei wrote:
>> This patch appears to come with a slight performance hit. 
> 
> Indeed, mul::eval() has more work to be done.
> 
> advantages:
> - subsequent operations, in particular gcd, are faster.
> - no more ugly stuff like (-x+y)*(x-y).
> 
> disadvantages:
> - subsequent operations, in particualr expand, may be slower.
> - there is some overhead in the trivial case, e.g. (x*y*z).eval().


It is not some overhead that worries me. Rather, it is the algorithmic 
complexity of the new overhead. The new transformation appears to 
introduce quadratic behavior at the eval() level. That's bad. One of the 
points of choosing the algorithms that are done at the eval() stage to 
be only subquadratic algorithms was that otherwise one might be unable 
to merely construct the ex object.


>> and Lewis-Wester test A from 0.055s to 0.22s.
> 
> Ouch. I do observe some slowdown (from 0.292s to 0.3s) too, but it is
> not *that* bad.
> 
>> (I'm seriously surprised by the latter since it only 
>> involves integers, but it's reproducible.)
> 
> a/b is actually mul(a, power(b, _ex_1)), and it has seq.size() >= 2.
> My patch adds empty loop over 2 elements, so there should be some slowdown.


Well, I still fail to see how that loop can make a measurable effect. 
But never mind this particular benchmark.


>> Looking at the code it appears to me like mul::eval recurses now. 
> 
> mul::eval calls evalchildren, so it is recursive even without my patch.


Well, but that recurses into *children* only! At the end of the loop 
that you introduced into mul::eval(), a new mul object is returned. It 
is not evaluated yet and enters mul::eval() again. And it might contain 
most of the original terms. This is an entirely different quantity of 
recursion that is responsible for potentially quadratic behavior, IINM.


>> Wouldn't it be faster to collect the coefficients in one sweep? 
> 
> I've tried this (see the patch [1]), it has almost no effect.


It still appears to be quadratic.  Must it really be quadratic?


>> Well, I recognize that most terms will be trivial in the following
>> recursions, but still.
> 
> My patch causes overhead even in the trivial case, e.g. when the
> polynomial is already unit normal. Consider e.g. 
> 
> e = (x+1)*(2*x^2+x+1)*...*(100*x^100+99*x^99+...+1);


Indeed. This expression is well suited to study the asymptotic behavior:

$ { echo -n "time((1+x)"; for i in $(seq 2 100); do echo -n "*(1+x"; for 
j in $(seq 2 $i); do echo -n "+${j}*x^${j}"; done; echo -n ")"; done; 
echo ");";} | ginsh-1.3.5
0.089994s
$ { echo -n "time((1+x)"; for i in $(seq 2 100); do echo -n "*(1+x"; for 
j in $(seq 2 $i); do echo -n "+${j}*x^${j}"; done; echo -n ")"; done; 
echo ");";} | ginsh-head
0.169989s
$ { echo -n "time((1+x)"; for i in $(seq 2 1000); do echo -n "*(1+x"; 
for j in $(seq 2 $i); do echo -n "+${j}*x^${j}"; done; echo -n ")"; 
done; echo ");";} | ginsh-1.3.5
11.4992s
$ { echo -n "time((1+x)"; for i in $(seq 2 1000); do echo -n "*(1+x"; 
for j in $(seq 2 $i); do echo -n "+${j}*x^${j}"; done; echo -n ")"; 
done; echo ");";} | ginsh-head
68.2522s



> mul::eval will do 100 of useless checks (each of them is relatively
> expansive on its own). Any ideas how to avoid this? E.g. what is 
> the best way to check if polynomial is already primitive (unit normal)?


Wild idea: If the primitive predicate becomes really important, would it 
help to cache it like it's done for the status_flags::expanded predicate 
inside basic::flags?  (Maybe using two bits to represent the tristate 
yes, no, unknown.)

Feel free to flame me if this idea is bogus for some reason.

Cheers
   -richy.
-- 
Richard B. Kreckel
<http://www.ginac.de/~kreckel/>