Sparse getindex performance

new_timings

NEW

m = vs[3]; =====================================

Integer indexing:                           elapsed time: 0.004826669 seconds (96088 bytes allocated)
 
#### indexing with ranges
Whole column-wise indexing:                 elapsed time: 0.001638723 seconds (6527288 bytes allocated)
Column-wise indexing with a range of rows:  elapsed time: 0.003093329 seconds (123832 bytes allocated)
Whole row-wise indexing:                    elapsed time: 6.059387827 seconds (32650872 bytes allocated)
Row-wise indexing with a range of columns:  elapsed time: 0.030642959 seconds (290488 bytes allocated)
Small sub-matrix with range indices:        elapsed time: 0.157466066 seconds (423944 bytes allocated)
Large sub-matrix with range indices:        elapsed time: 0.559105468 seconds (2788776 bytes allocated)
 
#### indexing with sorted vectors
Whole column-wise indexing:                 elapsed time: 0.287560622 seconds (326552536 bytes allocated)
Column-wise indexing with a [range] of rows:  elapsed time: 0.000338717 seconds (315160 bytes allocated)
Whole row-wise indexing:                    elapsed time: 7.779341657 seconds (64657592 bytes allocated)
Row-wise indexing with a [range] of columns:elapsed time: 0.029769896 seconds (482056 bytes allocated)
Small sub-matrix with [range] indices:      elapsed time: 0.044156593 seconds (810728 bytes allocated)
Large sub-matrix with [range] indices:      elapsed time: 0.174869549 seconds (4013352 bytes allocated)
 
#### indexing with unsorted vectors
Whole column-wise indexing:                 elapsed time: 0.121537862 seconds (320500736 bytes allocated)
Column-wise indexing with a range of rows:  elapsed time: 0.15038613 seconds (607200 bytes allocated)
Whole row-wise indexing:                    elapsed time: 0.38810473 seconds (3362456 bytes allocated)
Row-wise indexing with a range of columns:  elapsed time: 0.090306504 seconds (2181504 bytes allocated)
Small sub-matrix with range indices:        elapsed time: 0.050225289 seconds (1514696 bytes allocated)
Large sub-matrix with range indices:        elapsed time: 0.170256886 seconds (4152456 bytes allocated)

m = us[3]; =====================================

Integer indexing:                           elapsed time: 0.002431136 seconds (96088 bytes allocated)
 
#### indexing with ranges
Whole column-wise indexing:                 elapsed time: 0.000341337 seconds (801976 bytes allocated)
Column-wise indexing with a range of rows:  elapsed time: 0.000442672 seconds (119096 bytes allocated)
Whole row-wise indexing:                    elapsed time: 0.807498208 seconds (32082072 bytes allocated)
Row-wise indexing with a range of columns:  elapsed time: 0.003693256 seconds (285272 bytes allocated)
Small sub-matrix with range indices:        elapsed time: 0.016394652 seconds (274312 bytes allocated)
Large sub-matrix with range indices:        elapsed time: 0.058749939 seconds (893032 bytes allocated)
 
#### indexing with sorted vectors
Whole column-wise indexing:                 elapsed time: 0.265004958 seconds (320831160 bytes allocated)
Column-wise indexing with a [range] of rows:  elapsed time: 0.000279002 seconds (310968 bytes allocated)
Whole row-wise indexing:                    elapsed time: 0.923231968 seconds (64082712 bytes allocated)
Row-wise indexing with a [range] of columns:elapsed time: 0.003532543 seconds (477352 bytes allocated)
Small sub-matrix with [range] indices:      elapsed time: 0.008874504 seconds (658536 bytes allocated)
Large sub-matrix with [range] indices:      elapsed time: 0.066328286 seconds (2127560 bytes allocated)
 
#### indexing with unsorted vectors
Whole column-wise indexing:                 elapsed time: 0.011058379 seconds (32385472 bytes allocated)
Column-wise indexing with a range of rows:  elapsed time: 0.018393742 seconds (457920 bytes allocated)
Whole row-wise indexing:                    elapsed time: 0.102039089 seconds (2500056 bytes allocated)
Row-wise indexing with a range of columns:  elapsed time: 0.031043726 seconds (1880064 bytes allocated)
Small sub-matrix with range indices:        elapsed time: 0.015151309 seconds (1411208 bytes allocated)
Large sub-matrix with range indices:        elapsed time: 0.074135644 seconds (3338440 bytes allocated)

