{"action":"created","issue":{"url":"https://api.github.com/repos/JuliaLang/julia/issues/10507","labels_url":"https://api.github.com/repos/JuliaLang/julia/issues/10507/labels{/name}","comments_url":"https://api.github.com/repos/JuliaLang/julia/issues/10507/comments","events_url":"https://api.github.com/repos/JuliaLang/julia/issues/10507/events","html_url":"https://github.com/JuliaLang/julia/pull/10507","id":61077778,"number":10507,"title":"WIP: ReshapedArrays","user":{"login":"timholy","id":1525481,"avatar_url":"https://avatars.githubusercontent.com/u/1525481?v=3","gravatar_id":"","url":"https://api.github.com/users/timholy","html_url":"https://github.com/timholy","followers_url":"https://api.github.com/users/timholy/followers","following_url":"https://api.github.com/users/timholy/following{/other_user}","gists_url":"https://api.github.com/users/timholy/gists{/gist_id}","starred_url":"https://api.github.com/users/timholy/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/timholy/subscriptions","organizations_url":"https://api.github.com/users/timholy/orgs","repos_url":"https://api.github.com/users/timholy/repos","events_url":"https://api.github.com/users/timholy/events{/privacy}","received_events_url":"https://api.github.com/users/timholy/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":3,"created_at":"2015-03-13T14:34:33Z","updated_at":"2015-03-15T19:45:46Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/JuliaLang/julia/pulls/10507","html_url":"https://github.com/JuliaLang/julia/pull/10507","diff_url":"https://github.com/JuliaLang/julia/pull/10507.diff","patch_url":"https://github.com/JuliaLang/julia/pull/10507.patch"},"body":"This one is rather more fun than my last PR. It adds the ability to reshape an arbitrary `AbstractArray` without making a copy, creating a new type of view. The logic and a demonstration of this approach was described in https://github.com/JuliaLang/julia/issues/9874#issuecomment-75979041. Specifically, reshaping does not compose with subarray-indexing, so you really need two types of views (unfortunately).\r\n\r\nTo get good performance out of this, I had to optimize the tar out of it. (Honestly, I tried not to.) Any splatting/slurping was deadly, so I had to manually unpack each element of every tuple. I also had to add `@inline` markers in lots of places. And the performance still isn't great, I think mostly because of tuples (see below). Finally, I stole @simonster's neat work on speeding up `div` (I credited the commit to him), updating it for julia 0.4. I noted that I got errors if I tried to create a multiplicative inverse for 1, so I had to introduce a whole new type just to handle this special case. If any of the smart number-focused folks around here has a  better idea, I'm all ears.\r\n\r\nOne way in which this is incomplete (i.e., won't pass tests)  is that it doesn't allow one to index a ReshapedArray with anything other than (1) a scalar index (linear indexing) or (2) scalar indexing with the full `N` indexes, if the array is `N`-dimensional. I could implement that for `ReshapedArrays` [just like I did for SubArrays](https://github.com/JuliaLang/julia/blob/21199e321d0a8454a5bed07461d4bd160f191d93/base/subarray2.jl#L109-L169), but frankly this kind of stuff is no fun to implement time and time again. I'm hoping @mbauman delivers us a general framework (see https://github.com/JuliaLang/julia/pull/10458#issuecomment-78118593) so that people who implement `AbstractArray`s only need to worry about those two types of indexing.\r\n\r\nThis also won't pass the tests because currently it reshapes a `Range`. Since `Range`s are \"read-only\", I suspect that's not what we want? They are also currently used heavily for creating of arrays in combination with `reshape`.\r\n\r\nFinally, I also took the opportunity to create a performance test suite for our array indexing. The results have revealed a few unexpected trouble spots, particularly for small arrays---the main problems seem to come from extracting tuple fields. Here's the key:\r\n- `sumelt` refers to `for a in A` indexing; `sumeach` to `for I in eachindex(A)`; `sumfast` to `for i = 1:length(A)` _if_ `A` has a fast linear indexing trait set (otherwise it's redundant with `sumeach`).\r\n- `I` refers to integer, `F` to float. The latter is better-SIMDable.\r\n- `s` means small (3-by-5), `b` means big (300-by-500)\r\n- `ArrayLF` has fast linear indexing, `ArrayLS` does not. `ArrayStrides` and `ArrayStride1` are two implementations of very simple strided array types, used for comparison against other types that exploit similar operations.\r\n\r\n```\r\nsumeltIs Array        1.777    2.515    1.813    0.067\r\nsumeachIs Array      17.027   23.399   17.356    0.747\r\nsumfastIs Array       1.025    1.919    1.047    0.047\r\nsumeltIs ArrayLS     13.934   16.032   14.202    0.414\r\nsumeachIs ArrayLS     3.281    5.637    3.362    0.182\r\nsumfastIs ArrayLS     3.315    7.288    3.582    0.546\r\nsumeltIs ArrayLF      3.966    7.565    4.070    0.225\r\nsumeachIs ArrayLF     3.281    4.538    3.368    0.156\r\nsumfastIs ArrayLF     4.069    5.183    4.182    0.157\r\nsumeltIs ArrayStrides   13.890   20.870   16.064    1.337\r\nsumeachIs ArrayStrides    2.492    6.038    2.705    0.397\r\nsumfastIs ArrayStrides    2.639    4.689    2.761    0.253\r\nsumeltIs ArrayStrides1   14.280   16.082   14.558    0.417\r\nsumeachIs ArrayStrides1    3.281    7.003    3.445    0.303\r\nsumfastIs ArrayStrides1    3.315    6.232    3.442    0.267\r\nsumeltIs SubArray     3.144    4.949    3.454    0.290\r\nsumeachIs SubArray   19.258   28.084   20.460    1.716\r\nsumfastIs SubArray   19.183   26.505   19.822    0.908\r\nsumeltIs ReshapedArray{ArrayLS}    3.087    4.647    3.337    0.167\r\nsumeachIs ReshapedArray{ArrayLS}   18.944   21.837   19.382    0.588\r\nsumfastIs ReshapedArray{ArrayLS}   19.711   30.648   20.668    1.440\r\nsumeltIs ReshapedArray{ArrayLF}    4.291    8.029    4.548    0.495\r\nsumeachIs ReshapedArray{ArrayLF}   18.952   24.026   19.500    1.000\r\nsumfastIs ReshapedArray{ArrayLF}    4.205    6.382    4.349    0.288\r\nsumeltFs Array        1.538    2.622    1.599    0.115\r\nsumeachFs Array      18.690   25.214   19.747    1.607\r\nsumfastFs Array       1.299    1.802    1.339    0.069\r\nsumeltFs ArrayLS     14.289   21.898   15.281    1.617\r\nsumeachFs ArrayLS     4.171    7.126    4.339    0.378\r\nsumfastFs ArrayLS     4.171    7.311    4.311    0.363\r\nsumeltFs ArrayLF      4.223    8.144    4.537    0.611\r\nsumeachFs ArrayLF     4.171    5.512    4.313    0.249\r\nsumfastFs ArrayLF     4.240    6.903    4.435    0.264\r\nsumeltFs ArrayStrides   13.638   22.034   16.183    1.387\r\nsumeachFs ArrayStrides    2.552    5.009    2.710    0.322\r\nsumfastFs ArrayStrides    2.618    5.898    2.782    0.378\r\nsumeltFs ArrayStrides1   14.293   24.465   15.856    2.400\r\nsumeachFs ArrayStrides1    4.171    6.993    4.454    0.537\r\nsumfastFs ArrayStrides1    4.171    6.126    4.353    0.316\r\nsumeltFs SubArray     3.076    8.096    3.426    0.474\r\nsumeachFs SubArray   19.343   24.725   20.346    1.318\r\nsumfastFs SubArray   19.450   29.048   20.408    1.721\r\nsumeltFs ReshapedArray{ArrayLS}    3.321    4.863    3.437    0.192\r\nsumeachFs ReshapedArray{ArrayLS}   18.963   29.058   19.810    1.659\r\nsumfastFs ReshapedArray{ArrayLS}   19.740   26.780   21.341    1.947\r\nsumeltFs ReshapedArray{ArrayLF}    4.291    7.570    4.559    0.498\r\nsumeachFs ReshapedArray{ArrayLF}   18.937   25.426   19.814    1.363\r\nsumfastFs ReshapedArray{ArrayLF}    4.205    9.719    4.439    0.432\r\nsumeltIb Array       10.536   14.805   11.133    0.936\r\nsumeachIb Array       6.653   10.035    6.895    0.497\r\nsumfastIb Array       6.131    9.889    6.480    0.607\r\nsumeltIb ArrayLS    136.357  156.693  143.836    4.902\r\nsumeachIb ArrayLS     6.594   11.962    6.951    0.696\r\nsumfastIb ArrayLS     6.640   11.981    7.063    0.778\r\nsumeltIb ArrayLF     10.467   18.773   11.143    1.266\r\nsumeachIb ArrayLF     6.635   11.774    7.071    0.835\r\nsumfastIb ArrayLF     6.171    9.665    6.343    0.304\r\nsumeltIb ArrayStrides  140.613  150.800  145.009    3.801\r\nsumeachIb ArrayStrides   11.023   19.091   11.587    0.989\r\nsumfastIb ArrayStrides   10.999   18.700   11.454    0.755\r\nsumeltIb ArrayStrides1  145.468  152.717  147.724    2.491\r\nsumeachIb ArrayStrides1    6.625   10.784    6.906    0.536\r\nsumfastIb ArrayStrides1    6.602    9.302    6.792    0.300\r\nsumeltIb SubArray    26.313   31.715   27.250    1.178\r\nsumeachIb SubArray    7.205   12.633    7.516    0.573\r\nsumfastIb SubArray    7.192   13.702    7.581    0.760\r\nsumeltIb ReshapedArray{ArrayLS}   21.288   27.281   22.266    1.341\r\nsumeachIb ReshapedArray{ArrayLS}    7.048   10.469    7.369    0.526\r\nsumfastIb ReshapedArray{ArrayLS}    7.037   10.476    7.247    0.376\r\nsumeltIb ReshapedArray{ArrayLF}   10.577   14.395   10.843    0.513\r\nsumeachIb ReshapedArray{ArrayLF}    7.083   11.046    7.308    0.450\r\nsumfastIb ReshapedArray{ArrayLF}    6.181    9.886    6.400    0.430\r\nsumeltFb Array       15.433   17.467   15.789    0.473\r\nsumeachFb Array       3.598    7.467    3.761    0.415\r\nsumfastFb Array       3.362    5.245    3.512    0.196\r\nsumeltFb ArrayLS    140.020  154.997  145.069    4.714\r\nsumeachFb ArrayLS     3.576    6.038    3.745    0.269\r\nsumfastFb ArrayLS     3.575    6.646    3.707    0.292\r\nsumeltFb ArrayLF     15.460   19.912   15.784    0.561\r\nsumeachFb ArrayLF     3.574    5.398    3.676    0.191\r\nsumfastFb ArrayLF     3.401    5.646    3.490    0.197\r\nsumeltFb ArrayStrides  136.608  161.737  143.648    6.908\r\nsumeachFb ArrayStrides   15.453   21.897   16.317    1.018\r\nsumfastFb ArrayStrides   15.445   16.973   15.753    0.434\r\nsumeltFb ArrayStrides1  140.737  241.423  195.276   38.955\r\nsumeachFb ArrayStrides1    3.568    9.799    4.632    0.979\r\nsumfastFb ArrayStrides1    3.566    8.079    3.909    0.654\r\nsumeltFb SubArray    29.383   42.928   32.245    2.760\r\nsumeachFb SubArray    6.774   22.297    9.393    4.191\r\nsumfastFb SubArray   16.320   32.008   17.832    2.597\r\nsumeltFb ReshapedArray{ArrayLS}   51.433   60.201   52.709    1.883\r\nsumeachFb ReshapedArray{ArrayLS}   16.672   31.846   20.355    4.379\r\nsumfastFb ReshapedArray{ArrayLS}   16.650   30.555   17.631    2.464\r\nsumeltFb ReshapedArray{ArrayLF}   10.603   20.125   11.748    1.705\r\nsumeachFb ReshapedArray{ArrayLF}    7.016    9.973    7.474    0.555\r\nsumfastFb ReshapedArray{ArrayLF}    6.157    7.850    6.380    0.294\r\n```\r\nAs you can see, indexing with ReshapedArrays has an unfortunate penalty with respect to Arrays."},"comment":{"url":"https://api.github.com/repos/JuliaLang/julia/issues/comments/81214073","html_url":"https://github.com/JuliaLang/julia/pull/10507#issuecomment-81214073","issue_url":"https://api.github.com/repos/JuliaLang/julia/issues/10507","id":81214073,"user":{"login":"Jutho","id":4162102,"avatar_url":"https://avatars.githubusercontent.com/u/4162102?v=3","gravatar_id":"","url":"https://api.github.com/users/Jutho","html_url":"https://github.com/Jutho","followers_url":"https://api.github.com/users/Jutho/followers","following_url":"https://api.github.com/users/Jutho/following{/other_user}","gists_url":"https://api.github.com/users/Jutho/gists{/gist_id}","starred_url":"https://api.github.com/users/Jutho/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Jutho/subscriptions","organizations_url":"https://api.github.com/users/Jutho/orgs","repos_url":"https://api.github.com/users/Jutho/repos","events_url":"https://api.github.com/users/Jutho/events{/privacy}","received_events_url":"https://api.github.com/users/Jutho/received_events","type":"User","site_admin":false},"created_at":"2015-03-15T19:45:46Z","updated_at":"2015-03-15T19:45:46Z","body":"It's great to see `MultiplicativeInverse`, however I find the name somewhat confusing. It sounds like it is already an inverse, i.e. if `b=MultiplicativeInverse(a)` and I want to compute `div(x,a)`, it sounds like I would need to type `x*b` instead of `div(x,b)`. I was thinking something along the lines of `FastDividingInteger` (but I certainly hope that somebody can come up with a fancier and/or shorter name). Maybe then it could be implement to be a fully supported type of integer (i.e. `abstract FastDividingInteger{T} <: Integer`), such that it can be used just like any other `Integer` (with the promotion rule that as soon as it is combined with another integer, the result is the other integer type, such that not every operation requires to compute the multiplicative inverse information).\r\n\r\nLinear indexing into an `AbstractArray` `A` could then simply be implemented using\r\n`ind2sub(map(FastDividingInteger,size(A)),linearindex)` (together with maybe the improved versions of `ind2sub` in #10337).\r\n\r\nWith respect to `ReshapedArray`: This is very nice. I was wondering, though, whether all the complexity to keep track if certain groups of sizes in the new array match with certain groups of sizes in the old array is worth the gain in efficiency; especially since this cannot be determined at compile time and thus gives rise to type instability in the construction. With the fast multiplicative inverse, wouldn't a simple wrapper type that implements indexing using `ind2sub(fastsizeparent,sub2ind(newsize,index))` [where `fastsizeparent=map(FastDividingInteger,size(parent))` was computed at compile time] be almost as efficient (and type stable)?"}}