JuliaLang/julia — pull request #5393 by timholy (2014-01-14 12:41:21+00:00)
Title: WIP: arrayref performance for high dimensions?

(This is not really a PR, it's a bug/issue report disguised as a PR to make it easier to talk about and for others to do their own testing.)

Thanks to some great work by Jeff, julia's built-in `arrayref`---which implements both linear and cartesian indexing of arrays---now has amazing performance: in most cases you can't distinguish its performance between cartesian and linear indexing, _even_ in cases where that linear index is computed efficiently because the order of access follows a pattern. I've illustrated that by running `test/arrayperf` in two situations: one against current master which uses linear indexing to implement `getindex` for arrays, and the one in this PR in which the linear-indexing code is deleted and `getindex` falls back to the implementation for `AbstractArray`s (which uses cartesian indexing). The complete results for `getindex` are posted in [this gist](https://gist.github.com/timholy/8417617).

There are a few oddities (noise due to garbage-collection?), but to me the overall pattern suggests we don't need linear indexing. But there's one consistent exception, illustrated for this example but common to all of the tests:
```
Slicing with contiguous blocks (cartesian case):
Small arrays:
1 dimensions (2500000 repeats, 10000000 operations): elapsed time: 0.625764791 seconds (299991840 bytes allocated)
2 dimensions (2500000 repeats, 10000000 operations): elapsed time: 0.97220765 seconds (420500120 bytes allocated)
3 dimensions (625000 repeats, 10000000 operations): elapsed time: 1.096706901 seconds (419835400 bytes allocated)
4 dimensions (625000 repeats, 10000000 operations): elapsed time: 1.048247011 seconds (431500132 bytes allocated)
5 dimensions (156250 repeats, 10000000 operations): elapsed time: 0.467072104 seconds (207361056 bytes allocated)
6 dimensions (156250 repeats, 10000000 operations): elapsed time: 0.496604407 seconds (210810456 bytes allocated)
7 dimensions (39063 repeats, 10000128 operations): elapsed time: 0.3508091 seconds (121212592 bytes allocated)
8 dimensions (39063 repeats, 10000128 operations): elapsed time: 2.864820923 seconds (1322590144 bytes allocated)
9 dimensions (9766 repeats, 10000384 operations): elapsed time: 3.00026783 seconds (1377019176 bytes allocated)
10 dimensions (9766 repeats, 10000384 operations): elapsed time: 3.102930591 seconds (1457233652 bytes allocated)
```
Notice that the performance of `arrayref` falls off a cliff at 8 dimensions. Is this something that can be fixed? Or is this really hard?