JuliaLang/julia — pull request #8235 by timholy (2014-09-04 18:16:32+00:00)
Title: WIP: add views founded on cartesian indexing

Here's a demo of what a View type founded on cartesian indexing would look like. This is a complete implementation of the constructor and scalar indexing (i.e., `V[1,2,3,4]` returning a scalar rather than an array); the only big missing piece is creating a view from a view. And has been discussed elsewhere, for some AbstractArray types you'd want specialized implementations.

Very briefly, the way these work is dirt simple:
```
A = rand(10, 10)
B = subview(A, 2:4, 3:5)
```
Given this, `B[1,3]` simply gets directly translated into `A[2,5]`. The big advantage is that this works for any AbstractArray. You won't get optimal performance for BitArrays, but SparseMatrices should work perfectly well straight out of the box, as well as many, many other types of AbstractArrays.

If you look at the code, you'll see that the large majority of functions are one-liners. The one exception is that if you say `B[4]`, then it has to do linear indexing, so it generates the equivalent of
```
i1 = 4
(i2,i1) = divrem(i1, size(B,1))
A[1+i1, 2+i2]
```
But notice there are no loops in here---everything is generated specifically for the problem at hand.

The main issue is that to support both `sub` and `slice` (does ArrayViews.jl even support slices?), you need a lot of methods. In the table below, `ncreate` is the number of constructors generated (actually one for `subview` and one for `sliceview`), and `nindex` is the number of indexing methods (actually one for `getindex` and one for `setindex!`).
```
# Generate methods up to 4 dimensions
julia> @time reload("ArrayViewsAPL")
Warning: replacing module ArrayViewsAPL
ncreate = 30
nindex = 150
elapsed time: 3.632765916 seconds (22582744 bytes allocated)

# Generate methods up to 5 dimensions
julia> @time reload("ArrayViewsAPL")
Warning: replacing module ArrayViewsAPL
ncreate = 62
nindex = 372
elapsed time: 9.111417113 seconds (47277988 bytes allocated)

# Generate methods up to 6 dimensions
julia> @time reload("ArrayViewsAPL")
Warning: replacing module ArrayViewsAPL
ncreate = 126
nindex = 882
elapsed time: 25.07280445 seconds (115817664 bytes allocated, 1.17% gc time)

# Generate methods up to 7 dimensions
julia> @time reload("ArrayViewsAPL")
Warning: replacing module ArrayViewsAPL
ncreate = 254
nindex = 2032
elapsed time: 77.621801799 seconds (324388508 bytes allocated, 0.99% gc time)

# Generate methods up to 8 dimensions
julia> @time reload("ArrayViewsAPL")
Warning: replacing module ArrayViewsAPL
ncreate = 510
nindex = 4590
elapsed time: 261.558635945 seconds (991729360 bytes allocated, 1.01% gc time)
```
The reason I was holding out for stagedfunctions is that you could support arbitrary dimensionality without waiting 5 minutes for the file to finish getting through code lowering. But if people are eager to move forward with this, perhaps we shouldn't wait.