m = ts[3]; =====================================

Integer indexing:                           elapsed time: 0.001104554 seconds (96088 bytes allocated)
 
#### indexing with ranges
Whole column-wise indexing:                 elapsed time: 0.000176583 seconds (184664 bytes allocated)
Column-wise indexing with a range of rows:  elapsed time: 0.000214901 seconds (118584 bytes allocated)
Whole row-wise indexing:                    elapsed time: 0.188639573 seconds (32018360 bytes allocated)
Row-wise indexing with a range of columns:  elapsed time: 0.001012846 seconds (284856 bytes allocated)
Small sub-matrix with range indices:        elapsed time: 0.002309597 seconds (257544 bytes allocated)
Large sub-matrix with range indices:        elapsed time: 0.007887424 seconds (701992 bytes allocated)
 
#### indexing with sorted vectors
Whole column-wise indexing:                 elapsed time: 0.26683209 seconds (320205016 bytes allocated)
Column-wise indexing with a [range] of rows:  elapsed time: 0.000289524 seconds (310680 bytes allocated)
Whole row-wise indexing:                    elapsed time: 0.197211131 seconds (64020728 bytes allocated)
Row-wise indexing with a [range] of columns:elapsed time: 0.000824432 seconds (476904 bytes allocated)
Small sub-matrix with [range] indices:      elapsed time: 0.005072476 seconds (641640 bytes allocated)
Large sub-matrix with [range] indices:      elapsed time: 0.050494744 seconds (1929192 bytes allocated)
 
#### indexing with unsorted vectors
Whole column-wise indexing:                 elapsed time: 0.004436676 seconds (3655200 bytes allocated)
Column-wise indexing with a range of rows:  elapsed time: 0.00596366 seconds (441408 bytes allocated)
Whole row-wise indexing:                    elapsed time: 0.037032025 seconds (2412952 bytes allocated)
Row-wise indexing with a range of columns:  elapsed time: 0.011459501 seconds (1844928 bytes allocated)
Small sub-matrix with range indices:        elapsed time: 0.00881745 seconds (1395848 bytes allocated)
Large sub-matrix with range indices:        elapsed time: 0.028380641 seconds (3262536 bytes allocated)

m = ss[3]; =====================================


Integer indexing:                           elapsed time: 0.000709619 seconds (96088 bytes allocated)
 
#### indexing with ranges
Whole column-wise indexing:                 elapsed time: 0.000134096 seconds (127288 bytes allocated)
Column-wise indexing with a range of rows:  elapsed time: 0.000127868 seconds (118488 bytes allocated)
Whole row-wise indexing:                    elapsed time: 0.113374951 seconds (32012856 bytes allocated)
Row-wise indexing with a range of columns:  elapsed time: 0.000397379 seconds (284792 bytes allocated)
Small sub-matrix with range indices:        elapsed time: 0.000778785 seconds (254792 bytes allocated)
Large sub-matrix with range indices:        elapsed time: 0.002406474 seconds (680840 bytes allocated)
 
#### indexing with sorted vectors
Whole column-wise indexing:                 elapsed time: 0.176814709 seconds (320147160 bytes allocated)
Column-wise indexing with a [range] of rows:  elapsed time: 0.000243378 seconds (310456 bytes allocated)
Whole row-wise indexing:                    elapsed time: 0.111628623 seconds (64014936 bytes allocated)
Row-wise indexing with a [range] of columns:elapsed time: 0.000313938 seconds (476904 bytes allocated)
Small sub-matrix with [range] indices:      elapsed time: 0.002128189 seconds (638600 bytes allocated)
Large sub-matrix with [range] indices:      elapsed time: 0.020710757 seconds (1909480 bytes allocated)
 
#### indexing with unsorted vectors
Whole column-wise indexing:                 elapsed time: 0.001252614 seconds (774592 bytes allocated)
Column-wise indexing with a range of rows:  elapsed time: 0.001607016 seconds (438848 bytes allocated)
Whole row-wise indexing:                    elapsed time: 0.010117106 seconds (2403352 bytes allocated)
Row-wise indexing with a range of columns:  elapsed time: 0.00432139 seconds (1840576 bytes allocated)
Small sub-matrix with range indices:        elapsed time: 0.003361182 seconds (1393992 bytes allocated)
Large sub-matrix with range indices:        elapsed time: 0.010219036 seconds (3250952 bytes allocated)

