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@Uni-Mainz.DE> <http://wwwthep.physik.uni-mainz.de/~kreckel/>