{"action":"created","issue":{"url":"https://api.github.com/repos/JuliaLang/julia/issues/16931","repository_url":"https://api.github.com/repos/JuliaLang/julia","labels_url":"https://api.github.com/repos/JuliaLang/julia/issues/16931/labels{/name}","comments_url":"https://api.github.com/repos/JuliaLang/julia/issues/16931/comments","events_url":"https://api.github.com/repos/JuliaLang/julia/issues/16931/events","html_url":"https://github.com/JuliaLang/julia/pull/16931","id":160262729,"number":16931,"title":"MIT-licensed SparseMatrixCSC permute[!] and refactored [c]transpose[!]","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":[{"url":"https://api.github.com/repos/JuliaLang/julia/labels/sparse","name":"sparse","color":"fad8c7"}],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":4,"created_at":"2016-06-14T19:22:19Z","updated_at":"2016-06-14T21:00:35Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/JuliaLang/julia/pulls/16931","html_url":"https://github.com/JuliaLang/julia/pull/16931","diff_url":"https://github.com/JuliaLang/julia/pull/16931.diff","patch_url":"https://github.com/JuliaLang/julia/pull/16931.patch"},"body":"Followup to #13001, #14631, #14702, #14798, and #15242. This pull request refactors `[c]transpsose[!]` methods operating on `SparseMatrixCSC`s and introduces accompanying MIT-licensed `permute[!]` methods as a replacement for `csc_permute`. Details:\r\n\r\nThe first commit refactors the `[c]transpose[!]` methods: (1) such that the later-introduced `permute[!]` methods share the `[c]tranpose[!]` methods' code insofar as possible; and (2) taking advantage of #16371 for better structuring. Part of (1) is replacing `qftranspose!` with a more general `halfperm!`; in that replacement, the permutation vector convention changes to match that seemingly used elsewhere in Julia (such that `halfperm!(X, A, q)` now produces `X = transpose(A[:,q])` and consequently `permute(A, p, q)` produces `A[p,q]` --- desired behavior?). This first commit also adds several tests for those `[c]tranpsose[!]` methods.\r\n\r\nWould one of the powers that be ask NanoSoldier to run the sparse performance tests to check for regressions in `[c]transpose[!]`?\r\n\r\nThe second commit introduces `permute[!]` methods operating on `SparseMatrixCSC`s (intended to replace and extend the functionality of `csc_permute`), documents those methods, and adds a set of associated tests. In anticipation of heap-referencing immutables one day being stack-allocatable, the present interface operates solely on `SparseMatrixCSC`s rather than also providing methods working on sets of vectors constituting `SparseMatrixCSC`s. The second commit exports `permute` from `SparseArrays` but does not place an entry in `exports.jl` (should it?).\r\n\r\n Concerning `permute[!]`'s performance, these benchmarks\r\n\r\n```julia\r\nusing Benchmarks: @benchmark, SummaryStatistics\r\nimport Base.SparseArrays.permute\r\nimport Base.SparseArrays.csc_permute\r\n\r\nfunction prettytimes(bench)\r\n    stats = SummaryStatistics(bench)\r\n    timecenter = stats.elapsed_time_center\r\n    timelower = get(stats.elapsed_time_lower)\r\n    timeupper = get(stats.elapsed_time_upper)\r\n    # based on Benchmarks.pretty_time_string\r\n    timecenter < 1_000.0 ? (scalefactor = 1.0; units = \"ns\") :\r\n        timecenter < 1_000_000.0 ? (scalefactor = 1_000.0; units = \"μs\") :\r\n            timecenter < 1_000_000_000.0 ? (scalefactor = 1_000_000.0; units = \"ms\") :\r\n                (scalefactor = 1_000_000_000.0; units = \" s\")\r\n    @sprintf(\"%6.2f%s [%6.2f,%6.2f]\", timecenter/scalefactor, units, timelower/scalefactor, timeupper/scalefactor)\r\nend\r\n\r\nsmallN, smallerN = 600, 400;\r\nsmallsqrA = sprand(smallN, smallN, 0.01);\r\nsmalltallA = sprand(smallN, smallerN, 0.01);\r\nsmallwideA = sprand(smallerN, smallN, 0.01);\r\nlargeN, largerN = 50000, 100000;\r\nlargesqrA = sprand(largerN, largerN, 0.001);\r\nlargetallA = sprand(largerN, largeN, 0.001);\r\nlargewideA = sprand(largeN, largerN, 0.001);\r\npsmall = randperm(smallN); qsmall = randperm(smallN);\r\npsmaller = randperm(smallerN); qsmaller = randperm(smallerN);\r\nplarge = randperm(largeN); qlarge = randperm(largeN);\r\nplarger = randperm(largerN); qlarger = randperm(largerN);\r\n\r\nwm, wt = 12, 24;\r\nprintln(\" $(lpad(\"method \", wm)) $(lpad(\"small square A\", wt)), $(lpad(\"small tall A\", wt)), $(lpad(\"small wide A\", wt)) | $(lpad(\"large square A\", wt)), $(lpad(\"large tall A\", wt)), $(lpad(\"large wide A\", wt)) \")\r\n@printf(\"%s: %s , %s , %s | %s, %s , %s\\n\", lpad(\"permute\", wm),\r\n    prettytimes(@benchmark permute(smallsqrA, psmall, qsmall)),\r\n    prettytimes(@benchmark permute(smalltallA, psmall, qsmaller)),\r\n    prettytimes(@benchmark permute(smallwideA, psmaller, qsmall)),\r\n    prettytimes(@benchmark permute(largesqrA, plarger, qlarger)),\r\n    prettytimes(@benchmark permute(largetallA, plarger, qlarge)),\r\n    prettytimes(@benchmark permute(largewideA, plarge, qlarger)) )\r\n@printf(\"%s: %s , %s , %s | %s, %s , %s\\n\", lpad(\"csc_permute\", wm),\r\n    prettytimes(@benchmark csc_permute(smallsqrA, psmall, qsmall)),\r\n    prettytimes(@benchmark csc_permute(smalltallA, psmall, qsmaller)),\r\n    prettytimes(@benchmark csc_permute(smallwideA, psmaller, qsmall)),\r\n    prettytimes(@benchmark csc_permute(largesqrA, plarger, qlarger)),\r\n    prettytimes(@benchmark csc_permute(largetallA, plarger, qlarge)),\r\n    prettytimes(@benchmark csc_permute(largewideA, plarge, qlarger)) )\r\n```\r\n\r\nyield\r\n\r\n```julia\r\n      method              small square A,                small tall A,              small wide A |            large square A,               large tall A,              large wide A\r\n     permute:  59.50 μs [ 31.30, 87.71] ,  34.03 μs [ 32.35, 35.72] ,  41.43 μs [ 11.05, 71.80] |   1.27  s [  1.14,  1.39], 569.81 ms [529.28,610.35] , 567.68 ms [521.41,613.95]\r\n csc_permute: 107.57 μs [ 77.89,137.25] ,  69.29 μs [ 26.74,111.83] ,  74.63 μs [ 35.43,113.82] |   1.39  s [  1.27,  1.51], 639.68 ms [568.00,711.36] , 660.11 ms [585.24,734.98]\r\n```\r\n\r\nand `permute` requires signicantly less memory than `csc_permute`\r\n\r\n```julia\r\njulia> @benchmark permute(largesqrA, plarger, qlarger)\r\n================ Benchmark Results ========================\r\n     Time per evaluation: 1.31 s [1.20 s, 1.42 s]\r\nProportion of time in GC: 9.83% [2.53%, 17.14%]\r\n        Memory allocated: 306.57 mb\r\n   Number of allocations: 14 allocations\r\n       Number of samples: 6\r\n   Number of evaluations: 6\r\n Time spent benchmarking: 9.70 s\r\n\r\n\r\njulia> @benchmark csc_permute(largesqrA, plarger, qlarger)\r\n================ Benchmark Results ========================\r\n     Time per evaluation: 1.41 s [1.24 s, 1.58 s]\r\nProportion of time in GC: 12.20% [1.38%, 23.03%]\r\n        Memory allocated: 459.87 mb\r\n   Number of allocations: 31 allocations\r\n       Number of samples: 5\r\n   Number of evaluations: 5\r\n Time spent benchmarking: 9.03 s\r\n```\r\n\r\nTo avoid tangling this PR and #16070, this PR does not presently remove/deprecate `csc_permute`. @KristofferC, what would you like me to do here with respect to #16070?\r\n\r\n`symperm` remains on my radar.\r\n"},"comment":{"url":"https://api.github.com/repos/JuliaLang/julia/issues/comments/226014748","html_url":"https://github.com/JuliaLang/julia/pull/16931#issuecomment-226014748","issue_url":"https://api.github.com/repos/JuliaLang/julia/issues/16931","id":226014748,"user":{"login":"tkelman","id":5934628,"avatar_url":"https://avatars.githubusercontent.com/u/5934628?v=3","gravatar_id":"","url":"https://api.github.com/users/tkelman","html_url":"https://github.com/tkelman","followers_url":"https://api.github.com/users/tkelman/followers","following_url":"https://api.github.com/users/tkelman/following{/other_user}","gists_url":"https://api.github.com/users/tkelman/gists{/gist_id}","starred_url":"https://api.github.com/users/tkelman/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/tkelman/subscriptions","organizations_url":"https://api.github.com/users/tkelman/orgs","repos_url":"https://api.github.com/users/tkelman/repos","events_url":"https://api.github.com/users/tkelman/events{/privacy}","received_events_url":"https://api.github.com/users/tkelman/received_events","type":"User","site_admin":false},"created_at":"2016-06-14T21:00:34Z","updated_at":"2016-06-14T21:00:34Z","body":" @nanosoldier `runbenchmarks(\"sparse\", vs = \":master\")`"}}
{"actor":{"display_login":"tkelman"}}