JuliaLang/julia — pull request #8501 by timholy (2014-09-28 03:27:10+00:00)
Title: WIP: new array views based on stagedfunctions

Here's my updated proposal for an Array view type. With many different implementations and names floating around (ArrayViews, View, ArrayViewsAPL), to distinguish this one I decided on a bold and innovative name: `SubArray`.

However, these aren't the SubArrays your grandma played with out behind the old tire swing:

- They are based on stagedfunctions. Both construction and cartesian indexing should be fast. (Haven't had time to benchmark yet.) I expect the performance to still be slightly behind arrays, and it will likely stay that way until tuples get inlined in `type`s.
- In addition to supporting "strided" views, these also support non-strided views (a `Vector{Int}` along any axis)
- Unlike our current SubArrays, they support all kinds of whacky stuff, like changing dimensionality (`A = reshape(1:120,5,4,6); B = sub(A, 1:5, 3:18)`).

I realized only recently that these last two properties are required if we're going to consistently return views from indexing. Getting this working properly was the trickiest part.

This container also shares a number of features with our current SubArrays:
- They support arbitrary AbstractArrays
- They support `slice`s (dropping scalar-indexed dimensions) as well as `sub/getindex` style indexing.

This doesn't make the transition to returning views from indexing. I think we should merge the container and #8432 first, give them a little shaking out, and see where we stand. I already know of a couple likely performance bottlenecks, which I've annotated with comments.

This gets much of the way through all of our tests, but seems to uncover a bug with stagedfunctions in the `broadcast` tests. So this shouldn't be merged until that gets fixed. (I'll document that later after I've had a little time to investigate.)

@simonster, `merge_indexes_div` would be fertile territory for your contemplated `div` speedups.

Also, over at https://github.com/timholy/ArrayViewsAPL.jl (where all the development actually happened), I have a much-expanded set of tests. If desired, I can merge these into base.