Updating a dense vector by a sparse vector in Julia is slow

Question

I am using Julia version 0.4.5 and I am experiencing the following issue: As far as I know, taking inner product between a sparse vector and a dense vector should be as fast as updating the dense vector by a sparse vector. The latter one is much slower.

A = sprand(100000,100000,0.01)
w = rand(100000)

@time for i=1:100000
  w += A[:,i]
end
26.304380 seconds (1.30 M allocations: 150.556 GB, 8.16% gc time)

@time for i=1:100000
  A[:,i]'*w
end
0.815443 seconds (921.91 k allocations: 1.540 GB, 5.58% gc time)

I created a simple sparse matrix type of my own, and the addition code was ~ the same as the inner product.

Am I doing something wrong? I feel like there should be a special function doing the operation w += A[:,i], but I couldn't find it.

Any help is appreciated.

Answer 1

I asked the same question on GitHub and we came to the following conclusion. The type SparseVector was added as of Julia 0.4 and with it the BLAS function LinAlg.axpy!, which updates in-place a (possibly dense) vector x by a sparse vector y multiplied by a scalar a, i.e. performs x += a*y efficiently. However, in Julia 0.4 it is not implemented properly. It works only in Julia 0.5

@time for i=1:100000
  LinAlg.axpy!(1,A[:,i],w)
end
1.041587 seconds (799.49 k allocations: 1.530 GB, 8.01% gc time)

However, this code is still sub-optimal, as it creates the SparseVector A[:,i]. One can get an even faster version with the following function:

function upd!(w,A,i,c)
  rowval = A.rowval
  nzval = A.nzval
  @inbounds for j = nzrange(A,i)
    w[rowval[j]] += c* nzval[j]
  end
  return w
end

@time for i=1:100000
  upd!(w,A,i,1)
end
0.500323 seconds (99.49 k allocations: 1.518 MB)

This is exactly what I needed to achieve, after some research we managed to get there, thanks everyone!