{"action":"created","issue":{"url":"https://api.github.com/repos/JuliaLang/julia/issues/16069","repository_url":"https://api.github.com/repos/JuliaLang/julia","labels_url":"https://api.github.com/repos/JuliaLang/julia/issues/16069/labels{/name}","comments_url":"https://api.github.com/repos/JuliaLang/julia/issues/16069/comments","events_url":"https://api.github.com/repos/JuliaLang/julia/issues/16069/events","html_url":"https://github.com/JuliaLang/julia/issues/16069","id":151358135,"number":16069,"title":"Updating a dense vector by a column of sparse matrix is slow","user":{"login":"cedeerwe","id":11530208,"avatar_url":"https://avatars.githubusercontent.com/u/11530208?v=3","gravatar_id":"","url":"https://api.github.com/users/cedeerwe","html_url":"https://github.com/cedeerwe","followers_url":"https://api.github.com/users/cedeerwe/followers","following_url":"https://api.github.com/users/cedeerwe/following{/other_user}","gists_url":"https://api.github.com/users/cedeerwe/gists{/gist_id}","starred_url":"https://api.github.com/users/cedeerwe/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/cedeerwe/subscriptions","organizations_url":"https://api.github.com/users/cedeerwe/orgs","repos_url":"https://api.github.com/users/cedeerwe/repos","events_url":"https://api.github.com/users/cedeerwe/events{/privacy}","received_events_url":"https://api.github.com/users/cedeerwe/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/JuliaLang/julia/labels/performance","name":"performance","color":"d7e102"},{"url":"https://api.github.com/repos/JuliaLang/julia/labels/sparse","name":"sparse","color":"fad8c7"}],"state":"closed","locked":false,"assignee":null,"milestone":null,"comments":5,"created_at":"2016-04-27T11:00:32Z","updated_at":"2016-04-27T13:44:45Z","closed_at":"2016-04-27T13:43:04Z","body":"I am trying to tackle this problem for a long time now, and there really seems to be an issue. As a subroutine in my method, I need to add a multiple of a column of a sparse matrix to a vector. \r\n\r\nIn the following simple test code I will do this operation with every column, to showcase the average behaviour.\r\n```\r\nn = 10000\r\nA = sprand(n,n,0.01)\r\nw = rand(n)\r\n@time for i=1:n\r\n  w += A[:,i]\r\nend\r\n0.260738 seconds (148.47 k allocations: 1.511 GB, 17.83% gc time)\r\n```\r\nSeems like a reasonable time, until we compare it to taking the same amount of inner products, which should take ~ the same time according to the sparse matrix theory\r\n```\r\n@time for i=1:n\r\n  A[:,i]'*w\r\nend\r\n0.013407 seconds (108.47 k allocations: 21.167 MB, 18.72% gc time)`\r\n```\r\nNow we see, that it is actually quite slow. I looked for the BLAS function axpy, which should do exactly this operation. It is implemented for sparse vectors, so I tested it out.\r\n```\r\n@time for i=1:n\r\n  LinAlg.axpy!(1,A[:,i],w)\r\nend\r\n2.813774 seconds (128.47 k allocations: 38.695 MB, 0.10% gc time)\r\n```\r\nThat is even slower. So I made my own implementation of this operation in the function upd!(w,A,i,c), which updates w by a c-multiple of the i-th column of A:\r\n```\r\nfunction upd!(w,A,i,c)\r\n  for j=A.colptr[i]:A.colptr[i+1]-1\r\n    w[A.rowval[j]] += A.nzval[j]*c\r\n  end\r\n  return w\r\nend\r\n```\r\nThe implementation is very basic, with no optimization. However, running this code is way faster.\r\n```\r\n@time for i=1:n\r\n  upd!(w,A,i,1)\r\nend\r\n0.003673 seconds (28.98 k allocations: 609.078 KB)\r\n```\r\nThere should not be such a difference. I believe there is an issue somewhere, but cannot figure out where. Maybe there is a function, which does this correctly, but after couple of days I could not find it. Am I missing something? "},"comment":{"url":"https://api.github.com/repos/JuliaLang/julia/issues/comments/215087705","html_url":"https://github.com/JuliaLang/julia/issues/16069#issuecomment-215087705","issue_url":"https://api.github.com/repos/JuliaLang/julia/issues/16069","id":215087705,"user":{"login":"KristofferC","id":1282691,"avatar_url":"https://avatars.githubusercontent.com/u/1282691?v=3","gravatar_id":"","url":"https://api.github.com/users/KristofferC","html_url":"https://github.com/KristofferC","followers_url":"https://api.github.com/users/KristofferC/followers","following_url":"https://api.github.com/users/KristofferC/following{/other_user}","gists_url":"https://api.github.com/users/KristofferC/gists{/gist_id}","starred_url":"https://api.github.com/users/KristofferC/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/KristofferC/subscriptions","organizations_url":"https://api.github.com/users/KristofferC/orgs","repos_url":"https://api.github.com/users/KristofferC/repos","events_url":"https://api.github.com/users/KristofferC/events{/privacy}","received_events_url":"https://api.github.com/users/KristofferC/received_events","type":"User","site_admin":false},"created_at":"2016-04-27T13:44:45Z","updated_at":"2016-04-27T13:44:45Z","body":"Sorry, I have been running stuff on julia 0.5 where the situation is a bit different. The sparse vector functionality only came in julia v0.4 and you are right that axpy seems to be slow on v0.4. However, what I said still apply, your original function will create a copy and thus be slow."}}