Re: [GiNaC-cvs] ginac flags.h mul.cpp power.cpp
CVS Service wrote:
Update of /home/cvs/GiNaC/ginac by vollinga
Modified Files: Tag: ginac_1-4 flags.h mul.cpp power.cpp Log Message: Synced to HEAD: - This helps mul::expand() and friends to recognize objects which have no indices at all [Sheplyakov].
Chris, We are curious what can be done about the performance regression one of your patches for dummy index renaming introduced. The seemingly innocuous patch has been identified by Jens and Alexei: <http://www.ginac.de/pipermail/ginac-list/2007-September/001215.html>. At first, the above log message suggested to me that the problem has been dealt with. But that is not so: The program is still extremely slow. In fact, Alexei's patches are entirely unrelated. Since neither an explanation of what's happening nor a fix has been suggested, we would really appreciate some expert insight by you. Thanks in advance -richy. -- Richard B. Kreckel <http://www.ginac.de/~kreckel/>
Hello! On Mon, Oct 15, 2007 at 11:28:22PM +0200, Richard B. Kreckel wrote:
CVS Service wrote:
Update of /home/cvs/GiNaC/ginac by vollinga
Modified Files: Tag: ginac_1-4 flags.h mul.cpp power.cpp Log Message: Synced to HEAD: - This helps mul::expand() and friends to recognize objects which have no indices at all [Sheplyakov].
At first, the above log message suggested to me that the problem has been dealt with. But that is not so: The program is still extremely slow. In fact, Alexei's patches are entirely unrelated.
I admit my patches don't solve the problem for noncommutative products. But they are not "entirely unrelated".
Since neither an explanation of what's happening
The same problem as my patches address: ncmul ctor and ncmul::expand() try to rename the indices even if the expression has no indices at all.
nor a fix has been suggested,
I've tried to fix them in the same way as mul::expand (see the patch in the end of this mail), but this somehow breaks the clifford class, so `make check' barks at me: examining clifford objects.....Error: caught exception remove_dirac_ONE(): expression is a non-scalar Clifford number! [PATCH] Attempt to fix ncmul performance regression due to dummy indices renaming. Do not even try to rename dummy indices if the expression has no indices at all. BIG RED WARNING: this breaks clifford.cpp. --- ginac/ncmul.cpp | 47 ++++++++++++++++++++++++++--------------------- 1 files changed, 26 insertions(+), 21 deletions(-) diff --git a/ginac/ncmul.cpp b/ginac/ncmul.cpp index 3712329..eb659b4 100644 --- a/ginac/ncmul.cpp +++ b/ginac/ncmul.cpp @@ -124,18 +124,19 @@ bool ncmul::info(unsigned inf) const return inherited::info(inf); } -typedef std::vector<int> intvector; +typedef std::vector<std::size_t> uintvector; ex ncmul::expand(unsigned options) const { + const bool skip_idx_rename = info(info_flags::has_indices); // First, expand the children std::auto_ptr<exvector> vp = expandchildren(options); const exvector &expanded_seq = vp.get() ? *vp : this->seq; // Now, look for all the factors that are sums and remember their // position and number of terms. - intvector positions_of_adds(expanded_seq.size()); - intvector number_of_add_operands(expanded_seq.size()); + uintvector positions_of_adds(expanded_seq.size()); + uintvector number_of_add_operands(expanded_seq.size()); size_t number_of_adds = 0; size_t number_of_expanded_terms = 1; @@ -167,40 +168,44 @@ ex ncmul::expand(unsigned options) const exvector distrseq; distrseq.reserve(number_of_expanded_terms); - intvector k(number_of_adds); + uintvector k(number_of_adds); /* Rename indices in the static members of the product */ exvector expanded_seq_mod; size_t j = 0; exvector va; - for (size_t i=0; i<expanded_seq.size(); i++) { - if (i == positions_of_adds[j]) { - expanded_seq_mod.push_back(_ex1); - j++; - } else { - expanded_seq_mod.push_back(rename_dummy_indices_uniquely(va, expanded_seq[i], true)); + if (! skip_idx_rename) { + for (size_t i=0; i<expanded_seq.size(); i++) { + if (i == positions_of_adds[j]) { + expanded_seq_mod.push_back(_ex1); + j++; + } else { + expanded_seq_mod.push_back(rename_dummy_indices_uniquely(va, expanded_seq[i], true)); + } } } - while (true) { - exvector term = expanded_seq_mod; - for (size_t i=0; i<number_of_adds; i++) { - term[positions_of_adds[i]] = rename_dummy_indices_uniquely(va, expanded_seq[positions_of_adds[i]].op(k[i]), true); - } + size_t l = number_of_adds - 1; + do { + exvector term = skip_idx_rename ? expanded_seq : expanded_seq_mod; + for (size_t i=0; i<number_of_adds; i++) + term[positions_of_adds[i]] = skip_idx_rename ? expanded_seq[positions_of_adds[i]].op(k[i]) : + rename_dummy_indices_uniquely(va, expanded_seq[positions_of_adds[i]].op(k[i]), true); distrseq.push_back((new ncmul(term, true))-> setflag(status_flags::dynallocated | (options == 0 ? status_flags::expanded : 0))); // increment k[] - int l = number_of_adds-1; - while ((l>=0) && ((++k[l]) >= number_of_add_operands[l])) { + l = number_of_adds-1; + while ((++k[l]) >= number_of_add_operands[l]) { k[l] = 0; - l--; + if (l == 0) + break; + else + --l; } - if (l<0) - break; - } + } while (l > 0); return (new add(distrseq))-> setflag(status_flags::dynallocated | (options == 0 ? status_flags::expanded : 0)); -- 1.5.3.2 Best regards, Alexei -- All science is either physics or stamp collecting.
"ASh" == Alexei Sheplyakov <varg@theor.jinr.ru> writes: ASh> I've tried to fix them in the same way as mul::expand (see the ASh> patch in the end of this mail), but this somehow breaks the ASh> clifford class, so `make check' barks at me:
Unfortunately I will not have a chance to examine it closer till this weekend at least.... -- Vladimir V. Kisil email: kisilv@maths.leeds.ac.uk -- www: http://maths.leeds.ac.uk/~kisilv/
Hello, Alexei, On 10/16/07, Alexei Sheplyakov <varg@theor.jinr.ru> wrote:
I've tried to fix them in the same way as mul::expand (see the patch in the end of this mail), but this somehow breaks the clifford class,
Actually, the patch introduces problems which are not specific to clifford.cpp. In the self-check errors start from color.cpp, see the relevant portion of check/exams.out file below. Could your patch breaks simplification of indexed object somehow? By the way, I failed to apply your patch through the command patch -p1 < p.diff What is the correct way to apply it? Best wishes, Vladimir ----------indexed objects: (no output) ----------color objects: simplify_indexed(T.a*T.b*T.c*T.k*T.a*T.k*T.c*T.b)--1/162*ONE erroneously returned -7/18*ONE instead of 0 ----------clifford objects: (-4*D*ldotq+8*ldotq) - (-4*D*ldotq+4*D*m^2+8*ldotq-4*l^2*D+8*l^2) erroneously returned -4*D*m^2+4*l^2*D-8*l^2 instead of 0 (4*ldotq*q^2) - (4*m^2*q^2+8*ldotq^2-4*l^2*q^2+4*ldotq*q^2) erroneously returned -4*m^2*q^2-8*ldotq^2+4*l^2*q^2 instead of 0 (4*D*eta~rho~lam*eta~sig~nu-4*D*eta~rho~nu*eta~sig~lam-8*eta~nu~lam*eta~sig~rho+8*eta~rho~lam*eta~sig~nu-8*eta~rho~nu*eta~sig~lam-4*D*eta~nu~lam*eta~sig~rho) - (0) erroneously returned 4*D*eta~rho~lam*eta~sig~nu-4*D*eta~rho~nu*eta~sig~lam-8*eta~nu~lam*eta~sig~rho+8*eta~rho~lam*eta~sig~nu-8*eta~rho~nu*eta~sig~lam-4*D*eta~nu~lam*eta~sig~rho instead of 0 (16*eta~sig~rho-8*D*eta~sig~rho) - (0) erroneously returned 16*eta~sig~rho-8*D*eta~sig~rho instead of 0 (4*D^2*eta~sig~rho+16*eta~sig~rho) - (0) erroneously returned 4*D^2*eta~sig~rho+16*eta~sig~rho instead of 0 simplify_indexed(e~mu*e~nu*e.nu*e.mu) - (4*ONE) erroneously returned 2*(e~mu*e~nu)*[[-1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]].mu.nu instead of 0 simplify_indexed(e~mu*e~nu*e.mu*e.nu) - (2*(e~mu*e~nu)*[[-1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]].mu.nu-4*ONE) erroneously returned -8*ONE instead of 0 simplify_indexed(e.mu*e~nu*e~mu*e.nu) - (-4*ONE+2*(e.mu*e.nu)*[[-1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]]~nu~mu) erroneously returned -8*ONE instead of 0 simplify_indexed((4*ONE+2*(e~nu*e~rho)*[[-1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]].nu.rho)*e~mu+2*(e~nu*e~rho*e~mu)*[[-1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]].nu.rho-4*e.nu*[[-1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]]~mu~nu) - (-4*e~rho*[[-1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]]~mu.rho+4*e~nu*[[-1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]]~mu.rho*[[-1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]].nu~rho+4*e~mu-4*e~nu*[[-1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]]~mu.nu) erroneously returned 8*e.1 instead of 0 for mu=1 simplify_indexed((4*ONE+2*(e~nu*e~rho)*[[-1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]].nu.rho)*e~mu+2*(e~nu*e~rho*e~mu)*[[-1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]].nu.rho-4*e.nu*[[-1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]]~mu~nu) - (-4*e~rho*[[-1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]]~mu.rho+4*e~nu*[[-1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]]~mu.rho*[[-1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]].nu~rho+4*e~mu-4*e~nu*[[-1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]]~mu.nu) erroneously returned 8*e.1 instead of 0 for mu=1
Hello! On Sun, Oct 21, 2007 at 01:26:45PM +0100, Vladimir V. Kisil wrote:
Actually, the patch introduces problems which are not specific to clifford.cpp. In the self-check errors start from color.cpp, see the relevant portion of check/exams.out file below. Could your patch breaks simplification of indexed object somehow?
Yep. That patch is somewhat insane, here is the [more] correct (i.e. `make check' does not report any errors) one: [PATCH] Attempt to fix ncmul performance regression due to dummy indices renaming. Do not rename dummy indices if the object has no indices at all. --- ginac/ncmul.cpp | 36 ++++++++++++++++++++++-------------- 1 file changed, 22 insertions(+), 14 deletions(-) diff --git a/ginac/ncmul.cpp b/ginac/ncmul.cpp index 3712329..34f2c7b 100644 --- a/ginac/ncmul.cpp +++ b/ginac/ncmul.cpp @@ -124,18 +124,19 @@ bool ncmul::info(unsigned inf) const return inherited::info(inf); } -typedef std::vector<int> intvector; +typedef std::vector<std::size_t> uintvector; ex ncmul::expand(unsigned options) const { + const bool skip_idx_rename = ! info(info_flags::has_indices); // First, expand the children std::auto_ptr<exvector> vp = expandchildren(options); const exvector &expanded_seq = vp.get() ? *vp : this->seq; // Now, look for all the factors that are sums and remember their // position and number of terms. - intvector positions_of_adds(expanded_seq.size()); - intvector number_of_add_operands(expanded_seq.size()); + uintvector positions_of_adds(expanded_seq.size()); + uintvector number_of_add_operands(expanded_seq.size()); size_t number_of_adds = 0; size_t number_of_expanded_terms = 1; @@ -167,7 +168,7 @@ ex ncmul::expand(unsigned options) const exvector distrseq; distrseq.reserve(number_of_expanded_terms); - intvector k(number_of_adds); + uintvector k(number_of_adds); /* Rename indices in the static members of the product */ exvector expanded_seq_mod; @@ -176,30 +177,37 @@ ex ncmul::expand(unsigned options) const for (size_t i=0; i<expanded_seq.size(); i++) { if (i == positions_of_adds[j]) { + // XXX: could anyone explain why this is necessary? expanded_seq_mod.push_back(_ex1); j++; } else { - expanded_seq_mod.push_back(rename_dummy_indices_uniquely(va, expanded_seq[i], true)); + expanded_seq_mod.push_back(skip_idx_rename ? expanded_seq[i] : + rename_dummy_indices_uniquely(va, expanded_seq[i], true)); } } - while (true) { + bool show_must_go_on = true; + while (show_must_go_on) { exvector term = expanded_seq_mod; - for (size_t i=0; i<number_of_adds; i++) { - term[positions_of_adds[i]] = rename_dummy_indices_uniquely(va, expanded_seq[positions_of_adds[i]].op(k[i]), true); - } + for (size_t i=0; i<number_of_adds; i++) + term[positions_of_adds[i]] = skip_idx_rename ? + expanded_seq[positions_of_adds[i]].op(k[i]) : + rename_dummy_indices_uniquely(va, expanded_seq[positions_of_adds[i]].op(k[i]), true); distrseq.push_back((new ncmul(term, true))-> setflag(status_flags::dynallocated | (options == 0 ? status_flags::expanded : 0))); // increment k[] - int l = number_of_adds-1; - while ((l>=0) && ((++k[l]) >= number_of_add_operands[l])) { + size_t l = number_of_adds - 1; + while ((++k[l]) >= number_of_add_operands[l]) { k[l] = 0; - l--; + if (l == 0) { + show_must_go_on = false; + break; + } + else + --l; } - if (l<0) - break; } return (new add(distrseq))-> -- 1.5.3.2
By the way, I failed to apply your patch through the command
patch -p1 < p.diff
Interesting. Both patches work for me (TM), that is, I can apply them to current HEAD (and ginac_1-4) with patch -p1.
What is the correct way to apply it?
patch -p1 < that_file.diff Best regards, Alexei -- All science is either physics or stamp collecting.
Hello, Alexei,
"AS" == Alexei Sheplyakov <varg@theor.jinr.ru> writes: AS> Yep. That patch is somewhat insane, here is the [more] correct AS> (i.e. `make check' does not report any errors) one:
I tried the patch on my two large programs with Clifford numbers: no problems are observed. I did not collect the official benchmarks but some speed-up also presents. Best wishes, Vladimir -- Vladimir V. Kisil email: kisilv@maths.leeds.ac.uk -- www: http://maths.leeds.ac.uk/~kisilv/
participants (4)
-
Alexei Sheplyakov
-
Richard B. Kreckel
-
Vladimir Kisil
-
Vladimir V. Kisil