old_timings

OLD

m = vs[3];

Integer indexing:                           elapsed time: 0.004933011 seconds (96088 bytes allocated)
 
#### indexing with ranges
Whole column-wise indexing:                 elapsed time: 0.001816334 seconds (6562488 bytes allocated)
Column-wise indexing with a range of rows:  elapsed time: 0.218384062 seconds (645269432 bytes allocated)
Whole row-wise indexing:                    elapsed time: 44.142218493 seconds (97159672 bytes allocated)
Row-wise indexing with a range of columns:  elapsed time: 0.404527102 seconds (645378488 bytes allocated)
Small sub-matrix with range indices:        elapsed time: 0.416874746 seconds (645538184 bytes allocated)
Large sub-matrix with range indices:        elapsed time: 1.033242098 seconds (647904296 bytes allocated)
 
#### indexing with sorted vectors
Whole column-wise indexing:                 elapsed time: 0.682036568 seconds (971640536 bytes allocated)
Column-wise indexing with a [range] of rows:  elapsed time: 0.186211565 seconds (645403160 bytes allocated)
Whole row-wise indexing:                    elapsed time: 46.558229963 seconds (129166392 bytes allocated)
Row-wise indexing with a [range] of columns:elapsed time: 0.417086976 seconds (645570056 bytes allocated)
Small sub-matrix with [range] indices:      elapsed time: 0.415892174 seconds (645898728 bytes allocated)
Large sub-matrix with [range] indices:      elapsed time: 1.014054189 seconds (649101352 bytes allocated)
 
#### indexing with unsorted vectors
Whole column-wise indexing:                 elapsed time: 0.116280701 seconds (320535936 bytes allocated)
Column-wise indexing with a range of rows:  elapsed time: 0.414497644 seconds (645752800 bytes allocated)
Whole row-wise indexing:                    elapsed time: 0.373247283 seconds (3362456 bytes allocated)
Row-wise indexing with a range of columns:  elapsed time: 0.08468617 seconds (2181504 bytes allocated)
Small sub-matrix with range indices:        elapsed time: 0.04726133 seconds (1514696 bytes allocated)
Large sub-matrix with range indices:        elapsed time: 0.162207124 seconds (4152456 bytes allocated)

m = us[3]; =====================================

Integer indexing:                           elapsed time: 0.00249898 seconds (96088 bytes allocated)
 
#### indexing with ranges
Whole column-wise indexing:                 elapsed time: 0.000365609 seconds (837176 bytes allocated)
Column-wise indexing with a range of rows:  elapsed time: 0.187046026 seconds (645264696 bytes allocated)
Whole row-wise indexing:                    elapsed time: 4.511786921 seconds (96590872 bytes allocated)
Row-wise indexing with a range of columns:  elapsed time: 0.206392614 seconds (645373272 bytes allocated)
Small sub-matrix with range indices:        elapsed time: 0.208594521 seconds (645388552 bytes allocated)
Large sub-matrix with range indices:        elapsed time: 0.271528044 seconds (646008552 bytes allocated)
 
#### indexing with sorted vectors
Whole column-wise indexing:                 elapsed time: 0.681804618 seconds (965919160 bytes allocated)
Column-wise indexing with a [range] of rows:  elapsed time: 0.18779808 seconds (645398968 bytes allocated)
Whole row-wise indexing:                    elapsed time: 4.729410187 seconds (128591512 bytes allocated)
Row-wise indexing with a [range] of columns:elapsed time: 0.208684085 seconds (645565352 bytes allocated)
Small sub-matrix with [range] indices:      elapsed time: 0.208329726 seconds (645746536 bytes allocated)
Large sub-matrix with [range] indices:      elapsed time: 0.271036609 seconds (647215560 bytes allocated)
 
