Performance issues #3
Description
I've started looking into what it will take to make MultivariatePolynomials fast as a general-purpose polynomial tool. Specifically, I'm trying to focus on variable substitution for now. Currently, it's pretty slow:
@polyvar x y
p = x + y + 2x^2 + y^3
vars = [x, y]
vals = [1.0, 2.0]calling p(vals, vars) takes around 3 microseconds.
I've gotten that down to about 270 nanoseconds in #2, but doing any better will require some internal changes (by comparison, MultiPoly takes about 70 nanoseconds on the same test).
I think the fundamental problem is that we evaluate polynomials by iterating over the Terms in the polynomial. But that iteration requires constructing a new Term type for each element, which in turn has to allocate new Vectors of monomials and powers. That gets expensive and slow. Ideally, we should be able to evaluate a polynomial with zero allocations at all.
One way we could possibly achieve this is by changing the polynomial types to just store a vector of Terms, rather than constructing a new Term when we iterate. Is there a reason that wasn't done already? Does it make some other part of the code more difficult?