Re: [GiNaC-devel] [PATCH] gcd: fix heuristics to chose main variable properly
[adding ginac-devel to CC] On Tue, Nov 21, 2006 at 09:28:13AM +0100, Bernard Parisse wrote:
BTW, I checked your example with the gcd code of my giac library, it takes less than 3s. to normalize on a Intel(R) Pentium(R) M processor 1.60GHz, how long does it take with your patched ginac version?
[on a Pentium 4 3GHz box] $ g++ -O2 -march=pentium4 -finline-limit=1200 thepoly_another.cpp -o thepoly_another -lginac $ time ./thepoly_another >/dev/null 2>&1 real 0m7.846s user 0m7.836s sys 0m0.008s With unpatched GiNaC it takes way to long (after several days of calculation I get bored and killed the process). Best regards, Alexei -- All science is either physics or stamp collecting.
"ASh" == Alexei Sheplyakov <varg@theor.jinr.ru> writes:
ASh> real 0m7.846s user 0m7.836s sys 0m0.008s ASh> With unpatched GiNaC it takes way to long (after several days ASh> of calculation I get bored and killed the process). I also have examples of the same code which may run either few seconds or infinity. Is gcd the only source in GiNaC of such behaviour? Best wishes, Vladimir -- Vladimir V. Kisil email: kisilv@maths.leeds.ac.uk -- www: http://maths.leeds.ac.uk/~kisilv/
Hi, On Tue, Nov 21, 2006 at 01:32:32PM +0000, Vladimir Kisil wrote:
I also have examples of the same code which may run either few seconds or infinity.
Could you please show such an example?
Is gcd the only source in GiNaC of such behaviour?
I suspect there are few others too. In particular, collect() is _very_ inefficient when the argument is a sparse multivariate polynomial. (I've got a patch, but I need to do more tests before submitting it). But gcd and other polynomial operations which make use of it (normal, collect_common_factors) are the most ugly ones :( Best regards, Alexei -- All science is either physics or stamp collecting.
"ShA" == Sheplyakov Alexei <varg@theor.jinr.ru> writes: >> I also have examples of the same code which may run either few >> seconds or infinity. ShA> Could you please show such an example?
I do not have a short example. What I met is a part of a rather big program (cs.MS/0512073), specifically the chunk which check conformality of different distances. It uses series expansion of a fraction of two multi-variable polynomials so it can be either gcd() or collect() which cause infinite execution, I guess. Surprisingly infinite execution occurs only on my office computer but never at home, although they both have quite similar hardware configuration (Athlons 2800 and 3000). Best wishes, Vladimir -- Vladimir V. Kisil email: kisilv@maths.leeds.ac.uk -- www: http://maths.leeds.ac.uk/~kisilv/
On Tue, Nov 21, 2006 at 04:20:37PM +0000, Vladimir Kisil wrote:
I do not have a short example. What I met is a part of a rather big program (cs.MS/0512073),
I couldn't compile it (see the attached log), what I'm doing wrong? $ g++ --version | head -n 1 g++ (GCC) 4.1.2 20061028 (prerelease) (Debian 4.1.1-19) $ ginac-config --version 1.3.5 This is not really GiNaC 1.3.5, but rather my hijacked version, but the API is the same.
specifically the chunk which check conformality of different distances. It uses series expansion of a fraction of two multi-variable polynomials so it can be either gcd() or collect() which cause infinite execution, I guess.
AFAIK, no series() method uses gcd() on its own. But there are a couple of normal() (which obviously uses gcd()) in your code, so I guess bad gcd() performance might be the root of the problem. The patches I've posted (last month and yesterday) might solve it.
Surprisingly infinite execution occurs only on my office computer
Could you please show the backtrace? Or maybe print the expression before calling normal() and post it here?
but never at home, although they both have quite similar hardware configuration (Athlons 2800 and 3000).
This makes me think about compiler bugs/wrong compilation options, etc. Are you sure the software (first of all, the compiler) versions and compilation options are _exactly_ the same on machines in question? Best regards, Alexei -- All science is either physics or stamp collecting.
"ShA" == Sheplyakov Alexei <varg@theor.jinr.ru> writes: ShA> I couldn't compile it (see the attached log), what I'm doing ShA> wrong? ShA> $ ginac-config --version 1.3.5
I think that my library uses something from 1.4 (CVS) branch. ShA> Could you please show the backtrace? Or maybe print the ShA> expression before calling normal() and post it here? It may be indeed a compiler-related issue since such a behaviour disappeared a month ago (I am updating my Debian-testing distribution almost daily on both computers, thus, theoretically they should have the same soft). Another strange thing was that an insertion of few debug outputs makes the program finishes in a reasonable time. The infinite run resumed again after I again deleted all those silly cerr << 100 <<endl; statements. All of this is much beyond of my understanding. Best wishes, Vladimir -- Vladimir V. Kisil email: kisilv@maths.leeds.ac.uk -- www: http://maths.leeds.ac.uk/~kisilv/
Dear Alexei, Alexei Sheplyakov wrote:
[on a Pentium 4 3GHz box] $ g++ -O2 -march=pentium4 -finline-limit=1200 thepoly_another.cpp -o thepoly_another -lginac $ time ./thepoly_another >/dev/null 2>&1
real 0m7.846s user 0m7.836s sys 0m0.008s
With unpatched GiNaC it takes way to long (after several days of calculation I get bored and killed the process).
As a challenge, could you please have a look at the Lewis-Wester benchmarks M2, N, and O2 in files check/time_lw_M2.cpp, check/time_lw_N.cpp, and check/time_lw_M2.cpp, respectively? They all contain a boolean variable which is used to turn disable these tests. And they are all about GCDs. Some of them have never ever run to completion. BTW: May we assume that your little patch makes the GCD also much more memory effective? Regards -richy. -- Richard B. Kreckel <http://www.ginac.de/~kreckel/>
Richard B. Kreckel wrote:
As a challenge, could you please have a look at the Lewis-Wester benchmarks M2, N, and O2 in files check/time_lw_M2.cpp, check/time_lw_N.cpp, and check/time_lw_M2.cpp, respectively?
Sorry, the last file should've been check/time_lw_O.cpp. -richy. -- Richard B. Kreckel <http://www.ginac.de/~kreckel/>
participants (4)
-
Alexei Sheplyakov
-
Richard B. Kreckel
-
varg＠theor.jinr.ru
-
Vladimir Kisil