JuliaLang/julia — pull request #5556 by lindahua (2014-01-26 18:24:39+00:00)
Title: WIP: ArrayViews (A systematic array view framework)

Efficient array views have been a long standing issue in Julia. Recently, I decided to tackle this problem again, and thus made this Pull Request.

This PR is actually migrated from [ArrayViews.jl](https://github.com/lindahua/ArrayViews.jl), which I originally created to explore this.

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.

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

- 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.

- Linear indexing over contiguous views are remarkably faster than linear indexing over subarrays (up to 50x - 100x faster) for 2D, 3D and multidimensional cases.

- 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.

- For non-contiguous views, indexing performance is similar to subarrays. (For such cases, the codes for indexing are similar).

- 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.

- Type stability is carefully maintained.