-
-
Notifications
You must be signed in to change notification settings - Fork 127
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Support Everything that XArray Expects #1
Comments
I updated the check-list (apparently I'm an "Owner" for pydata) to drop "insert/fancy indexing" and add a three-item checklist for indexing instead. |
Do we have partial XArray compatibility or does XArray fail with |
@hameerabbasi Not yet, see pydata/xarray#1375. But From a usability perspective, the most helpful additional feature would be nan-skipping aggregations. I know In addition to the direct uses, xarray uses |
I just tested with your example code, NaN-skipping aggregations use >>> class A(np.ndarray):
... def __array_ufunc__(self, *args, **kwargs):
... print('ufunc', args, kwargs)
...
>>> np.nansum(np.arange(5).view(A))
ufunc (<ufunc 'add'>, 'reduce', A([0, 1, 2, 3, 4])) {'axis': None, 'dtype': None, 'keepdims': False} Although I have absolutely now idea how to discern that this was NaN skipping from the args/kwargs. |
Ah, it was a >>> np.nansum(np.arange(5, dtype=np.float).view(A))
ufunc (<ufunc 'isnan'>, '__call__', A([0., 1., 2., 3., 4.])) {}
ufunc (<ufunc 'add'>, 'reduce', A([0., 1., 2., 3., 4.])) {'axis': None, 'dtype': None, 'keepdims': False} So we're good to go on those already. :-) Edit: Concrete example: >>> ar = sparse.DOK((2, 2))
>>> ar[1, 1] = np.nan
>>> s = sparse.COO(ar)
>>> np.nansum(s)
0.0 |
FWIW this is a great demonstration of the value of NumPy's use of protocols. It would be great if we could get an alternative ndarray implementation, |
I was also considering sparse arrays with different fill values. However, some operations (such as |
NumPy's nan-aggregations work, but only by converting sparse arrays into numpy arrays, inside import numpy as np
import sparse
class NoncoercibleCOO(sparse.COO):
def __array__(self, *args, **kwargs):
raise Exception('cannot convert to numpy')
ar = sparse.DOK((2, 2))
ar[1, 1] = np.nan
s = NoncoercibleCOO(ar)
np.nansum(s) This results in:
So this really isn't a good solution yet :). You might actually view this as the flip side of implementing protocols (like |
Is this already reported upstream in NumPy? |
Hmm. So for this what we really want is something like: implement |
I think this could be quite interesting indeed. NaN (which pandas's SparseArray uses) is the most obvious other default value to support. Even
I don't know if this really qualifies as a bug, so much as an unintended consequence. I think the easiest fix would be to replace |
A simpler option would be to add Edit: And Edit: Or maybe in |
I meant supporting arbitrary fill values. This would make many dense operations automatically possible, e.g. You might, for example, do |
Yes, I see the elegance in that. NaN has a nice property (like zero) that NaN * anything -> NaN. This could make some operations easier to implement if the general fill value is not viable. |
The fill value is viable, and pretty easy to implement. I would just need to make a decorator that could be used to filter out operations that require a zero fill value, and could be used like this: @zero_fill_value
dot(a, b)
... |
I recently raised an issue of nan-aggregation in numpy/numpy#10456, but it looks a little hard to implement nan-aggregations without copy. |
The main issue I see with the three-argument version of If someone can come up with an easier way to do N-way broadcasting of sparse arrays rather than just repeating them over and over... I'd be all for it. Broadcasts in Numpy are views... Here they're separate objects (repeats), with all the memory and performance losses that come with that. Edit: Also the performance speedups when one of the operators returns zeros when one side is zero (like Edit 2: Currently, I've optimised |
I just realized there is a complicated (yet, hiding in plain sight) way to recursively reduce an N-way broadcast down into a 2-way/1-way (without losing out on any performance benefits). It will also simplify the code hugely. I'll try it today and tomorrow, maybe I'll come up with something genius. |
In practice broadcasting for |
The broadcasting is turning out to be more complex than I anticipated (it took the most of last weekend).
|
@hameerabbasi what exactly is a involved in the "match" you're proposing? My initial thought is that an algorithm for this could simultaneously iterate over all input arguments exactly once each. Assuming sorted coordinates, this looks something like: # warning: untested!
iter_coords = [iter(input.coords) for input in inputs]
iter_datas = [iter(input.data) for input in inputs]
indices = [next(it) for it in iters]
result_coords = []
result_data = []
num_finished = 0
while True:
current_index = min(indices)
current_data = [next(it_data) if current_index == index else input.fill_value
for it_data, index, input in zip(iter_data, indices, inputs)]
result_coords.append(current_index)
# in reality, we probably save an explicit indexer array in each input's data,
# using -1 for fill-values, and then compute the result data once by applying
# it to 1D vectors
result_data.append(func(*current_data))
next_indices = []
for it, index in zip(iter_coords, indices):
if current_index == index:
index = next(it, default=None)
if index is None:
num_finished += 1
if num_finished == len(inputs):
break
next_indices.append(index) This would runtime O(NK), where |
Since my last comment was a mishmash of incoherent half-formed thoughts, I'm re-commenting. This is much simpler than what I had in mind, and can be easily extended to a broadcasting scenario. The main problem I see with something like this is the following: Consider two arrays If this optimization can somehow be ported to your method (I don't see how, unfortunately, while keeping broadcasting), I'd be perfectly willing to write up a Cython equivalent of it. To answer your original question, a "match" is a calcultation of where input 1 is nonzero, input 2 is zero, and so on... For every possible combination. |
It seems like the solution we need here is a "sparse broadcast" function, which only repeats non-zero indices in the result. . The algorithm would look something like:
"sparse" vs "regular" broadcasting could be chosen based on the nature of the operator being applied (e.g., |
That's (roughly) what I'm doing with my matching setup. I do the following (in psuedocode):
Edit: The matching setup is on a branch on my fork, it isn't in the main codebase, and it isn't in working condition yet. It needs more work. Edit 2: Choosing it based on the operator is still troublesome for some edge cases involving |
I don't think it's necessary to iterate through every possible combination of zero/nonzero inputs. Maybe something like:
If you are concerned about the (constant factor) overhead for explicit broadcasting in cases like |
What I'm more concerned about is:
Some things that could be made independent of the implementation:
To be perfectly clear, I would prefer your approach much more (it is undeniably more performant in the "dense" broadcasting case) if these edge-cases etc. could be nicely handled automatically. |
The property you need here is
So sure, the way this works is fill-value specific, but you could store the list of these identities and operations in a table.
This feels like a separate issue to me. How do you handle this in your current approach? One option is to keep track of the finiteness of sparse arrays, e.g., by adding a (possibly cached)
I think I finally understand your approach: you are actually computing I would suggest adding an |
If you're asking how we "match" for a particular combination of zero/nonzero inputs, we:
At the end, we simply concatenate all possible data/coords and return the result. |
I've implemented N-ary broadcasting following the algorithm here over in #98. Feedback welcome. :) |
OK, I'm hearing the following thoughts (paraphrasing):
These both seem like reasonable positions to me. I wonder if we can accomplish both by having optional parameters to elemwise that specify which inputs propagate zeros elemwise(operation.mul, x, y, z, zero_prop=[0, 1, 2])
or
elemwise(operation.add, x, y, z, zero_prop=[]) With perhaps values like This is only an example of such an argument. There are many more complex situations that might arise, but I suspect that this handles the common case. I do think that some static information like this is likely to be desirable when we start profiling. Also, I suspect that most use of |
Alternativley, what is our current support for operations that have non-zero return values when one of the inputs is zero? My guess was that we erred. If this is the case then can we just ignore the situation where we produce values on zero-valued inputs? Am I understanding things correctly? |
I agree 100% with this. But (at the risk of repeating myself), this ignores the
Currently, we err iff |
@shoyer I don't suppose you happen to have a TestCase for what an XArray container class should support do you? If so it would be good to import that into our test suite to track progress in the future between the projects. |
No, not yet, unfortunately. Historically, the API for xarray container
classes has evolved in a dynamic way based on what we needed for numpy +
dask. We'll need to do some internal clean-up before we can support sparse
arrays well.
…On Wed, Feb 21, 2018 at 6:24 AM Matthew Rocklin ***@***.***> wrote:
@shoyer <https://github.com/shoyer> I don't suppose you happen to have a
TestCase for what an XArray container class should support do you? If so it
would be good to import that into our test suite to track progress in the
future between the projects.
—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
<#1 (comment)>, or mute
the thread
<https://github.com/notifications/unsubscribe-auth/ABKS1nYsOS6VNgx8ninOXeEf-QPNHwL-ks5tXCc5gaJpZM4M-1J4>
.
|
Feel free to ping me or involve me in the project. :-) |
Three-argument version of |
@shoyer what is the right thing for folks to push on here if they have time? The multipledispatch VarArgs conversation? Internal fixes to XArray? A test suite? |
My intuition would be the multipledispatch VarArgs conversation. We should do things properly. 😄 I don't mind it taking time, it'll save time and headache down the road. Of course, if the consensus is on another solution, I'd happily work on that, too. |
VarArgs will be needed for finishing this in xarray, but really only for a few functions (concatenate and stack). So I think we could simultaneously work on:
|
Since the final review deadline for the papers in SciPy 2018 is June 18, I thought I'd revive this thread. I'd love to show off Dask/Sparse and XArray/Sparse integration in the paper and at SciPy 2018. cc @mrocklin @shoyer If you need anything done on my end, or anything at all you think I'm capable of that'd speed this along (Including contributing to XArray or Dask, I'd love to dip my feet in), don't hesitate to say so. I looked into |
Experiments with dask.array and sparse would be welcome. I think that this should work today (we do include some tests here in dask.array's CI). It might be interesting to do profile a few workflows. I'll think a bit about what these might be. For XArray my guess is that the right thing to do is to follow @shoyer 's two paths listed just above. Looking at duck_array_ops.py and how that functionality gets used within XArray seems like a sensible place to start, though @shoyer may have other suggestions (I don't know this codebase as well). My guess is that there some work to get through here, but probably nothing that is too controversial. |
It also looks like the conversation in mrocklin/multipledispatch#72 ended in a nice place. Again, it seems like consensus was reached and now this requires some hopefully straightforward work. |
I’ve implemented outer indexing for a single array, but not multiple. When NumPy implements oindex and vindex, we’ll follow suit. I somehow don’t feel like implementing every single fancy index case with its weird behaviour. |
Not sure if this is the right place to mention, but it doesn't appear elsewhere in issues/PRs on the repo. I ran into the following trying to call
There were other similar cases. So far I've noticed:
|
@khaeru Do you have use-cases for these for sparse arrays? If so, please raise separate issues for each missing function. In a lot of cases, one can’t achieve better performance on these than dense arrays. |
@hameerabbasi the concern is less performance than being able to use the DataArray API as it is defined without a bunch of extra wrapper code—what I understood as the topic of this issue, given the title. My current mitigation is to have a subclass that allows some of these calls by converting to dense/numpy.ndarray-backed DataArray, performing the operation, then re-converting to sparse.COO-backed. I know that subclassing the xarray classes is not encouraged, I would be very happy to not have to do that :) I'll do as you suggest and open an issue for one example. |
bolt-project/bolt#58
int
/slice
)int
,slice
and 1d integer arrays separately applied to each axis)The text was updated successfully, but these errors were encountered: