conv is slower than necessary

[KristofferC]

Moved from JuliaLang/julia#13996 (more discussion there)

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(a::Array{T}, b::Array{T}) where 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)
    @inbounds 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.

[ViralBShah]

There's still a large gap for small sizes:

julia> x = rand(100); y = rand(100);

julia> @btime sebconv($x, $y);
  1.429 μs (1 allocation: 1.77 KiB)

julia> @btime conv($x, $y);
  17.875 μs (18 allocations: 9.84 KiB)

[martinholters]

Ref. #545.