#### indexing with unsorted vectors
Whole column-wise indexing:                 elapsed time: 0.009998953 seconds (32420672 bytes allocated)
Column-wise indexing with a range of rows:  elapsed time: 0.211808421 seconds (645603520 bytes allocated)
Whole row-wise indexing:                    elapsed time: 0.095462008 seconds (2500056 bytes allocated)
Row-wise indexing with a range of columns:  elapsed time: 0.029304436 seconds (1880064 bytes allocated)
Small sub-matrix with range indices:        elapsed time: 0.014708355 seconds (1411208 bytes allocated)
Large sub-matrix with range indices:        elapsed time: 0.071364559 seconds (3338440 bytes allocated)

m = ts[3]; =====================================

Integer indexing:                           elapsed time: 0.001009136 seconds (96088 bytes allocated)
 
#### indexing with ranges
Whole column-wise indexing:                 elapsed time: 0.000204787 seconds (219864 bytes allocated)
Column-wise indexing with a range of rows:  elapsed time: 0.188637262 seconds (645264184 bytes allocated)
Whole row-wise indexing:                    elapsed time: 0.593791719 seconds (96527160 bytes allocated)
Row-wise indexing with a range of columns:  elapsed time: 0.186840818 seconds (645372856 bytes allocated)
Small sub-matrix with range indices:        elapsed time: 0.23019267 seconds (645371784 bytes allocated)
Large sub-matrix with range indices:        elapsed time: 0.247773388 seconds (645817512 bytes allocated)
 
#### indexing with sorted vectors
Whole column-wise indexing:                 elapsed time: 0.726576735 seconds (965293016 bytes allocated)
Column-wise indexing with a [range] of rows:  elapsed time: 0.205842819 seconds (645398680 bytes allocated)
Whole row-wise indexing:                    elapsed time: 0.567744618 seconds (128529528 bytes allocated)
Row-wise indexing with a [range] of columns:elapsed time: 0.185421824 seconds (645564904 bytes allocated)
Small sub-matrix with [range] indices:      elapsed time: 0.186841712 seconds (645729640 bytes allocated)
Large sub-matrix with [range] indices:      elapsed time: 0.194440953 seconds (647017192 bytes allocated)
 
#### indexing with unsorted vectors
Whole column-wise indexing:                 elapsed time: 0.002948333 seconds (3690400 bytes allocated)
Column-wise indexing with a range of rows:  elapsed time: 0.190377422 seconds (645587008 bytes allocated)
Whole row-wise indexing:                    elapsed time: 0.034799572 seconds (2412952 bytes allocated)
Row-wise indexing with a range of columns:  elapsed time: 0.010344416 seconds (1844928 bytes allocated)
Small sub-matrix with range indices:        elapsed time: 0.006968656 seconds (1395848 bytes allocated)
Large sub-matrix with range indices:        elapsed time: 0.024690384 seconds (3262536 bytes allocated)

m = ss[3]; =====================================

Integer indexing:                           elapsed time: 0.000562925 seconds (96088 bytes allocated)
 
#### indexing with ranges
Whole column-wise indexing:                 elapsed time: 0.000172524 seconds (162488 bytes allocated)
Column-wise indexing with a range of rows:  elapsed time: 0.186211808 seconds (645264088 bytes allocated)
Whole row-wise indexing:                    elapsed time: 0.162798425 seconds (96521656 bytes allocated)
Row-wise indexing with a range of columns:  elapsed time: 0.18451112 seconds (645372792 bytes allocated)
Small sub-matrix with range indices:        elapsed time: 0.183808621 seconds (645369032 bytes allocated)
Large sub-matrix with range indices:        elapsed time: 0.188064782 seconds (645796360 bytes allocated)
 
#### indexing with sorted vectors
Whole column-wise indexing:                 elapsed time: 0.666695997 seconds (965235160 bytes allocated)
Column-wise indexing with a [range] of rows:  elapsed time: 0.183820893 seconds (645398456 bytes allocated)
Whole row-wise indexing:                    elapsed time: 0.155497633 seconds (128523736 bytes allocated)
Row-wise indexing with a [range] of columns:elapsed time: 0.183179921 seconds (645564904 bytes allocated)
Small sub-matrix with [range] indices:      elapsed time: 0.183684065 seconds (645726600 bytes allocated)
Large sub-matrix with [range] indices:      elapsed time: 0.185817356 seconds (646997480 bytes allocated)
 
