Does using a tree merge cause performance degradation for the single node case? If not, we might want to default to that behavior.

For a wide enough tree, no. It actually might improve performance, as the aggregate step can be done in parallel (probably negligible though). Trick is determining what is a sane default number.

These produce different results

In [11]: x.sum(max_leaves=4).visualize('dask.pdf')

In [12]: x.sum(max_leaves={0: 4}).visualize('dask.pdf')

I wouldn't expect much degredation in non-pathological cases. The worst thing we're doing is adding O(log_k n) more tasks.

Suggest renaming max_leaves. I think that your intent of the name was something akin to max_children. There might even be a slicker name than that. I'm trying to think of a term like breadth that might be the converse of a depth of a tree. Perhaps "branching factor", if it wasn't so verbose.

Any thoughts on how hard the combine function for moments will be?

I haven't worked through the gritty details, but at first glance this looks pretty cool to me.

These produce different results

What is the shape of x in that case? If it's not 1d, then I'd expect them to. I definitely need to clean up input verification though, as it occurs to me that I never verify that sorted(axis) == sorted(max_leaves). Need max block combination sizes for all reduction axis.

What is the shape of x in that case? If it's not 1d, then I'd expect them to. I definitely need to clean up input verification though, as it occurs to me that I never verify that sorted(axis) == sorted(max_leaves). Need max block combination sizes for all reduction axis.

x = da.arange(1000, chunks=100)

There is some input validation missing. This is also the motivation behind the "we should test the branching factor explicitly somewhere" comment

I cleaned up the tests, and fixed the bug you pointed out above. Could always test more, but I think the coverage here is pretty good.

Any thoughts on how hard the combine function for moments will be?

It's proving harder than I would like - my tired brain isn't up for mathing it out right now :/. Should be doable though, just need to do some math.

@jcrist what is the status on this? I wouldn't mind using it to redo recent array experiments.

Doesn't support arg_*, var, std, or moment, and could use some more tests. I'm mostly out this week, so I doubt this will be fixed until next week. Should be good to go for redoing the array experiments though, if you don't mind working off non-merged stuff.

I'm not sure if these should have the same name or not.

In [1]: import dask.array as da

In [2]: x = da.random.random((100, 100), chunks=(10, 10))

In [3]: x.mean(axis=0).name
Out[3]: 'reduce-460ea5b3313d36450410978acc2ace95'

In [4]: x.mean(axis=0, max_leaves=6).name
Out[4]: 'reduce-460ea5b3313d36450410978acc2ace95'

Using this branch I've found a speedup from 30s to 5s when doing a reduction of 2GB across a small network of 3 machines. This is only when the reduction required data sharing and was only because we happened to have scattered the data in a way that aligns with this (both defaults cause nice behavior.) There was no speedup or slowdown when the reduction didn't require significant data transfer, though that case was fast anyway (1-2s).

Reasons to keep the keys the same:

• They're mathematically the same result, just computed in different ways

Reasons to keep the keys separate and include max_leaves in tokenize:

• The graphs are quite different, and so assumptions made about same keys having the same dependencies are incorrect.

I made them have the same keys so that it would play well with caching. I could revert this, but it seemed like the correct behavior in my mind. Where do we make assumptions that identical key names have the same dependencies?

Within the distributed scheduler.

Or, more generally, within any scheduler that supports graph updates.

Ah, that makes sense. I don't have strong opinions on this, happy to go either way.

My life will be easier if we include the branching factor within tokenize. It also follows the "when in doubt, disambiguate keys" principle.

I'm still in favor of changing the name away from max_leaves. To me a leaf is strictly at the bottom of a tree. This is a restriction both on leaves and on interior nodes.

Better name suggestion? Some ideas:

• max_children
• max_branches
• branches
• branch_factor
• bfactor

I like max_children and branch_factor

Heuristics sound like they would be valuable. I think that we'll be better able to do this after some use. I could just @jcrist 's help on some other things so I'm still behind a default that is just-a-number for now.

