JuliaLang/julia — pull request #4427 by timholy (2013-10-03 10:11:32+00:00)
Title: Faster linear indexing for SubArrays, dims 1-5

Since many of the algorithms in base working on `AbstractArray`s use linear indexing, it seemed reasonable to write hand-tuned linear-indexing for the most commonly-used dimensions. This is still much slower than cartesian indexing, but a big improvement over what we have now. In 5 dimensions the improvement is something like 40-fold, as shown below.

Test script:
```
function linearfill!(A::AbstractArray)
for i = 1:length(A)
A[i] = i
end
A
end

A2 = zeros(1000,1000)
B2 = sub(A2, :, :)
linearfill!(A2)
print("Array 2d: ")
@time linearfill!(A2)
Ac = copy(A2)
linearfill!(B2)
print("SubArray 2d: ")
@time linearfill!(B2)
@assert A2 == Ac

...
```
and so forth up through 5 dimensions (always with `10^6` total elements).

Before this patch:
```
julia> include("/tmp/test_linear.jl")
Array 2d: elapsed time: 0.001823028 seconds (48 bytes allocated)
SubArray 2d: elapsed time: 0.025735556 seconds (64 bytes allocated)
Array 3d: elapsed time: 0.001867426 seconds (48 bytes allocated)
SubArray 3d: elapsed time: 0.372512698 seconds (103983712 bytes allocated)
Array 4d: elapsed time: 0.002026042 seconds (48 bytes allocated)
SubArray 4d: elapsed time: 2.425155532 seconds (521105744 bytes allocated)
Array 5d: elapsed time: 0.001645669 seconds (48 bytes allocated)
SubArray 5d: elapsed time: 3.028932076 seconds (662305792 bytes allocated)
```
In 5d, it's approximately 2000-fold slower to use a `SubArray`.

With this patch:
```
julia> include("/tmp/test_linear.jl")
Array 2d: elapsed time: 0.00195559 seconds (6896 bytes allocated)
SubArray 2d: elapsed time: 0.027324321 seconds (64 bytes allocated)
Array 3d: elapsed time: 0.001553236 seconds (48 bytes allocated)
SubArray 3d: elapsed time: 0.047140215 seconds (64 bytes allocated)
Array 4d: elapsed time: 0.001706639 seconds (48 bytes allocated)
SubArray 4d: elapsed time: 0.064958196 seconds (64 bytes allocated)
Array 5d: elapsed time: 0.001624899 seconds (48 bytes allocated)
SubArray 5d: elapsed time: 0.086291385 seconds (112 bytes allocated)
```
Now in 5d it's a mere 50-fold slower to use a `SubArray`. The main remaining issue is that `div` is approximately ten-fold more expensive than `*` and `/`.