{"action":"created","issue":{"url":"https://api.github.com/repos/JuliaLang/julia/issues/10536","labels_url":"https://api.github.com/repos/JuliaLang/julia/issues/10536/labels{/name}","comments_url":"https://api.github.com/repos/JuliaLang/julia/issues/10536/comments","events_url":"https://api.github.com/repos/JuliaLang/julia/issues/10536/events","html_url":"https://github.com/JuliaLang/julia/pull/10536","id":62233263,"number":10536,"title":"Faster and more general reductions for sparse matrices","user":{"login":"simonster","id":470884,"avatar_url":"https://avatars.githubusercontent.com/u/470884?v=3","gravatar_id":"","url":"https://api.github.com/users/simonster","html_url":"https://github.com/simonster","followers_url":"https://api.github.com/users/simonster/followers","following_url":"https://api.github.com/users/simonster/following{/other_user}","gists_url":"https://api.github.com/users/simonster/gists{/gist_id}","starred_url":"https://api.github.com/users/simonster/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/simonster/subscriptions","organizations_url":"https://api.github.com/users/simonster/orgs","repos_url":"https://api.github.com/users/simonster/repos","events_url":"https://api.github.com/users/simonster/events{/privacy}","received_events_url":"https://api.github.com/users/simonster/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":2,"created_at":"2015-03-16T23:14:28Z","updated_at":"2015-03-16T23:19:43Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/JuliaLang/julia/pulls/10536","html_url":"https://github.com/JuliaLang/julia/pull/10536","diff_url":"https://github.com/JuliaLang/julia/pull/10536.diff","patch_url":"https://github.com/JuliaLang/julia/pull/10536.patch"},"body":"This hooks sparse matrix reductions into the `mapreduce`/`mapreducedim` framework so that reductions based on one of those two functions (`sum`, `prod`, `maximum`, `minimum`,  `sumabs`, `sumabs2`, `maxabs`, `minabs`, and others) are fast for sparse matrices. I also implemented a method of `centralize_sumabs2!`, which is the function that computes the reduction for `var` and `std`. This required a tiny tweak to `statistics.jl`.\r\nBefore:\r\n\r\n```julia\r\njulia> A = sprand(10000, 10000, 0.01);\r\n\r\njulia> @time sum(A);\r\nelapsed time: 0.000725368 seconds (128 bytes allocated)\r\n\r\njulia> @time sum(A, 1);\r\nelapsed time: 0.050776048 seconds (31 MB allocated, 31.91% gc time in 2 pauses with 1 full sweep)\r\n\r\njulia> @time sum(A, 2);\r\nelapsed time: 0.150387959 seconds (76 MB allocated, 16.90% gc time in 3 pauses with 0 full sweep)\r\n\r\njulia> @time minimum(A);\r\nelapsed time: 0.000895639 seconds (128 bytes allocated)\r\n\r\njulia> @time minimum(A, 1);\r\nelapsed time: 0.025368923 seconds (31 MB allocated, 16.27% gc time in 2 pauses with 0 full sweep)\r\n\r\njulia> @time minimum(A, 2);\r\nelapsed time: 0.099724495 seconds (76 MB allocated, 5.97% gc time in 3 pauses with 0 full sweep)\r\n\r\njulia> @time sumabs2(A);\r\nelapsed time: 2.84146989 seconds (128 bytes allocated)\r\n\r\njulia> @time sumabs2(A, 1);\r\nelapsed time: 1.347525703 seconds (592 kB allocated)\r\n\r\njulia> @time sumabs2(A, 2);\r\nelapsed time: 9.477093327 seconds (514 kB allocated)\r\n\r\njulia> @time var(A);\r\nelapsed time: 2.861990251 seconds (224 bytes allocated)\r\n\r\njulia> @time var(A, 1);\r\nelapsed time: 1.378826771 seconds (31 MB allocated, 0.29% gc time in 2 pauses with 0 full sweep)\r\n\r\njulia> @time var(A, 2);\r\nelapsed time: 9.576421764 seconds (76 MB allocated, 0.06% gc time in 3 pauses with 0 full sweep)\r\n```\r\n\r\nAfter:\r\n\r\n```julia\r\njulia> A = sprand(10000, 10000, 0.01);\r\n\r\njulia> @time sum(A);\r\nelapsed time: 0.00059218 seconds (96 bytes allocated)\r\n\r\njulia> @time sum(A, 1);\r\nelapsed time: 0.000527368 seconds (78 kB allocated)\r\n\r\njulia> @time sum(A, 2);\r\nelapsed time: 0.001874181 seconds (78 kB allocated)\r\n\r\njulia> @time minimum(A);\r\nelapsed time: 0.000835505 seconds (96 bytes allocated)\r\n\r\njulia> @time minimum(A, 1);\r\nelapsed time: 0.00154097 seconds (78 kB allocated)\r\n\r\njulia> @time minimum(A, 2);\r\nelapsed time: 0.003695277 seconds (156 kB allocated)\r\n\r\njulia> @time sumabs2(A);\r\nelapsed time: 0.000476106 seconds (96 bytes allocated)\r\n\r\njulia> @time sumabs2(A, 1);\r\nelapsed time: 0.000620605 seconds (78 kB allocated)\r\n\r\njulia> @time sumabs2(A, 2);\r\nelapsed time: 0.001989696 seconds (78 kB allocated)\r\n\r\njulia> @time var(A);\r\nelapsed time: 0.000910167 seconds (192 bytes allocated)\r\n\r\njulia> @time var(A, 1);\r\nelapsed time: 0.001041256 seconds (157 kB allocated)\r\n\r\njulia> @time var(A, 2);\r\nelapsed time: 0.006364037 seconds (235 kB allocated)\r\n```\r\n\r\nAll times include warmup."},"comment":{"url":"https://api.github.com/repos/JuliaLang/julia/issues/comments/81986052","html_url":"https://github.com/JuliaLang/julia/pull/10536#issuecomment-81986052","issue_url":"https://api.github.com/repos/JuliaLang/julia/issues/10536","id":81986052,"user":{"login":"andreasnoack","id":505001,"avatar_url":"https://avatars.githubusercontent.com/u/505001?v=3","gravatar_id":"","url":"https://api.github.com/users/andreasnoack","html_url":"https://github.com/andreasnoack","followers_url":"https://api.github.com/users/andreasnoack/followers","following_url":"https://api.github.com/users/andreasnoack/following{/other_user}","gists_url":"https://api.github.com/users/andreasnoack/gists{/gist_id}","starred_url":"https://api.github.com/users/andreasnoack/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/andreasnoack/subscriptions","organizations_url":"https://api.github.com/users/andreasnoack/orgs","repos_url":"https://api.github.com/users/andreasnoack/repos","events_url":"https://api.github.com/users/andreasnoack/events{/privacy}","received_events_url":"https://api.github.com/users/andreasnoack/received_events","type":"User","site_admin":false},"created_at":"2015-03-16T23:19:43Z","updated_at":"2015-03-16T23:19:43Z","body":":+1: "}}