JuliaLang/julia — pull request #5387 by timholy (2014-01-13 20:33:39+00:00)
Title: RFC: move Cartesian to base

This introduces a new-and-improved version of Cartesian, and rewrites certain functionality from base to use it.

Main points:
- A new macro `@ngenerate` that takes away most of the "wrapper pain" from using Cartesian
- Only a handful of functions have been migrated---I've focused this on the more difficult cases, namely `getindex`, `setindex!`, `reducedim`, and `broadcast`.
- Despite adding `cartesian.jl` (a 400+ line file), this leads to a net _reduction_ of the codebase by approximately 400 lines; almost 800 lines were deleted by reimplementing just those 4 core functions.
- In the case of `broadcast`, the new version is more general in that it supports `AbstractArray`s and not just `StridedArray`s.
- Many functions that have previously been written with linear indexing can be easily re-written. da8f1dd2e2dcc16d2c7374d564f177d2b5baf332 is included as an example of how to do this for a single function, `fill!`.
- Performance for SubArrays is notably better for some the functions that have been migrated over; performance has been approximately maintained in other cases.

TODO:
- From the documentation I didn't quite follow how `broadcast_getindex` and `broadcast_setindex!` are supposed to work (what are the `inds` arrays?); these function have been deleted from this PR, but can be restored if needed.
- Initially I intended to migrate the `BitArray` functions, so that `gen_cartesian_map` could be eliminated. I chickened out in the face of their complexity, but if this PR makes it in we could do that at a later time.

All times are after suitable warmup.

On master:
```
X = zeros(100,100,30,30);
S = sub(X, :, :, :, :);
julia> @time fill!(S, 5);
elapsed time: 0.555467706 seconds (64 bytes allocated)
```
This PR:
```
julia> @time fill!(S, 5);
elapsed time: 0.07676407 seconds (48 bytes allocated)
```
Approximately 7-fold better.

Other times are shown below. Test code is in this [gist](https://gist.github.com/timholy/8407269), as are the results of running `arrayperf` in `test/`.

`reducedim` (first set of rows is for Arrays, 2nd for SubArrays; left column is the region, middle column is timing for master, right column is this PR):
```
1	0.1435	0.1423
2	0.1754	0.1608
3	0.1538	0.1649
4	0.3379	0.3591
(1,2)	0.1339	0.1445
(1,3)	0.1302	0.1361
(1,4)	0.1305	0.1418
(2,3)	0.1574	0.1562
(2,4)	0.1608	0.1572
(3,4)	0.1511	0.1595
(1,2,3)	0.1244	0.1418
(1,2,4)	0.1244	0.142
(1,3,4)	0.129	0.1366
(2,3,4)	0.1572	0.1553
(1,2,3,4)	0.1242	0.1423
1	0.4896	0.3994
2	1.0059	0.4507
3	1.1755	0.4613
4	0.9263	0.5376
(1,2)	0.4883	0.3808
(1,3)	0.7812	0.3811
(1,4)	0.5038	0.3813
(2,3)	1.2748	0.4469
(2,4)	1.0367	0.4485
(3,4)	1.81	0.4545
(1,2,3)	0.4832	0.3807
(1,2,4)	0.4891	0.3809
(1,3,4)	0.6274	0.3814
(2,3,4)	2.8611	0.4469
(1,2,3,4)	0.4828	0.3807
```

```
broadcast:
(10,)	(1,10)	0.5324	0.6126
(10,10)	(10,10)	0.3802	0.4507
(1000,)	(1,1000)	0.0778	0.0641
(10,1,10)	(1,10,10)	0.1142	0.1112
(10,10,1)	(1,10,10)	0.0948	0.0936
(100,1,100)	(1,100,100)	0.0659	0.0566
```

arrayperf results are in the gist.

CC @lindahua, @toivoh.