JuliaLang/julia — pull request #6280 by mauro3 (2014-03-27 14:46:47+00:00)
Title: WIP: Sparse matrix indexing with ranges is slow and memory hungry

This PR fixes the case when a whole column of a sparse matrix is indexed. For a 1e7 by 1e7 sparse identity matrix this PR achieves a 180x speedup and uses 10000x less memory. This issue was brought up here:
https://groups.google.com/d/msg/julia-users/sxigT0PLbrw/AooGFgdUnwgJ

However, indexing only parts of columns with ranges still has the same problem. This needs a bigger rewrite of `getindex_I_sorted` and `getindex_general`. I will try to work on this in the next few weeks. Thus this is marked as WIP. However, this pull request could also be merged as it stands and the additional work be done after that.

@viralbshah could you check this pull request?

Here is my timing comparison-script:
```julia
small = speye(10); # warm up matrix
n = int(1e7);
e = speye(n); # text matrix

# whole column-wise indexing is slow in upstream
f(spa, col) = spa[:,col]
f(small, 5)
@time out = f(e, int(n/2))
# pull-req: elapsed time: 0.000937658 seconds (23264 bytes allocated)
# upstream: elapsed time: 0.167528016 seconds (241273560 bytes allocated)
# speedup: 180x, memory 10,000x less

# not full column-wise indexing: (uses getindex_I_sorted)
g(spa, col) = spa[2:end-1,col]
g(small, 5)
@time out = g(e, int(n/2))
# pull-req: elapsed time: 0.085139379 seconds (161252440 bytes allocated)
# upstream: elapsed time: 0.163165531 seconds (241250776 bytes allocated)
# speedup: 2x, memory 2x less

# reversed column-wise indexing: (uses getindex_general at the moment)
gg(spa, col) = spa[end:-1:1,col]
gg(small, 5)
@time out = gg(e, int(n/2))
# pull-req: elapsed time: 0.962661565 seconds (480001400 bytes allocated)
# upstream: elapsed time: 0.947118108 seconds (480001288 bytes allocated)
# same as no code change
```