I do, actually, tried expanding vectorized operations into explicit for loops, and computing vector multiplication / vector norm in BLAS interfaces. For explicit loops, it did allocate less memory, but took much more time. Meanwhile, the vectorized version which I've been get used to write runs incredibly fast, as the following tests indicates:
# Explicit for loop, slightly modified from SimilarityMetric.jl by johnmyleswhite (https://github.com/johnmyleswhite/SimilarityMetrics.jl/blob/master/src/cosine.jl) function cosine(a::SparseMatrixCSC{Float64, Int64}, b::SparseMatrixCSC{Float64, Int64}) sA, sB, sI = 0.0, 0.0, 0.0 for i in 1:length(a) sA += a[i]^2 sI += a[i] * b[i] end for i in 1:length(b) sB += b[i]^2 end return sI / sqrt(sA * sB) end # BLAS version function cosine_blas(i::SparseMatrixCSC{Float64, Int64}, j::SparseMatrixCSC{Float64, Int64}) i = full(i) j = full(j) numerator = BLAS.dot(i, j) denominator = BLAS.nrm2(i) * BLAS.nrm2(j) return numerator / denominator end # the vectorized version remains the same, as the 1st post shows. # Test functions function test_explicit_loop(d) for n in 1:10000 v = d[:,1] cosine(v,v) end end function test_blas(d) for n in 1:10000 v = d[:,1] cosine_blas(v,v) end end function test_vectorized(d) for n in 1:10000 v = d[:,1] cosine_vectorized(v,v) end end test_explicit_loop(mat) test_blas(mat) test_vectorized(mat) gc() @time test_explicit_loop(mat) gc() @time test_blas(mat) gc() @time test_vectorized(mat) # Results elapsed time: 3.772606858 seconds (6240080 bytes allocated) elapsed time: 0.400972089 seconds (327520080 bytes allocated, 81.58% gc time) elapsed time: 0.011236068 seconds (34560080 bytes allocated) On Monday, November 10, 2014 7:23:17 PM UTC+8, Milan Bouchet-Valat wrote: > > Le dimanche 09 novembre 2014 à 21:17 -0800, Todd Leo a écrit : > > Hi fellows, > > > > I'm currently working on sparse matrix and cosine similarity > computation, but my routines is running very slow, at least not reach my > expectation. So I wrote some test functions, to dig out the reason of > ineffectiveness. To my surprise, the execution time of passing two vectors > to the test function and passing the whole sparse matrix differs greatly, > the latter is 80x faster. I am wondering why extracting two vectors of the > matrix in each loop is dramatically faster that much, and how to avoid the > multi-GB memory allocate. Thanks guys. > > > > -- > > BEST REGARDS, > > Todd Leo > > > > # The sparse matrix > > mat # 2000x15037 SparseMatrixCSC{Float64, Int64} > > > > # The two vectors, prepared in advance > > v = mat'[:,1] > > w = mat'[:,2] > > > > # Cosine similarity function > > function cosine_vectorized(i::SparseMatrixCSC{Float64, Int64}, > j::SparseMatrixCSC{Float64, Int64}) > > return sum(i .* j)/sqrt(sum(i.*i)*sum(j.*j)) > > end > > I think you'll experience a dramatic speed gain if you write the sums in > explicit loops, accessing elements one by one, taking their product and > adding it immediately to a counter. In your current version, the > element-wise products allocate new vectors before computing the sums, which > is very costly. > > This will also get rid of the difference you report between passing arrays > and vectors. > > > Regards > > function test1(d) > > res = 0. > > for i in 1:10000 > > res = cosine_vectorized(d[:,1], d[:,2]) > > end > > end > > > > function test2(_v,_w) > > res = 0. > > for i in 1:10000 > > res = cosine_vectorized(_v, _w) > > end > > end > > > > test1(dtm) > > test2(v,w) > > gc() > > @time test1(dtm) > > gc() > > @time test2(v,w) > > > > #elapsed time: 0.054925372 seconds (59360080 bytes allocated, 59.07% gc > time) > > #elapsed time: 4.204132608 seconds (3684160080 bytes allocated, 65.51% > gc time) > > >
