Skip to content

Performance of Inplace Addition #73

@David-Berghaus

Description

@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?

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions