Improved sparse getindex

[mauro3]

This PR improves the sparse getindex performance. Execution time is shorter by a factor of 1 to 500 on the (somewhat primitive) examples I ran, memory usage is down by a factor of 1 to 5000. The performance
tests and results are here: https://gist.github.com/mauro3/7f01931b5f25d7b397af

Updates:

• row indexing with ranges has now a dedicated method (biggest
  speedup & memory gain).
• row indexing with sorted vectors is now using a method similar to
  the original getindex_general (some large speed-ups/memory gains as well)
• row indexing with unsorted vectors uses original getindex_general
  (therefore no gains)
• I had to add some dis-ambiguity methods
• more tests added. --code-coverage shows full coverage of all
  getindex & related functions

[kmsquire]

A factor of 0 would never return, so I assume you mean 1. :-)

Anyway, the timings are impressive!

[mauro3]

Yep, 1, as in no improvement (now corrected). Tnx.

[ViralBShah]

This is really great, and much needed improvement. The performance tests are nice too. Could you add them to the test/perf directory?

[ViralBShah]

@tanmaykm This will probably conflict with the SparseMatrixCSR PR.

[mauro3]

That was swift work! I'll have a look at test/perf stuff.

[ViralBShah]

@mauro3 Keep 'em coming! I see you work quite a bit with sparse matrices, on your homepage. It would be great if you can keep pushing the limits.

[dmbates]

The binarysearch call in getindex can fail for cases where the index type of the sparse matrix is not the default integer size. I often use SparseMatrixCSC{Float64,Int32} even on a 64-bit machine to save on storage but a simple getindex will fail

julia> typeof(ztz)
SparseMatrixCSC{Float64,Int32} (constructor with 2 methods)

julia> ztz[1,1]
ERROR: no method binarysearch(Array{Int32,1}, Int64, Int32, Int64)
 in getindex at ./sparse/sparsematrix.jl:740

Even converting the indices to Int32 doesn't work because the expression for the last argument in the call to getindex has a literal - 1 in it.

julia> ztz[one(Int32),one(Int32)]
ERROR: no method binarysearch(Array{Int32,1}, Int32, Int32, Int64)
 in getindex at ./sparse/sparsematrix.jl:740

[mauro3]

Ha, I thought it unlikely that this would be bug free. Thanks!

The -1 can be changed to 0, which would probably be better and binarysearch to:

function binarysearch{Ti<:Integer}(haystack::AbstractVector{Ti}, needle, lo::Ti, hi::Ti)
    # Finds the first occurrence of needle in haystack[lo:hi]
    lo = lo-1
    hi2 = hi
    hi = hi+1
    @inbounds while lo < hi-1
        m = (lo+hi)>>>1
        if haystack[m] < needle
            lo = m
        else
            hi = m
        end
    end
    (hi==hi2+1 || haystack[hi]!=needle) ? 0 : hi
end

plus a few other changes. I don't have time to do it now but I'll try tomorrow.

[kmsquire]

Is there a reason you're reimplementing binarysearch?

[mauro3]

@kmsquire: you mean with respect to the ones in sort.jl? The searchsortedfirst returns the index of the found needle or the insertion point. But this is not what I need here. There is searchsorted which returns an empty range if the needle hasn't been found but it looks like it has quite some overhead. (Although I did not profile it.) Further, it would suffer as well from the bug @dmbates reported as lo and hi are also ::int.

[mauro3]

Made PR with performance tests I used for this: #7177