What are your thoughts on the kwarg names above?

I think max_children is better than branch_factor, which is more vague. It still feels more evocative for the particular implementation (using trees) rather than the concept (splitting the reduction into sub-problems).

More options:
split_threshold
max_chunks
max_splits
reduce_limit
subproblem_size
max_subproblems

I think split_threshold is my favorite.

This could use another review. I changed the keyword to split_threshold, added it to set_options, and defaulted at 32. Tests were improved, and all reductions are now supported.

This looks great to me.

+1

I expect this to need some use before we can determine a good default behavior/smart heuristic. I'm going to experiment with the ocean dataset to see how different configurations fair. If others have some workflows they could try this on, it would be much appreciated.

I was playing with this with distributed with @stefanv . Some issues came up

1. The split_threshold kwarg wasn't immediately clear to him (perhaps he can chime in here on his thoughts
2. We ran into an issue about reductions on flexible types while computing a mean. This might be a distributed or a dask.array issue. Some play testing is in order. Flexible type issues arise when you try to call a typical reduction on an array of struct dtype.

There are no docs for this yet, so any suggestions on how to make this more intuitive to use would be much appreciated.

We ran into an issue about reductions on flexible types while computing a mean.

I assume you weren't trying to compute a reduction on a struct array (which doesn't work even in numpy), but instead a bug somewhere in dask/distributed that resulted in the reduction being computed on a struct array? If you remember what computation caused it, it would be nice to be able to reproduce.

The reason split_threshold did not immediately make sense to me is because it contains these two concepts I needed to think about: split and threshold. And threshold is slightly confusing because it could imply "split after this condition" or "split until this condition", with potentially different meanings ("split after n chunks" or "split until you have n chunks").

So, while I don't propose this name, something like split_every_n_chunks would read very straightforwardly. Maybe there's a shorter version of that, like chunks_per_split, split_every, group_chunks, etc.

I like Stefan's names!

On Thu, Dec 3, 2015 at 7:51 PM, Stefan van der Walt
notifications@github.com wrote:

The reason split_threshold did not immediately make sense to me is because it contains these two concepts I needed to think about: split and threshold. And threshold is slightly confusing because it could imply "split after this condition" or "split until this condition", with potentially different meanings ("split after n chunks" or "split until you have n chunks").

So, while I don't propose this name, something like split_every_n_chunks would read very straightforwardly. Maybe there's a shorter version of that, like chunks_per_split, split_every, group_chunks, etc.

Reply to this email directly or view it on GitHub:
#839 (comment)

Sorry, this somehow slipped through. Of the new names, I like split_every the best, when used in a function call (i.e. a.mean(axis=1, split_every=32)). As a global/context config though with set_options, I like split_ever_n_chunks the best, as it's more descriptive. Unsure what's best here. Either way, a better name would be nice.

I'd prefer using the same name in both places if possible.

On Fri, Dec 11, 2015 at 3:01 PM, Jim Crist notifications@github.com wrote:

Sorry, this somehow slipped through. Of the new names, I like split_every
the best, when used in a function call (i.e. a.mean(axis=1,
split_every=32)). As a global/context config though with set_options, I
like split_ever_n_chunks the best, as it's more descriptive. Unsure
what's best here. Either way, a better name would be nice.

—
Reply to this email directly or view it on GitHub
#839 (comment).

Yeah, I wasn't suggesting different names in different spots. Perhaps just go with the more verbose one, as it will probably be set contextually/globally?

I'd prefer split_every over split_every_n_chunks

I think split_every is probably verbose enough. I suspect it would usually
be poor practice to set this globally, given that it depends on the
particular reduction being performed.

On Fri, Dec 11, 2015 at 3:12 PM, Matthew Rocklin notifications@github.com
wrote:

I'd prefer split_every over split_every_n_chunks

—
Reply to this email directly or view it on GitHub
#839 (comment).

Done. See #876.