Open kalmarek opened 4 years ago
This is weird, MA should be much faster for this with less allocations. Does the issue persist if mt[i, j]
is replaced by i + (j - 1) * N
? EDIT it seems it does persist
https://github.com/JuliaAlgebra/DynamicPolynomials.jl/pull/65 solves one part of the performance issue but it's still slower.
The issue is that fill(zero(T), maximum(mt))
uses the same polynomial for every entry so it's slower because it modifies a large polynomial. You should use [zero(T) for i in 1:maximum(mt)]
for instance
@blegat thanks for investigating; interesting find: indeed v = fill(zero(T), 3)
results in identical (===
) entries, but modifying one unaliases it from the others (?). When using
function algebra_SOS(Q::AbstractMatrix{T}, mt::AbstractMatrix{<:Integer}) where T
# result = zeros(T, maximum(mt)) doesn't work
result = [zero(T) for _ in 1:maximum(mt)]
for i in 1:size(Q,2)
@views algebra_addmul!(result, Q[:,i], Q[:,i], mt)
end
end
I get the following timings:
0.026193 seconds (235.44 k allocations: 30.099 MiB, 17.03% gc time) # with add_mul!
0.015501 seconds (121.20 k allocations: 15.861 MiB) # with res[mt[i,j]] += X[i]*X[j]
Setup: (
mt
is a multiplication table of an algebra)and timings (on contrived example):
@blegat, @tweisser