#### indexing with unsorted vectors
Whole column-wise indexing:                 elapsed time: 0.001265843 seconds (809792 bytes allocated)
Column-wise indexing with a range of rows:  elapsed time: 0.18806167 seconds (645584448 bytes allocated)
Whole row-wise indexing:                    elapsed time: 0.009827299 seconds (2403352 bytes allocated)
Row-wise indexing with a range of columns:  elapsed time: 0.004155211 seconds (1840576 bytes allocated)
Small sub-matrix with range indices:        elapsed time: 0.003358176 seconds (1393992 bytes allocated)
Large sub-matrix with range indices:        elapsed time: 0.010274825 seconds (3250952 bytes allocated)

sparseperformance

## to test performance of sparse indexing

# test function as macro so it can be evaluated both with old and new sparse getindex
macro testfn(name)
    quote
        function $(esc(name))(A)
            srand(seed)
            nI, nJ = size(A)
            rI = 1:nI
            rJ = 1:nJ
            rep = 20
            reps = rep^2 # should be a square and divisible by 10

            tmp::eltype(A)

            print("Integer indexing:                           ")
            # Base.SparseMatrix.getindex
            gc()
            @time begin
                tmp = 0.0
                for i in rand(rI, reps)
                    for j in rand(rJ, rep)
                        tmp += A[i,j]
                    end 
                end
            end

            ###########
            println(" ")
            println("#### indexing with ranges")
            
            print("Whole column-wise indexing:                 ")
            # Base.SparseMatrix.getindex_cols
            gc()
            @time begin
                tmp = 0.0
                for j in rand(rJ, reps)
                    tmp += sum(A[:,j])
                end
            end
            print("Column-wise indexing with a range of rows:  ")
            # getindex_range
            gc()
            @time begin
                tmp = 0.0
                for j in rand(rJ, reps)
                    tmp += sum(A[50:100,j])
                end
            end
            print("Whole row-wise indexing:                    ")
            # getindex_general3
            gc()
            @time begin
                tmp = 0.0
                for i in rand(rI, div(reps,10) )
                    tmp += sum(A[i,:])
                end
            end
            print("Row-wise indexing with a range of columns:  ")
            # getindex_general3
            gc()
            @time begin
                tmp = 0.0
                for i in rand(rI, reps)
                    tmp += sum(A[i,50:100])
                end
            end
            print("Small sub-matrix with range indices:        ")
            # getindex_general3
            gc()
            @time begin
                for i in rand(1:nI-100, rep)
                    for j in rand(1:nJ-100, rep)
                        tmp2 = A[i:i+50, j:j+50]
                    end
                end
            end
            print("Large sub-matrix with range indices:        ")
            # getindex_general3
            gc()
            @time begin
                for i in rand(1:nI-200, rep)
                    for j in rand(1:nJ-200, rep)
                        tmp2 = A[i:i+180, j:j+180]
                    end
                end
            end

            ###########
            println(" ")
            println("#### indexing with sorted vectors")

            print("Whole column-wise indexing:                 ")
            # Base.SparseMatrix.getindex_cols
            gc()
            @time begin
                tmp = 0.0
                for j in rand(rJ, reps)
                    tmp += sum(A[[1:end],j])
                end
            end
            print("Column-wise indexing with a [range] of rows:  ")
            # getindex_range
            gc()
            @time begin
                tmp = 0.0
                for j in rand(rJ, reps)
                    tmp += sum(A[[50:100],j])
                end
            end
            print("Whole row-wise indexing:                    ")
            # getindex_general3
            gc()
            @time begin
                tmp = 0.0
                for i in rand(rI, div(reps,10) )
                    tmp += sum(A[i,[1:end]])
                end
            end
            print("Row-wise indexing with a [range] of columns:")
            # getindex_general3
            gc()
            @time begin
                tmp = 0.0
                for i in rand(rI, reps)
                    tmp += sum(A[i,[50:100]])
                end
            end
            print("Small sub-matrix with [range] indices:      ")
            # getindex_general3
            gc()
            @time begin
                for i in rand(1:nI-100, rep)
                    for j in rand(1:nJ-100, rep)
                        tmp2 = A[[i:i+50], [j:j+50]]
                    end
                end
            end
            print("Large sub-matrix with [range] indices:      ")
            # getindex_general3
            gc()
            @time begin
                for i in rand(1:nI-200, rep)
                    for j in rand(1:nJ-200, rep)
                        tmp2 = A[[i:i+180], [j:j+180]]
                    end
                end
            end

            ##########
            println(" ")
            println("#### indexing with unsorted vectors")

            print("Whole column-wise indexing:                 ")
            # Base.SparseMatrix.getindex_cols
            gc()
            @time begin
                tmp = 0.0
                for j in 1:reps
                    jj = rand(rJ, 50)
                    tmp += sum(A[:,jj])
                end
            end
            print("Column-wise indexing with a range of rows:  ")
            # getindex_range
            gc()
            @time begin
                tmp = 0.0
                for j in 1:reps
                    jj = rand(rJ, 50)
                    tmp += sum(A[50:100,jj])
                end
            end

