Possible memory leak? (was: update on fast mult benchmark (fwd))

[Richard B. Kreckel]

Hi,

On Sat, 23 Mar 2002, Pearu Peterson wrote:
> I have tried to run Richard Fateman's multiplication benchmark also with
> GiNaC (1.0.2,1.0.6) but unsuccefully because expand() method starts to eat
> large amounts of memory so that I had to kill the process. 
> 
> Could this indicate a possible memory leak in GiNaC? Any other ideas? Here
> is my test program:
> 
> #include <ginac/ginac.h>
> using namespace GiNaC;
> int main()
> {
>   symbol x("x"), y("y"), z("z");
>   ex r = (ex(power(1 + x + y + z, 20 ))).expand();
>   ex r1 = r+1;
>   ex m = (r*r1).expand();
>   return 0;
> }

Incidentally, we have had this problem before.  See the message 
<http://www.ginac.de/lists/ginac-devel/msg00062.html> and the following
one.  That has been solved then, but the test by Richard Fateman shows
clearly that there are other problematic cases.

What happens?  The above test runs when you give it one GigaByte.  And
there is no memory-leak, because you can run it infinitely many times.
If we look at GiNaC's memory footprint of the final result, it becomes
obvious that its representation is quite competitive, too.

The culprit is mul::expand(), where two expanded polynomials (class
add), one with n1 terms and another with n2 terms are first written out by
brute force in an n1*n2 vector.  This is then returned through an add
constructor which sorts it (calling expairseq::canonize()) and then
compacitifies it (calling expairseq::combine_same_terms_sorted_seq()).

For two large input polynomials this is clearly bogus, because it does not
allow for early cancellations.  It was done this way because the compexity
of sorting is asymptotically ideal (n*log(n) comparisons).  This seems
to have been a short-sighted decision.

I can think of a gazillion ways how to repair this and will try to provide
a fix really soon now.  It needs some careful balancing, however.  
(Incidentally, I already had some trial-code in my private tree which
performs much better.)

To me it appears that this test per se does not tell us very much about
representation.  Besides questions of representation, the actual
implementation of expand() might differ between the systems compared by
Richard Fateman.  In particular, I am amazed to see the difference between
Maple, Mathematica and MuPAD being so tiny.  This contradicts my own
experience with handling polynomials in these three systems.  The pattern
t(MuPAD) > t(Maple) > t(Mma) looks reasonable, but the differnece is
usually *much* bigger.

Geez, and we thought polynomial expansion was trivial...

Regards
     -richy.

PS: Richard: 1234567890 < (2^31)-1, on page 1, third paragraph.
-- 
Richard B. Kreckel
<Richard.Kreckel at Uni-Mainz.DE>
<http://wwwthep.physik.uni-mainz.de/~kreckel/>