JuliaLang/julia — pull request #3219 by timholy (2013-05-27 21:42:09+00:00)
Title: Cache-friendly transpose

In working on `Images` and image display with `Cairo`, I was struck by the fact that `transpose()` (which can be used to change the orientation of an image) had an execution time comparable to the time needed to display the image on the screen---meaning, the transpose operation would exact significant overhead.

For largish arrays, this patch speeds up `transpose()` by a typical factor of ~2 or 3; nothing to go crazy over, but enough to make the transpose operation relatively inconsequential. This should enable me to simplify a few aspects of `Image`'s API. For "large" arrays (as large as I could reasonably test on my laptop, anyway) it has approximately the same performance as `FFTW`'s transpose, and is much better for small arrays---that's true even if you get rid of the "short circuit" I put in my algorithm for small arrays. Unlike `FFTW`'s, it also works for `Uint32`, which is the case you care about when working with Cairo. (Although I presume one could get it to handle `Uint32` simply by pretending it's an array of `Float32`---after all, both are simply collections of 4-byte words. Wouldn't work for smaller integer types, however.)

In the following graphs, I've taken issues like memory allocation out of the picture by doing it in advance. "Fold advantage" is relative to a linear-indexing "simple" transpose; anything less than 1 is worse than the simple algorithm, anything bigger is better and reflects improved handling of the cache. Gist with the code used to run these tests: https://gist.github.com/timholy/5659152

For comparison, I also included a direct copy (which is always cache-friendly), so we see how much of a penalty the "work" of transposition incurs compared to other overhead. Just keep in mind that the green line is not really relevant for transposition.

![uint8](https://f.cloud.github.com/assets/1525481/569805/263266a0-c713-11e2-9ecb-fff79a337d32.png)
![uint16](https://f.cloud.github.com/assets/1525481/569806/2c51bba8-c713-11e2-9dfb-3f27acbf1fd0.png)
![uint32](https://f.cloud.github.com/assets/1525481/569807/2ee3b7fe-c713-11e2-9941-4ed9ce323d60.png)
![uint64](https://f.cloud.github.com/assets/1525481/569808/3263f48e-c713-11e2-89f8-792e6a63607e.png)
![float32](https://f.cloud.github.com/assets/1525481/569809/350a69a2-c713-11e2-9d54-d4a915ef68ea.png)
![float64](https://f.cloud.github.com/assets/1525481/569811/36d67154-c713-11e2-91d1-4b1879f5e4fb.png)
![complex32](https://f.cloud.github.com/assets/1525481/569812/38baf508-c713-11e2-9d43-816100454a79.png)
![complex64](https://f.cloud.github.com/assets/1525481/569813/3a7acef4-c713-11e2-9a15-a9cf68064103.png)