# xxx worse below here:
            print("Whole row-wise indexing:                    ")
            # getindex_general3
            gc()
            @time begin
                tmp = 0.0
                for i in div(reps,10) 
                    ii = rand(rI, 30)
                    tmp += sum(A[ii,:])
                end
            end
            print("Row-wise indexing with a range of columns:  ")
            # getindex_general3
            gc()
            @time begin
                tmp = 0.0
                for i in 1:reps
                    ii = rand(rI, 50)
                    tmp += sum(A[ii,50:100])
                end
            end
            print("Small sub-matrix with range indices:        ")
            # getindex_general3
            gc()
            @time begin
                for i in rand(1:nI-100, rep)
                    for j in rand(1:nJ-100, rep)
                        ii = rand(rI, 30)
                        jj = rand(rJ, 30)
                        tmp2 = A[ii,jj]
                    end
                end
            end
            print("Large sub-matrix with range indices:        ")
            # getindex_general3
            gc()
            @time begin
                for i in rand(1:nI-200, rep)
                    for j in rand(1:nJ-200, rep)
                        ii = rand(rI, 80)
                        jj = rand(rJ, 80)
                        tmp2 = A[ii,jj]
                    end
                end
            end

            
        end
    end
end

## setup
using MatrixMarket

seed = 1
srand(seed)
# 1 entry per line
ss = {}
push!(ss, sprand(1000, 1000, 1e-3))
push!(ss, sprand(10000, 10000, 1e-4))
push!(ss, sprand(100000, 100000, 1e-5))

# 10 entries per line
ts = {}
push!(ts, sprand(1000, 1000, 1e-2))
push!(ts, sprand(10000, 10000, 1e-3))
push!(ts, sprand(100000, 100000, 1e-4))

# 100 entries per line
us = {}
push!(us, sprand(1000, 1000, 1e-1))
push!(us, sprand(10000, 10000, 1e-2))
push!(us, sprand(100_000, 100_000, 1e-3))
#push!(us, sprand(10_00_000, 10_00_000, 1e-5))

# 1000 entries per line
vs = {}
push!(vs, sprand(1000, 1000, 1.0))
push!(vs, sprand(10000, 10000, 1e-1))
push!(vs, sprand(100_000, 100_000, 1e-2))
push!(vs, sprand(10_00_000, 10_00_000, 1e-5))


seed = 2
@testfn ptests
m = us[1]
ptests(m)  # warmup

# @assert full(us[2])[3456:4400,1234:4567]==full(us[2][3456:4400,1234:4567])
# @assert full(us[2])[3456:4400,[1234:4567]]==full(us[2][3456:4400,[1234:4567]])
# @assert full(us[2])[[3456:4400],1234:4567]==full(us[2][[3456:4400],1234:4567])
# @assert ts[3][3405:23455, 5*(305:2345)]== ts[3][[3405:23455], 5*(305:2345)]
# @assert full(us[2])[[3456:3530],1234:4567]==full(us[2][[3456:3530],1234:4567])

# si = 3456:3530
# sj = 1234:4567
# pi = randperm(length(si))
# pj = randperm(length(sj))
# pi = si[pi]
# pj = sj[pj]
# @assert full(us[2])[pi,pj]==full(us[2][pi,pj])

m = ss[3];
#m = ts[3];
m = us[3];
#m = vs[3];
println(" ")
ptests(m)