Description
JuliaLang/julia#42647 improves sparse matrix slicing when the matrix isn't too sparse and the number of requested indices isn't too large relative to the average number of non-zeros in a column (the linear search case). However, the overhead from a large cache vector is also present in the method used when the number of requested indices is large relative to the average number of nonzeros, (the binary search in the index vector case, i.e. getindex_I_sorted_bsearch_I). The problematic allocation is https://github.com/JuliaLang/julia/blob/7c5e28c4c1ff4bf5c3c9f38450158833a366b4f6/stdlib/SparseArrays/src/sparsematrix.jl#L2438-L2440 and it would be nice to get rid of. In JuliaLang/julia#42647, it was possible to show a 1000000x speedup in a simple case and I suspect something similar is possible here.