{"action":"created","issue":{"url":"https://api.github.com/repos/JuliaLang/julia/issues/19518","repository_url":"https://api.github.com/repos/JuliaLang/julia","labels_url":"https://api.github.com/repos/JuliaLang/julia/issues/19518/labels{/name}","comments_url":"https://api.github.com/repos/JuliaLang/julia/issues/19518/comments","events_url":"https://api.github.com/repos/JuliaLang/julia/issues/19518/events","html_url":"https://github.com/JuliaLang/julia/pull/19518","id":193937482,"number":19518,"title":"generic broadcast/broadcast! for sparse matrices, with #19372 semantics","user":{"login":"Sacha0","id":5799177,"avatar_url":"https://avatars.githubusercontent.com/u/5799177?v=3","gravatar_id":"","url":"https://api.github.com/users/Sacha0","html_url":"https://github.com/Sacha0","followers_url":"https://api.github.com/users/Sacha0/followers","following_url":"https://api.github.com/users/Sacha0/following{/other_user}","gists_url":"https://api.github.com/users/Sacha0/gists{/gist_id}","starred_url":"https://api.github.com/users/Sacha0/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Sacha0/subscriptions","organizations_url":"https://api.github.com/users/Sacha0/orgs","repos_url":"https://api.github.com/users/Sacha0/repos","events_url":"https://api.github.com/users/Sacha0/events{/privacy}","received_events_url":"https://api.github.com/users/Sacha0/received_events","type":"User","site_admin":false},"labels":[{"id":94575532,"url":"https://api.github.com/repos/JuliaLang/julia/labels/sparse","name":"sparse","color":"fad8c7","default":false},{"id":418435319,"url":"https://api.github.com/repos/JuliaLang/julia/labels/vectorization","name":"vectorization","color":"1d76db","default":false}],"state":"closed","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":15,"created_at":"2016-12-07T01:56:01Z","updated_at":"2016-12-13T20:20:39Z","closed_at":"2016-12-13T04:22:48Z","pull_request":{"url":"https://api.github.com/repos/JuliaLang/julia/pulls/19518","html_url":"https://github.com/JuliaLang/julia/pull/19518","diff_url":"https://github.com/JuliaLang/julia/pull/19518.diff","patch_url":"https://github.com/JuliaLang/julia/pull/19518.patch"},"body":"This pull request provides (1) a new `broadcast`/`broadcast!` implementation specialized for a pair of (input) sparse matrices, and (2) a general `broadcast`/`broadcast!` implementation capable of efficiently handling an arbitrary number of sparse matrices (within compiler limits). This pull request also integrates these `broadcast`/`broadcast!` methods with the new `map`/`map!` implementation specialized for sparse matrices, and touches up a few rough edges of the latter.\r\n\r\nThe semantics of these `broadcast!` methods are those discussed in #19372. Notably these `broadcast!` methods only allocate when strictly necessary, so for example\r\n```julia\r\njulia> C = spzeros(5,5); A = speye(5); B = sparse(Bidiagonal(zeros(5), ones(4), true));\r\n\r\njulia> @allocated broadcast!(*, C, A, B) # after warmup\r\n0\r\n```\r\nAdditionally, where these `broadcast!` methods do allocate, they do so *slightly* less pessimistically than the existing `broadcast!` methods. [1]\r\n\r\n(Edited) For operations that yield zero when at least one argument is zero (like `*`), the new `broadcast`/`broadcast!` methods specialized for a pair of (input) sparse matrices achieve substantially better performance than corresponding existing `broadcast`/`broadcast!` methods (despite performing slightly more work to enable more precise allocation behavior).\r\n\r\n(Edited) For operations that yield zero only when all arguments are zero (like `+`), the new `broadcast`/`broadcast!` methods specialized for a pair of (input) sparse matrices achieve performance comparable to corresponding existing `broadcast`/`broadcast!` methods. The former win in some cases and the latter in others, with runtime differences usually within ~30% in (hopefully realistic) tests.\r\n\r\nThe general `broadcast`/`broadcast!` methods achieve performance not too far behind the new methods specialized for pairs of (input) sparse matrices. The former take from 1% to 80% again the latter's runtime, with performance for small matrices falling in the middle to slower half of that range, and performance for large matrices falling in the faster quarter to faster half of that range.\r\n\r\nRelevant to #16285 and friends as a (near-final?) step in the sparse `broadcast`/`broadcast!` overhaul. Best!\r\n\r\n[1] `broadcast`/`broadcast!` could allocate still less pessimistically, but whether the additional code complexity would be worth the improvement is not clear. An extreme example: `broadcast[!]` operations that both allocate and involve one-by-one sparse matrices allocate enough storage for a dense result, though that often isn't necessary. Implementing smarter behavior for that case is straightforward but complicates the code somewhat, and `broadcast`ing with one-by-one sparse matrices seems like a marginal case.\r\n"},"comment":{"url":"https://api.github.com/repos/JuliaLang/julia/issues/comments/266850323","html_url":"https://github.com/JuliaLang/julia/pull/19518#issuecomment-266850323","issue_url":"https://api.github.com/repos/JuliaLang/julia/issues/19518","id":266850323,"user":{"login":"Sacha0","id":5799177,"avatar_url":"https://avatars.githubusercontent.com/u/5799177?v=3","gravatar_id":"","url":"https://api.github.com/users/Sacha0","html_url":"https://github.com/Sacha0","followers_url":"https://api.github.com/users/Sacha0/followers","following_url":"https://api.github.com/users/Sacha0/following{/other_user}","gists_url":"https://api.github.com/users/Sacha0/gists{/gist_id}","starred_url":"https://api.github.com/users/Sacha0/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Sacha0/subscriptions","organizations_url":"https://api.github.com/users/Sacha0/orgs","repos_url":"https://api.github.com/users/Sacha0/repos","events_url":"https://api.github.com/users/Sacha0/events{/privacy}","received_events_url":"https://api.github.com/users/Sacha0/received_events","type":"User","site_admin":false},"created_at":"2016-12-13T20:20:38Z","updated_at":"2016-12-13T20:20:38Z","body":"> @Sacha0, do you think we can update the sparse matrix code to behave like the dense array code?\r\n\r\nYes, my intention was to change the sparse broadcast promotion mechanism in this pull request to that provided in #19421 prior to merging. #19576 (thanks!) should have fixed this discrepancy? Best!"}}
{"actor":{"display_login":"Sacha0"}}