RFC: A systematic array view framework

[lindahua]

Efficient array views have been a long standing issue in Julia. Recently, I decided to tackle this problem again, and for this purpose, created a package ArrayViews.jl to explore a generic & efficient approach.

There remains some work to be done, but the framework is largely there. While I will continue to work on this package, I would like to solicit comments here.

The ultimate goal is to move this to the Base when it is ready, to take the place of the current subarray system.

An important feature of this approach is that it has two view types ContiguousView and StridedView. Each strided view is associated with a static number called contiguous rank, which can be used to determine (statically) the contiguousness of a subview thereof.

A contiguous view (with more compact representation and faster indexing) will be returned whenever the contiguousness of a view can be determined statically, thus substantially improving indexing efficiency in a lot of common situations.

[ViralBShah]

This looks really systematic. How does the performance on your benchmarks compare currently?

[tknopp]

@lindahua: This looks fantastic! hopefully this gets in for 0.3 and replaces getindex/setindex! for regular arrays

[lindahua]

@ViralBShah: Here is a brief summary of my benchmark results obtained so far:

1. Indexing over contiguous views are considerably faster than subarrays. For example, traversing view(a, :, i) is about 2x - 3x faster than traversing sub(a, :, i). The speed of traversing view(a, :, i) is comparable to traversing an ordinary array.
2. Linear indexing over contiguous views are remarkably faster than linear indexing over subarrays (up to 50x - 100x faster) for 2D, 3D and multidimensional cases.
3. Since view(a, :, i), view(a, i:j), view(a, i:j, k), view(:, i:j, k), view(:,:,k) and many more cases are statically detected as contiguous (thanks to the systematical approach), many practical use cases can benefit from the performance improvement over contiguous views.
4. For non-contiguous views, indexing performance is similar to subarrays. (For such cases, the codes for indexing are similar).
5. Constructor of views are much more light-weighted. A specific benchmark on view construction shows that for array views, it takes about 0.15 sec (on average) to construct 1 million views, while it takes 1.5 - 1.9 sec to construct the same number of sub-arrays. The overhead of view construction is substantially reduced, and therefore use cases that require constructing a lot of small subviews can also benefit from this.
6. Type stability is carefully maintained.

cc: @StefanKarpinski

[mschauer]

Very nice. Could ArrayViews allow to iterate over the contiguous r dimensional subarrays of a dimension n matrix in a efficient manner?

[lindahua]

The package is basically ready. Now it supports view composition (i.e. views over views) and works well with linear algebra functions. I think it is ready to be migrated to the Base.

@mschauer The interface of view is nearly the same as sub, but with a more efficient internal representation & implementation.

To iterate over sub slices, one may do

a = rand(m, n, k)
for i = 1 : size(a, 3)
    do_something(view(a,:,:,i))
end

This is more efficient than using a[:,:,i] or sub(a,:,:,i).

[mschauer]

Ah, that is good, these contiguous subarrays were a bit underprivileged in Julia compared to APL and J, where operations on those are very well integrated... I guess you know by your usage of the term [rank](http://en.wikipedia.org/wiki/Rank_(J_programming_language%29) . Here also #5405 applies because the syntax changes with the number of dimensions which makes it a bit inflexible.

[lindahua]

For #5405, I like the ellipsis notation. Until that lands, I am not able to support the notation like view(a, ..., i).

However, it is possible to add something like view(a, ellipsis(), i). It is ugly, but it does the job.

[lindahua]

Close in favor of the PR at #5556. Please move the discussions there.