Fast path for block sizes where all blocks have the same size

[KristofferC]

I don't think there is need for a new type, just a bool if the sizes are the same. Scalar indexing could then be made faster since you don't have to search like how it is done now.

[dlfivefifty]

The way I handle this in ApproxFun is to template the type for the row block lengths (RI) and col block lengths (CI):

type BlockBandedMatrix{T,RI,CI} <: AbstractBlockBandedMatrix{T,Matrix{T}}
    data::Vector{T}

    l::Int  # block lower bandwidth
    u::Int  # block upper bandwidth
    rows::RI   # the size of the row blocks
    cols::CI  # the size of the column blocks

    rowblocks::Vector{Int}   # lookup the row block given the row
    colblocks::Vector{Int}   # lookup col row block given the row

    blockstart::BandedMatrix{Int}  # gives shift of first entry of data for each block

    function (::Type{BlockBandedMatrix{T,RI,CI}}){T,RI,CI}(data::Vector{T},l,u,rows,cols)
        new{T,RI,CI}(data,l,u,rows,cols,blocklookup(rows),blocklookup(cols),bbm_blockstarts(rows,cols,l,u))
    end
end

Then you can dispatch on Base.Iterators.Take{Base.Iterators.Repeated{Int64}} to ensure the blocks are constant size. (Note this doesn't ensure square blocks.)

[KristofferC]

Putting them as a type parameter is an idea but is it needed ? I guess better code could be generated if you have kernels operating on blocks and the blocks are small. You could also just pay the cost of one dynamic dispatch call to avoid type parameters but still enable good codegen as is done here
https://github.com/KristofferC/BlockSparseMatrices.jl/blob/master/src/SparseMatrixBSC.jl#L307.

[dlfivefifty]

It might be overkill in this context, though it saves a little bit of memory in addition to allowing dispatch based on block structure. This is more of a savings for BlockBandedMatrix where you can realistically have, say, millions of block rows/columns provided that the bandwidth is small.

[KristofferC]

Why would it save memory (except for N ints for a rank N array)?

[dlfivefifty]

Exactly: if you have N = 1_000_000 blocks you save 8MB of memory due to the array of ints. If the block bandwidth is small, this will be comparable to the memory stored.

Though my example was flawed since Base.Iterators.Take{Base.Iterators.Repeated{Int64}} does not support getindex. In ApproxFun I made my own ApproxFun.Take and ApproxFun.Repeated that support getindex, but that is 100% overkill so I think I withdraw my suggestion.

[KristofferC]

Oh I thought we where talking about storing as type parameters versus storing in the struct. Makes sense now. I want so concerned about memory but the binary search you can avoid when you want to figure out what block a scalar index belong.

[dlfivefifty]

Here's a more realistic proposal: template out the type of block_size, and have multiple versions of BlockSize:

abstract type AbstractBlockSize end

struct BlockSize  <: AbstractBlockSize
…
end

struct ConstantBlockSize <: AbstractBlockSize  # row blocks and col blocks have fixed size, not necessarily square blocks
rowblocksize::Int
colblocksize::Int
end

struct SquareBlockSize <: AbstractBlockSize # row blocks == col blocks, but not necessarily constant
blocksize::Vector{Int}
end

struct ConstantSquareBlockSize <: AbstractBlockSize # row blocks == col blocks and all have same size
blocksize::Int
end

Then users could add their own block sizes for other types of structures. (In my case, rows = blocks = 1:N is important).

Edit: These obviously would need to be generalized to arrays.