Draft of symbolic arrays

[mrocklin]

I wanted to create a symbolic numpy array to help with some scalability issues with Dask. The goal here is to provide a target for high-level array expression optimization.

This is leaning heavily on logic currently in Dask, which seems to be going well. Here is a tiny example:

In [1]: from symbolic_array import Leaf, compute

In [2]: x = Leaf(shape=(10, 10), dtype='float32', name='x')

In [3]: import numpy as np

In [4]: y = np.sin(x)[::2, :5].max(axis=0)

In [5]: y.shape
Out[5]: (5,)

In [6]: y.dtype
Out[6]: dtype('float32')

In [7]: data = np.ones((10, 10), dtype='float32')

In [8]: compute([y], {x: data})
Out[8]: 
(array([0.84147096, 0.84147096, 0.84147096, 0.84147096, 0.84147096],
       dtype=float32),)

In [9]: x
Out[9]: x

In [10]: y
Out[10]: amax(sin(x)[slice(None, None, 2), slice(None, 5, None)], axis=0, keepdims=False)

There are a few things that we would do next if we think this is worth doing:

1. Build out enough of the API to satisfy a commonly used subset of XArray, or some other use case (though I'm currently being paid to think about XArray)
2. Align that API to optimizations we would want to make in dask array, particularly atop fusion and slice-reordering
3. Build those optimizations (non-trivial, but probably doable once we have the expression trees in place)
4. Figure out how to back an XArray by symbolic arrays (possibly hard without NEP-0018)
5. Find people interested in this problem that we can cajole into evolving and maintaining it.

cc @jcrist @shoyer @rabernat @saulshanabrook @jhamman @scopatz

I apologize for the lack of docs but the code here is only 150 lines, and I think it should be pretty digestible to this crowd.

[jhamman]

This looks super cool @mrocklin! Cross referencing with pydata/xarray#2298.

[dhirschfeld]

I'm curious to what extent this overlaps with the functionality previously provided by blaze, and if there's anything to use/learn from that experience?

[shoyer]

Cc @fujiisoup

[fujiisoup]

This looks super nice.

In pydata/xarray#2298, we tried to skip unused computation by interchanging __getitem__ and __array_ufunc__.
I'm curious how easy it is to realize this optimization in symbolic_array (is it exactly the 2nd item in the 'we would do next' ?)

[mrocklin]

I'm curious to what extent this overlaps with the functionality previously provided by blaze, and

There is some obvious overlap.

if there's anything to use/learn from that experience?

This is a somewhat general question. I guess the answer is "yes"? Did you have something in particular in mind?

[mrocklin]

I'm curious how easy it is to realize this optimization in symbolic_array (is it exactly the 2nd item in the 'we would do next' ?)

Well, we would need a function that traverses through the expression tree and manipulates it, returning a new expression tree that is rewritten in the way that we want. There are several ways piece of infrastructure we could build to help people write functions to rewrite graphs, but in principle you could do this with a recursive function.

[saulshanabrook]

Thanks for tagging me in this! Just last week I started implementing a generic array computation library on top of MatchPy. Still very much in flux, but I think the approach is interesting. See an intro notebook and a cross product example.

Some of the symbols are copied from Lenore Mullin's (@womenflyplanes) A Mathematics of Arrays, but @pearu and @hameerabbasi are making some progress documenting those and giving correspondences to NumPy, see this document.

[mrocklin]

Yes, a pattern matching system such as is found in matchpy would be one way to make writing optimizations for the expression tree easier.

[mrocklin]

Thanks for chiming in @saulshanabrook !

It looks like in uarray you're reimagining arrays generally. My guess is that to solve XArray's problems today we would need a symbolic array that would look more-or-less exactly like a numpy array (or a large subset) and lower to a numpy or dask array. Are these constraints reasonable for your work with uarray? (my guess is not, but thought I'd ask)

I'm curious about your experience with MatchPy. Has it met your needs? Anything particularly concerning or encouraging? Do you have a sense on how you would implement @fujiisoup's request (exchanging getitems and elemwise operations) either with the implementation in this repository or with uarray?

[mrocklin]

XArray devs (@shoyer @jhamman @fujiisoup @rabernat) is this symbolic array approach feasible given this task:

Figure out how to back an XArray by symbolic arrays (possibly hard without NEP-0018)

Are we waiting for NEP-0018 to land first or is it reasonable to change XArray to have its own dispatch mechanism.

[saulshanabrook]

My guess is that to solve XArray's problems today we would need a symbolic array that would look more-or-less exactly like a numpy array (or a large subset) and lower to a numpy or dask array. Are these constraints reasonable for your work with uarray?

I do plan on making a duck typed Numpy array that forwards operations to uarray, so that it you could use it where you need the NumPy API. I am thinking about uarray more like an IR, so that would be one frontend for it but it would also be able to build expressions without tying yourself to NumPy's API.

I'm curious about your experience with MatchPy. Has it met your needs? Anything particularly concerning or encouraging?

It mostly has so far. It has a pretty nice developer experience in terms of how the classes are structured and how you create replacements and expressions. Because it's a new library there aren't a ton of examples and it gives you a lot of freedom, so I have found myself rewriting the base a couple of different ways.

Right now I have to manually think about how to write the replacement rules so that two couldn't be applied to the same expression. I have to look more into how it chooses which rules to apply to see if there are some precedences I can depend on. If not, I need to add some kind of automated checking to tell me if I wrote ambiguous rules. Especially since this is an open core kind of thing, I would want others to write their own rules and it is important that you don't end up with non determinism in the compilation.

[saulshanabrook]

Do you have a sense on how you would implement @fujiisoup's request (exchanging getitems and elemwise operations) either with the implementation in this repository or with uarray?

Could you give me a specific example? The way things are defined, indexing operations are lazy. So if you do something equiv to (a + b)[1] it will only evaluate summing that one value. Or even something like np.outer(a, b)[10, 20] it will only evaluate that one part of the outer product, because the outer product is defined by how you index into it (and by it's shape).

[mrocklin]

I think that @fujiisoup is interested in a transformation that would transform graphs like the following:

• Input: (x.T + 1 + 2)[:5]
• Output: x.T[:5] + 1 + 2

The knowledge that uarray already implements this is useful, but I suspect that it would be more informative for the people here to explain a bit about how you wrote this sort of rewrite rule and how it gets applied. I suspect that few people here are familiar with systems like MatchPy.

[womenflyplanes]

Interfering. Being sure two expressions get the same normal form is the test.

On Sun, Sep 23, 2018 at 9:59 AM Matthew Rocklin ***@***.***> wrote: I think that @fujiisoup <https://github.com/fujiisoup> is interested in a transformation that would transform graphs like the following: - Input: (x.T + 1 + 2)[:5] - Output: x.T[:5] + 1 + 2 The knowledge that uarray already implements this is useful, but I suspect that it would be more informative for the people here to explain a bit about how you wrote this sort of rewrite rule and how it gets applied. I suspect that few people here are familiar with systems like MatchPy. — 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/AGsmlKKrPWqyFtMaIqDnRwekTdoMWmlOks5ud5O5gaJpZM4W1Rd6> .

-- "Great spirits have always encountered violent opposition from mediocre minds" - Albert Einstein