@inbounds macro on sparse arrays

General Usage Performance
1

Hi all,

the @inbounds macro can speed up the in-place editing of a standard array by a factor of two; however it has no performance gain for the same task when applied on a sparse matrix. Please see my test functions and @btime benchmarks below. Why is this? Am I using @inbounds wrong on the sparse array / Is this feature not (yet) implemented? / Is there a reason it should not be implemented? I’m happy for any advice.

using BenchmarkTools
using SparseArrays

# test array
const testarr = [1.0, 2.0, 3.0]

# test sparse array
const testsparr = spzeros(3, 1)
testsparr[1, 1] = 1.0
testsparr[2, 1] = 2.0
testsparr[3, 1] = 3.0

# test function on standard array
function test_inbounds(testarr)
    for i=1:50_000_000
        testarr[2] += 2.0
    end
    testarr
end
function test_inbounds2(testarr)
    for i=1:50_000_000
        @inbounds testarr[2] += 2.0
    end
    testarr
end

# test functions on sparse array
function test_inbounds_sparse(testsparr)
    for i=1:50_000_000
        testsparr[2, 1] += 2.0
    end
    testsparr
end
function test_inbounds2_sparse(testsparr)
    for i=1:50_000_000
        @inbounds testsparr[2, 1] += 2.0
    end
    testsparr
end
function test_inbounds3_sparse(testsparr)
    @inbounds for i=1:50_000_000
        testsparr[2, 1] += 2.0
    end
    testsparr
end

benchmark results

@btime test_inbounds(testarr) # 111.919 ms (0 allocations: 0 bytes)
@btime test_inbounds2(testarr) # 48.900 ms (0 allocations: 0 bytes)

@btime test_inbounds_sparse(testsparr) # 551.772 ms (0 allocations: 0 bytes)
@btime test_inbounds2_sparse(testsparr) # 576.797 ms (0 allocations: 0 bytes)
@btime test_inbounds3_sparse(testsparr) # 581.419 ms (0 allocations: 0 bytes)

Best

2

@inbounds let the compiler remove bounds check
https://docs.julialang.org/en/v1/devdocs/boundscheck/index.html

sparse arrays
https://docs.julialang.org/en/v1/stdlib/SparseArrays/index.html
are stored as
Compressed Sparse Column (CSC) format
see also
http://netlib.org/linalg/html_templates/node92.html#SECTION00931200000000000000

Without looking into the code I would say, bounds check doesn’t make any sense when accessing entries in a sparse array/matrix, or in other words, accessing values from a sparse matrix with indices involves special code where bounds checks aren’t needed.

In a normal array the memory location of the indexed value is calculated from the index and the memory size of the array value type. Therefor you can point to memory outside of the array with indices e.g. larger than the length of the array. This is checked with bounds checking and this is what costs some performance. @inbounds switches these checks off in normal arrays. In a sparse array there is nothing to switch off.

4 Likes
3

ok that makes sense, thanks a lot!