ENH: Reimplementing the indexing machinery #3798
Conversation
|
Fast paths are horrible beasts -- they increase code paths that need So just a thought, as you're implementing them, you'll probably want On Thu, Sep 26, 2013 at 4:57 PM, seberg [email protected] wrote:
|
|
OK, there is a test failing, but that is not a big deal. I have now replaced the whole MapIter with one that specializes no-subspace (iterating everything in one, even the operand) and subspace iteration (as nested iters). The new MapIter will do iteration order optimization (if an index is visited twice, the order is not guaranteed) and for getitem will not keep the original array order. The code is now generally faster for larger arrays, though for very small advanced indexing operation it is around 1.5x slower. And it is a lot faster for larger subspaces and non C-Order arrays. The big issue remaining issue is that shape mismatch errors are even more cryptic then before (they are reported by NpyIter with axis remapping and all...), and I think I need a dedicated function to replace the errors with something human readable. Anyway, overall, it has converged enough that you can look at it/play with it. Technically I don't think the code will need to change much, unless someone has some comments. |
|
For anyone interested. This has converged quite far. It probably needs a bit readibility fixes for the MapIterNew code, and new tests are still missing. Also the GetMap/SetMap should probably be condensed (could get more inner loop specializations too, but I am not really interested in that right now). BUT: It is definetly in a stage where you can look at it, and should be in a state ready for usage. Numpy tests run through fine, scipy tests run through fine and the broadcasting errors are now nice and clean. The only disadvantage with the code is that it is actually slower for fancy indexing with less then about 100 elements because of the longer set up time of the NpyIter. I will probably do some timings to show the differences clearer. |
|
I added some fast paths (1-d trivial iteration), and if they can be taken it is insanely fast. Uploaded some timings at http://sebastian.sipsolutions.net/indexing_speedup/. Basically the new stuff is much faster unless buffering is used (or the for smaller arrays the special cases cannot be used, i.e. uncontiguous indexes). Especially non |
|
What happens with indexing with integer scalars? Maybe out of scope for this PR, but that case I think has quite severe overheads. |
|
It doesn't have any severe overheads I am aware of (maybe a bit of it was fixed when I sped up the |
|
The speedups here look great. What I'm a bit concerned about is the test coverage here. It would be very useful if it's possible to run this through some C code coverage tool to see if all branches are covered. |
|
The current test coverage is actually not too bad, except maybe for things like non-native byte order, object references, etc. and broadcasting in assignments. I know I have to add a bit of tests there. I uploaded a few timings for simple slicing (basically what I said). You are indeed right about one thing. The current master (and probably also 1.8.x) as a performance bug when indexing |
|
gcov points out a couple of code paths never run (apart from memory allocation error handling), see gh-3979, but coverage looks quite OK. |
|
Thanks a lot, I will have a look at that and add tests for those things that are missing. |
|
Hmmm, @pv maybe you know it, but your coverage commands don't give any output for me. Just too old gcc (4.7.3)? Am on an ubuntu, so somewhat expected it to just work. EDIT: What I mean is of course that the .gcda gcov files are not created |
|
Nvm that. It ran through fine after I deleted the build directory, dunno maybe the script just searched the wrong paths. |
|
Btw. since 1.8. is soon out ;)... This is pretty much done from my side except some new Deprecation tests. I am sure things will crop up, but it is ready for starting review in case someone wants to read 2500 or so lines of code :) (fortunatly they are very linear, except MapIterNew I think). |
There was a problem hiding this comment.
@seberg can you try to keep the existing struct ABI ? If possible, we'd like to keep ABI compatibility in the 1.x branch.
There was a problem hiding this comment.
I hope I did keep everything ABI compatible (well everything that is reasonably to use). This is used in two different tests for ufunc.at and another one more specific, but as of yet not tested for ABI, only for API compatibility. I am aware it still needs checking. I think Thaeno is probably the only project using this API (it was only exposed in 1.8. and that is not even officially released yet).
There was a problem hiding this comment.
this structure was already exposed in at least 1.7 possibly much earlier.
There was a problem hiding this comment.
Maybe the structure, but MapIterArray was not. So nobody could have possibly used it before 1.8.x (though I admit in master it has been possibly a year).
There was a problem hiding this comment.
over which functions is it used in 1.8? I could only find PyArray_MapIterNew which is not exposed.
if it is private we should move it out of the public header into a private one.
There was a problem hiding this comment.
for 1.8 we could at least deprecate PyArrayMapIterObject via comments in the code to avoid that we get new code using it:
What about these:
PyArrayIterObject
PyArrayMultiIterObject
PyArrayNeighborhoodIterObject
can they be deprecated? the first two are probably more commonly used so deprecation of direct access might be premature without existing get/set methods.
There was a problem hiding this comment.
I've already tagged 1.8 and am waiting for Ralf to do the binaries. If we get this figured out, we could maybe do a 1.8.1, but I'd rather figure out something for 1.9. This doesn't fall into the category of a bug fix and it isn't clear to me that we yet have a consensus on what should be done, or for that matter, what has already been done. For instance, IIRC, PyArrayNeighborhoodIterObject goes back several releases. All that makes me loathe to stop the 1.8 process at this point.
There was a problem hiding this comment.
yes lets figure something out for 1.9 and not delay 1.8 any longer.
There was a problem hiding this comment.
I know, nobody has really time for this probably :). But I just tested the multiarray_tests.test_inplace_add compiled with master and ran it with this branch and it works. So I am pretty confident that it is binary compatible for the usage which makes sense, unless there may be some subtleties on other architectures or compilers or so.
There was a problem hiding this comment.
PyArrayIterObject
PyArrayMultiIterObject
PyArrayNeighborhoodIterObject
I haven't checked the others yet, but it looks like PyArrayNeighborhoodIterObject already has functions for accesses, so we could move it into a deprecated file I think. That should not break anyone's code unless we start moving the internals around, at which point folks will probably need to recompile as the functions are inline, i.e., the accesses to struct internals will still be there. So we can guarantee API but not ABI. That is already the case for PyArrayObject, but I don't know if that is widely publicised. It may be that we need to make that a policy, because otherwise we are frozen.
|
@seberg the gcov needs clean rebuild. distutils cant figure out it needs to rebuild itself |
|
Time to get this moving again. I think a first step would be to deprecate direct access to the struct internals, but that would also imply having a compatible fall back, which would vitiate this work. Hmm, we really need to know if people are already accessing the internals, and I don't know how to do that without a deprecation. Thoughts? |
|
I wouldn't mind to resurrect this... People most definetly are accessing the internals, however, I hope (and actually think it is most likely) that "people" is limited to thaeno and possibly one more guy and if nobody tries to be overly smart using it then this does not break compatibility (I am sure thaeno is not). The struct should only be accessed for two reasons (which is how the examples you can find use it) I think 1. to get the operand array (mostly for the dtype) and 2. to check if transposing is necessary. Both of these reasons could easily be moved into a function (or moved into the transpose function itself). However ffor those things I did keep binary compatibility with. I know it is a bit hairy, and we should deprecate the access in any case. Btw. if someone else feels like starting to review, I could move the branch to the numpy repository so that you can just push some changes directly. |
|
have you already tried running some reverse dependencies against the branch? e.g. pandas, pytables, scipy, h5py |
|
I ran the scipy tests before, it was fine. I just ran pandas and it is fine except for finding a pretty fat bug in this code which is fixed now. |
|
@seberg Where is this now? You have quite a few PR's that I'd like to go through, but I'm not sure which ones you consider more or less ready. |
|
This one is good for review. (The doc I didn't update; the npyiter one still needs action; the boolean subtract one mostly needs ping of mailing list again to make sure we really want it I think; the dtype shape also needs decision if it is the right way or not) |
There was a problem hiding this comment.
Is this consistent with the rules?
In [5]: array(1)[(True,)]
Out[5]: array([1])
In [6]: array(1)[[True]]
---------------------------------------------------------------------------
IndexError Traceback (most recent call last)
<ipython-input-6-fc18d566cf7d> in <module>()
----> 1 array(1)[[True]]
IndexError: too many indices for array
There was a problem hiding this comment.
It is a bit curious that scalar booleans return 1D arrays
In [30]: a[True]
Out[30]: array([1])
There was a problem hiding this comment.
Hah, I first thought it looks like a bug too, but it is actually meant like that. I agree, it is non-obvious why this should be right, but of course I am convinced it is ;). The is this an example of why:
def filter_subarrays_with_large_sum(array, large):
"""
arrays : ndarray {..., N}
out : ndarray {1, N}
"""
large_sum = array.sum(-1)
return array[large_sum >= large]
With this change, the result will consistently add one dimension even if array is one dimensional and the 0-d change is the same. No dimension is removed (boolean index is 0-d) but as always one dimension is added. That said, it might be a large change.
This should also fix array-likes
Found by pandas tests...
Undid it by accident.
|
Hmmm, didn't look too long, but I don't quite understand the segfault. I can reproduce it in 3.3 (though not with valgrind) and see the backtrace in gdb, but the |
|
Ok, fixed that bug... I forgot to fix the convert_shape_to_string name in the common.h and somehow that destroyed the return pointer. |
|
0d-arrays are treated as very a special case For the latter case, the fix seems to allow 0d-arrays to be indexed by booleans rather than fixing the previous behaviors, making 0d arrays even more special. Would it be possible instead to make generalized functions of 0d arrays return 0d arrays? (See issue #1421) |
|
This does not add a special case for 0-d arrays being indexed, it changes the treatment of boolean scalars in indexing to be more sensible. Sure, changing the ufunc behaviour would remove the necessity to do it, but even then it would make sense in my opinion (why should So in my opinion it is simply a different issue (and one that I still think might be quite hairy and complex to change). |
|
If there are no more comments in the next day I'm going to put this in. |
|
OK, let's see how this plays. @seberg Adding functions to access the struct internals would be good so we can start down the long road to hiding them. |
ENH: Reimplementing the indexing machinery
7 participants
Current status: Everything works. Some reorganizing is likely necessary, but pending input on that.
TODOs, but they should not require much action.