From: Ralf Stephan <gtrwst9@gmail.com>
Date: Thu, 31 Dec 2015 15:36:46 +0000 (+0100)
Subject: cache pseries coeff accesses in pseries::mul_series.
X-Git-Tag: release_1-7-0~7^2~25
X-Git-Url: https://www.ginac.de/ginac.git//ginac.git?p=ginac.git;a=commitdiff_plain;h=2c8d5b298c5354c32514c4d5e52cfc80e8b32fbd

cache pseries coeff accesses in pseries::mul_series.

Coeff is too general as long as we have only ints as exponents.
This patch fixes a potentially cubic slowdown.
---

diff --git a/ginac/pseries.cpp b/ginac/pseries.cpp
index cc756ac4..8f267e8d 100644
--- a/ginac/pseries.cpp
+++ b/ginac/pseries.cpp
@@ -823,11 +823,11 @@ ex pseries::mul_series(const pseries &other) const
 	
 	// Series multiplication
 	epvector new_seq;
-	int a_max = degree(var);
-	int b_max = other.degree(var);
-	int a_min = ldegree(var);
-	int b_min = other.ldegree(var);
-	int cdeg_min = a_min + b_min;
+	const int a_max = degree(var);
+	const int b_max = other.degree(var);
+	const int a_min = ldegree(var);
+	const int b_min = other.ldegree(var);
+	const int cdeg_min = a_min + b_min;
 	int cdeg_max = a_max + b_max;
 	
 	int higher_order_a = std::numeric_limits<int>::max();
@@ -836,18 +836,30 @@ ex pseries::mul_series(const pseries &other) const
 		higher_order_a = a_max + b_min;
 	if (is_order_function(other.coeff(var, b_max)))
 		higher_order_b = b_max + a_min;
-	int higher_order_c = std::min(higher_order_a, higher_order_b);
+	const int higher_order_c = std::min(higher_order_a, higher_order_b);
 	if (cdeg_max >= higher_order_c)
 		cdeg_max = higher_order_c - 1;
-	
+
+	std::map<int, ex> rest_map_a, rest_map_b;
+	for (const auto& it : seq)
+		rest_map_a[ex_to<numeric>(it.coeff).to_int()] = it.rest;
+
+	if (other.var.is_equal(var))
+		for (const auto& it : other.seq)
+			rest_map_b[ex_to<numeric>(it.coeff).to_int()] = it.rest;
+
 	for (int cdeg=cdeg_min; cdeg<=cdeg_max; ++cdeg) {
 		ex co = _ex0;
 		// c(i)=a(0)b(i)+...+a(i)b(0)
 		for (int i=a_min; cdeg-i>=b_min; ++i) {
-			ex a_coeff = coeff(var, i);
-			ex b_coeff = other.coeff(var, cdeg-i);
-			if (!is_order_function(a_coeff) && !is_order_function(b_coeff))
-				co += a_coeff * b_coeff;
+			const auto& ita = rest_map_a.find(i);
+			if (ita == rest_map_a.end())
+				continue;
+			const auto& itb = rest_map_b.find(cdeg-i);
+			if (itb == rest_map_b.end())
+				continue;
+			if (!is_order_function(ita->second) && !is_order_function(itb->second))
+				co += ita->second * itb->second;
 		}
 		if (!co.is_zero())
 			new_seq.push_back(expair(co, numeric(cdeg)));