conv is slower than necessary

[sloisel]

It seems that conv is slower than necessary. By implementing a naive convolution, I am able to outperform conv for moderate vector sizes. On my particular machine, naive convolution is better than conv if the product of vector sizes is less than 100 000.

Just so everyone sees what the naive solution is, I'm pasting it below.

slowconvcost(m,n) = 2e-9*m*n+1e-6
fastconvcost(m,n) = 7e-8*(m+n)*log(m+n)+1e-4
function sebconv{T}(a::Array{T}, b::Array{T})
    m = length(a)
    n = length(b)
    if(fastconvcost(m,n)<slowconvcost(m,n)) return conv(a,b); end
    c = zeros(T,m+n-1)
    @inbound for j=1:m
        for k=1:n
            c[j+k-1] += a[j]*b[k]
        end
    end
    return c
end

Here is a performance plot:

Edit: tweaked code for better heuristic as to when slowconv is faster than fastconv.

[simonster]

You can also use filt(y, 1, [x; zeros(length(y)-1)]) to perform convolution, where x is the longer of the two vectors and y is the shorter one.

DSP.jl has an implementation of filt that decides whether or not to use the FFT algorithm based on the vector lengths. The FFT algorithm in DSP.jl should also be a little more efficient than conv when one vector is much longer than the other, since it does overlap-save. I guess we could move that here, but that seems contrary to #5155.

[sloisel]

filt seems to run slightly slower than naive convolution. I've tested that my switching heuristic (between naive and FFT) above seems to be the correct one at all scales.

function anotherconv{T}(x::Array{T},y::Array{T})
    if(length(y)>length(x))
        foo = x
        x = y
        y = foo
    end
    return filt(y, 1, [x; zeros(length(y)-1)])
end

[dehann]

FYI: recent work at MIT Accelerated Convolutions for Efficient Multi-Scale Time to Contact Computation in Julia
(link to pdf on arxiv) of which the implementation should be available somewhere. First author repos seem empty though. aamini/FastConv.jl and issue aamini/TimeToContact.jl#1.

Maybe you already know about this and have it wrapped in, but I can't find it and then this pointer might be useful to others also.

[aamini]

Thanks for the mention. Both packages have been updated.
Fast convolutions for Julia: amini/FastConv.jl
Time to Contact in Julia: amini/TimeToContact.jl

[KristofferC]

Moved to JuliaDSP/DSP.jl#167