Performance of Inplace Addition

[David-Berghaus]

Consider the two functions:

function add_terms(n)
    @ncpolyvar x[1:n]
    res = zero(Polynomial{false,Int64})
    for i = 1:n
        res += x[i]
    end
    return res        
end

function add_terms!(n)
    @ncpolyvar x[1:n]
    res = zero(Polynomial{false,Int64})
    for i = 1:n
        DynamicPolynomials.MA.mutable_operate!(+,res,x[i])
    end
    return res
end

These are some benchmarks:

julia> @btime add_terms(20)
  92.801 μs (1385 allocations: 105.70 KiB)
x₁ + x₂ + x₃ + x₄ + x₅ + x₆ + x₇ + x₈ + x₉ + x₁₀ + x₁₁ + x₁₂ + x₁₃ + x₁₄ + x₁₅ + x₁₆ + x₁₇ + x₁₈ + x₁₉ + x₂₀

julia> @btime add_terms!(20)
  124.900 μs (2393 allocations: 184.84 KiB)
x₁ + x₂ + x₃ + x₄ + x₅ + x₆ + x₇ + x₈ + x₉ + x₁₀ + x₁₁ + x₁₂ + x₁₃ + x₁₄ + x₁₅ + x₁₆ + x₁₇ + x₁₈ + x₁₉ + x₂₀

Let us now consider the case where we add terms that are already monomials:

function add_terms(n)
    @ncpolyvar x[1:n]
    res = sum(x)
    for i = 1:n
        res += x[i]
    end
    return res        
end

function add_terms!(n)
    @ncpolyvar x[1:n]
    res = sum(x)
    for i = 1:n
        DynamicPolynomials.MA.mutable_operate!(+,res,x[i])
    end
    return res
end

Which has benchmarks:

julia> @btime add_terms(20)
  207.300 μs (3763 allocations: 351.41 KiB)
2x₁ + 2x₂ + 2x₃ + 2x₄ + 2x₅ + 2x₆ + 2x₇ + 2x₈ + 2x₉ + 2x₁₀ + 2x₁₁ + 2x₁₂ + 2x₁₃ + 2x₁₄ + 2x₁₅ + 2x₁₆ + 2x₁₇ + 2x₁₈ + 2x₁₉ + 2x₂₀

julia> @btime add_terms!(20)
  244.400 μs (4953 allocations: 482.34 KiB)
2x₁ + 2x₂ + 2x₃ + 2x₄ + 2x₅ + 2x₆ + 2x₇ + 2x₈ + 2x₉ + 2x₁₀ + 2x₁₁ + 2x₁₂ + 2x₁₃ + 2x₁₄ + 2x₁₅ + 2x₁₆ + 2x₁₇ + 2x₁₈ + 2x₁₉ + 2x₂₀

All examples have been compiled with "-O2". I am suprised that for both examples, the inplace-addition turns out to be slower and causes more allocations. Do you have an idea what causes this?

[blegat]

Can you try with https://github.com/JuliaAlgebra/DynamicPolynomials.jl/pull/67/ ?

[David-Berghaus]

I directly installed the package from your repository (i.e., (@v1.4) pkg> add https://github.com/JuliaAlgebra/DynamicPolynomials.jl"), which, as far as I understand, should contain the updates of #67, but the benchmarks unfortunately remain the same...

[David-Berghaus]

Oh, I saw that you have not pushed the fixes yet, so I did add DynamicPolynomials#bl/add_term Now the results are different. For the first case we get:

julia> @btime add_terms(20)
  91.800 μs (1385 allocations: 105.70 KiB)
x₁ + x₂ + x₃ + x₄ + x₅ + x₆ + x₇ + x₈ + x₉ + x₁₀ + x₁₁ + x₁₂ + x₁₃ + x₁₄ + x₁₅ + x₁₆ + x₁₇ + x₁₈ + x₁₉ + x₂₀
julia> @btime add_terms!(20)
  69.599 μs (960 allocations: 67.52 KiB)
x₁ + x₂ + x₃ + x₄ + x₅ + x₆ + x₇ + x₈ + x₉ + x₁₀ + x₁₁ + x₁₂ + x₁₃ + x₁₄ + x₁₅ + x₁₆ + x₁₇ + x₁₈ + x₁₉ + x₂₀

And for the second one:

julia> @btime add_terms(20)
  154.199 μs (2330 allocations: 234.08 KiB)
2x₁ + 2x₂ + 2x₃ + 2x₄ + 2x₅ + 2x₆ + 2x₇ + 2x₈ + 2x₉ + 2x₁₀ + 2x₁₁ + 2x₁₂ + 2x₁₃ + 2x₁₄ + 2x₁₅ + 2x₁₆ + 2x₁₇ + 2x₁₈ + 2x₁₉ + 2x₂₀

julia> @btime add_terms!(20)
  102.900 μs (1540 allocations: 118.45 KiB)
2x₁ + 2x₂ + 2x₃ + 2x₄ + 2x₅ + 2x₆ + 2x₇ + 2x₈ + 2x₉ + 2x₁₀ + 2x₁₁ + 2x₁₂ + 2x₁₃ + 2x₁₄ + 2x₁₅ + 2x₁₆ + 2x₁₇ + 2x₁₈ + 2x₁₉ + 2x₂₀