[GiNaC-devel] ncmul regression [Was: Re: [GiNaC-cvs] ginac flags.h mul.cpp power.cpp]

[Alexei Sheplyakov]

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.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 827 bytes
Desc: Digital signature
Url : http://www.cebix.net/pipermail/ginac-devel/attachments/20071016/c6103c86/attachment.pgp