Drop size 0 arrays in concatenate #4167

jakirkham · 2018-11-02T00:46:29Z

If a size 0 array shows up in concatenate, it doesn't contribute any data. So it would be good to drop these terms from the sequence to avoid unnecessary constraints on computations.

To-do: Handle case with all size 0 arrays.

Tests added / passed
Passes flake8 dask

Make sure that `da.concatenate` does not include empty arrays in the result as they don't contribute any data.

If any of the arrays passed to `da.concatenate` has a size of 0, then it won't contribute anything to the array created by concatenation. As such make sure to drop any size 0 arrays from the sequence of arrays to concatenate before proceeding.

dask/array/core.py

shoyer · 2018-11-02T18:04:39Z

Size 0 arrays don't affect the values, but they could change the dtype, e.g., note

>>> np.concatenate([np.zeros((0,), dtype=float), np.zeros((1,), dtype=int)]).dtype
dtype('float64')

jakirkham · 2018-11-02T18:12:04Z

Thanks for that. Didn't catch the type point when playing earlier.

Also they can affect final shape in some cases.

In [1]: import numpy as np                                                                                                                                   

In [2]: np.concatenate([np.empty((0, 2, 4)), np.empty((0, 2, 3))], axis=2)                                                                                   
Out[2]: array([], shape=(0, 2, 7), dtype=float64)

hmaarrfk · 2018-11-02T20:22:28Z

https://docs.scipy.org/doc/numpy-1.15.0/reference/generated/numpy.result_type.html

jakirkham · 2018-11-03T21:49:50Z

Yeah, there is a da.result_type that we could use to accomplish that.

jakirkham · 2018-11-05T17:10:24Z

Am wondering if we should solve this problem at an even higher level. Namely optimizing out empty chunks from the graph entirely. ( #4173 )

jrbourbeau · 2019-05-20T16:40:03Z

I recently had someone bring the issue of size 0 arrays affecting the output of da.concatenate to my attention. For example,

import numpy as np
import dask.array as da

x_np = np.concatenate([np.zeros(0), np.zeros(1)])
x_da = da.concatenate([da.zeros(0), da.zeros(1)])

result_np = np.concatenate([x_np, x_np])
result_da = da.concatenate([x_da, x_da])

print(f'result_np = {result_np}')
print(f'result_da = {result_da.compute()}')

outputs

result_np = [0. 0.]
result_da = []

The proposed solution of dropping size 0 arrays seems like a reasonable fix to me. I'm happy to help move this along by pushing commits to this PR, if that's okay with you @jakirkham

jakirkham · 2019-05-20T17:24:35Z

Maybe we should bring this up as core work? Though I'm not sure entirely how to propose it.

mrocklin · 2019-05-20T17:27:38Z

Click "Projects" above

jakirkham · 2019-05-20T17:30:06Z

Ah ok. Was trying to do it from the project board. Thanks for the pointer.

…e_arrs

jrbourbeau · 2019-05-22T01:47:53Z

@jakirkham I pushed some commits to ensure that the output dtype and case when all inputs to da.concatenate have 0 size are handled properly, so I think this should be ready for another review

Avoids the need to cast later and the addition of another node to the graph.

jakirkham

Thanks @jrbourbeau. Pushed a few commits to tidy some things as this has simplified the code a bit. Hope that is ok. Think there is one outstanding issue to address (noted below).

dask/array/core.py

There was some left over type promotion code for the arrays to concatenate using their `dtype`s. However this should now use the `_meta` information instead since that is available.

NumPy will raise if no arrays are provided to concatenate as it is unclear what to do. This adds a similar exception for Dask Arrays. Also this short circuits handling unusual cases later. Plus raises a clearer exception than one might see if this weren't raised.

…_arrs

Needed to handle the case where all arrays have trivial shapes.

jakirkham · 2019-06-12T18:36:26Z

Broke out some smaller pieces from this into PR ( #4925 ) and PR ( #4927 ), which have been integrated.

Have updated to include the latests changes from master (including _meta).

Finally pushed some fixes to address some of the remaining issues. This is passing for me locally.

Would be great to get another review if someone has a chance.

jrbourbeau

Thanks for all your work on this @jakirkham! This generally looks good to me. I've attached a couple of questions and a few nitpicky comments

dask/array/core.py

Co-Authored-By: James Bourbeau <[email protected]>

jakirkham · 2019-06-12T20:40:17Z

Thanks @jrbourbeau. Think I've addressed your concerns. So please give it another look.

jrbourbeau · 2019-06-12T22:16:52Z

The Travis build failure here is due to dropping Python 2.7 in #4919 and can be ignored

jakirkham · 2019-06-13T15:02:29Z

The Travis build failure here is due to dropping Python 2.7 in #4919 and can be ignored

Have merged with master. So this should be fixed.

Simplifies the `_meta` handling logic in `concatenate` to assume that `_meta` is valid. As all arguments have been coerced to Dask Arrays, this is a reasonable assumption to make.

jakirkham · 2019-06-13T15:18:36Z

@jrbourbeau, could you please take another look?

jrbourbeau

This looks good to me. Thanks for all your work on this @jakirkham! Merging on green

jakirkham · 2019-06-13T16:26:26Z

Thanks for the reviews.

Have raised an issue about doing this for da.stack as well. ( #4928 )

commit 66531ba Author: jakirkham <[email protected]> Date: Thu Jun 13 12:13:55 2019 -0400 Drop size 0 arrays in concatenate (dask#4167) * Test `da.concatenate` with size 0 array Make sure that `da.concatenate` does not include empty arrays in the result as they don't contribute any data. * Drop size 0 arrays from `da.concatenate` If any of the arrays passed to `da.concatenate` has a size of 0, then it won't contribute anything to the array created by concatenation. As such make sure to drop any size 0 arrays from the sequence of arrays to concatenate before proceeding. * Handle dtype and all 0 size case * Cast inputs with asarray * Coerce all arrays to concatenate to the same type * Drop obsoleted type handling code * Comment on why arrays are being dropped * Use `np.promote_types` for parity w/old behavior * Handle endianness during type promotion * Construct empty array of right type Avoids the need to cast later and the addition of another node to the graph. * Promote types in `concatenate` using `_meta` There was some left over type promotion code for the arrays to concatenate using their `dtype`s. However this should now use the `_meta` information instead since that is available. * Ensure `concatenate` is working on Dask Arrays * Raise `ValueError` if `concatenate` gets no arrays NumPy will raise if no arrays are provided to concatenate as it is unclear what to do. This adds a similar exception for Dask Arrays. Also this short circuits handling unusual cases later. Plus raises a clearer exception than one might see if this weren't raised. * Test `concatenate` raises when no arrays are given * Determine the concatenated array's shape Needed to handle the case where all arrays have trivial shapes. * Handle special sequence cases together * Update dask/array/core.py Co-Authored-By: James Bourbeau <[email protected]> * Drop outdated comment * Assume valid `_meta` in `concatenate` Simplifies the `_meta` handling logic in `concatenate` to assume that `_meta` is valid. As all arguments have been coerced to Dask Arrays, this is a reasonable assumption to make. commit 46aef58 Author: James Bourbeau <[email protected]> Date: Thu Jun 13 11:04:47 2019 -0500 Overload HLG values method (dask#4918) * Overload HLG values method * Return lists for keys, values, and items * Add tests for keys and items commit f9cd802 Author: mcsoini <[email protected]> Date: Thu Jun 13 18:03:55 2019 +0200 Merge dtype warning (dask#4917) * add test covering the merge column dtype mismatch warning * for various merge types: checks that the resulting dataframe has either no nans or that a UserWarning has been thrown * Add warning for mismatches between column data types * fixes issue dask#4574 * Warning is thrown if the on-columns of left and right have different dtypes * flake8 fixes * fixes * use asciitable for warning string commit c400691 Author: Hugo <[email protected]> Date: Thu Jun 13 17:38:37 2019 +0300 Docs: Drop support for Python 2.7 (dask#4932) commit 985cdf2 Author: Benjamin Zaitlen <[email protected]> Date: Thu Jun 13 10:38:15 2019 -0400 Groupby Covariance/Correlation (dask#4889) commit 6e8c1b7 Author: Jim Crist <[email protected]> Date: Wed Jun 12 15:55:11 2019 -0500 Drop Python 2.7 (dask#4919) * Drop Python 2.7 Drops Python 2.7 from our `setup.py`, and from our test matrix. We don't drop any of the compatability fixes (yet), but won't be adding new ones. * fixup commit 7a9cfaf Author: Ian Bolliger <[email protected]> Date: Wed Jun 12 11:44:26 2019 -0700 keep index name with to_datetime (dask#4905) * keep index name with to_datetime * allow users to pass meta * Update dask/dataframe/core.py put meta as explicit kwarg Co-Authored-By: Matthew Rocklin <[email protected]> * Update dask/dataframe/core.py remove meta kwargs.pop Co-Authored-By: Matthew Rocklin <[email protected]> * remove test for index * allow index commit abc86d3 Author: jakirkham <[email protected]> Date: Wed Jun 12 14:20:59 2019 -0400 Raise ValueError if concatenate is given no arrays (dask#4927) * Raise `ValueError` if `concatenate` gets no arrays NumPy will raise if no arrays are provided to concatenate as it is unclear what to do. This adds a similar exception for Dask Arrays. Also this short circuits handling unusual cases later. Plus raises a clearer exception than one might see if this weren't raised. * Test `concatenate` raises when no arrays are given commit ce2f866 Author: jakirkham <[email protected]> Date: Wed Jun 12 14:09:35 2019 -0400 Promote types in `concatenate` using `_meta` (dask#4925) * Promote types in `concatenate` using `_meta` There was some left over type promotion code for the arrays to concatenate using their `dtype`s. However this should now use the `_meta` information instead since that is available. * Ensure `concatenate` is working on Dask Arrays

commit 255cc5b Author: Justin Waugh <[email protected]> Date: Mon Jun 17 08:18:26 2019 -0600 Map Dask Series to Dask Series (dask#4872) * index-test needed fix * single-parititon-error * added code to make it work * add tests * delete some comments * remove seed set * updated tests * remove sort_index and add tests commit f7d73f8 Author: Matthew Rocklin <[email protected]> Date: Mon Jun 17 15:22:35 2019 +0200 Further relax Array meta checks for Xarray (dask#4944) Our checks in slicing were causing issues for Xarray, which has some unslicable array types. Additionally, this centralizes a bit of logic from blockwise into meta_from_array * simplify slicing meta code with meta_from_array commit 4f97be6 Author: Peter Andreas Entschev <[email protected]> Date: Mon Jun 17 15:21:15 2019 +0200 Expand *_like_safe usage (dask#4946) commit abe9e28 Author: Peter Andreas Entschev <[email protected]> Date: Mon Jun 17 15:19:24 2019 +0200 Defer order/casting einsum parameters to NumPy implementation (dask#4914) commit 76f55fd Author: Matthew Rocklin <[email protected]> Date: Mon Jun 17 09:28:07 2019 +0200 Remove numpy warning in moment calculation (dask#4921) Previously we would divide by 0 in meta calculations for dask array moments, which would raise a Numpy RuntimeWarning to users. Now we avoid that situation, though we may also want to investigate a more thorough solution. commit c437e63 Author: Matthew Rocklin <[email protected]> Date: Sun Jun 16 10:42:16 2019 +0200 Fix meta_from_array to support Xarray test suite (dask#4938) Fixes pydata/xarray#3009 commit d8ff4c4 Author: jakirkham <[email protected]> Date: Fri Jun 14 10:35:00 2019 -0400 Add a diagnostics extra (includes bokeh) (dask#4924) * Add a diagnostics extra (includes bokeh) * Bump bokeh minimum to 0.13.0 * Add to `test_imports` commit 773f775 Author: btw08 <[email protected]> Date: Fri Jun 14 14:34:34 2019 +0000 4809 fix extra cr (dask#4935) * added test that fails to demonstrate the issue in 4809 * modfied open_files/OpenFile to accept a newline parameter, similar to io.TextIOWrapper or the builtin open on py3. Pass newline='' to open_files when preparing to write csv files. Fixed dask#4809 * modified newline documentation to follow convention * added blank line to make test_csv.py flake8-compliant commit 419d27e Author: Peter Andreas Entschev <[email protected]> Date: Fri Jun 14 15:18:42 2019 +0200 Minor meta construction cleanup in concatenate (dask#4937) commit 1f821f4 Author: Bruce Merry <[email protected]> Date: Fri Jun 14 12:49:59 2019 +0200 Cache chunk boundaries for integer slicing (dask#4923) This is an alternative to dask#4909, to implement dask#4867. Instead of caching in the class as in dask#4909, use functools.lru_cache. This unfortunately has a fixed cache size rather than a cache entry stored with each array, but simplifies the code as it is not necessary to pass the cached value from the Array class down through the call tree to the point of use. A quick benchmark shows that the result for indexing a single value from a large array is similar to that from dask#4909, i.e., around 10x faster for constructing the graph. This only applies the cache in `_slice_1d`, so should be considered a proof-of-concept. * Move cached_cumsum to dask/array/slicing.py It can't go in dask/utils.py because the top level is not supposed to depend on numpy. * cached_cumsum: index cache by both id and hash The underlying _cumsum is first called with _HashIdWrapper, which will hit (very cheaply) if we've seen this tuple object before. If not, it will call itself again without the wrapper, which will hit (but at a higher cost for tuple.__hash__) if we've seen the same value before but in a different tuple object. * Apply cached_cumsum in more places commit 66531ba Author: jakirkham <[email protected]> Date: Thu Jun 13 12:13:55 2019 -0400 Drop size 0 arrays in concatenate (dask#4167) * Test `da.concatenate` with size 0 array Make sure that `da.concatenate` does not include empty arrays in the result as they don't contribute any data. * Drop size 0 arrays from `da.concatenate` If any of the arrays passed to `da.concatenate` has a size of 0, then it won't contribute anything to the array created by concatenation. As such make sure to drop any size 0 arrays from the sequence of arrays to concatenate before proceeding. * Handle dtype and all 0 size case * Cast inputs with asarray * Coerce all arrays to concatenate to the same type * Drop obsoleted type handling code * Comment on why arrays are being dropped * Use `np.promote_types` for parity w/old behavior * Handle endianness during type promotion * Construct empty array of right type Avoids the need to cast later and the addition of another node to the graph. * Promote types in `concatenate` using `_meta` There was some left over type promotion code for the arrays to concatenate using their `dtype`s. However this should now use the `_meta` information instead since that is available. * Ensure `concatenate` is working on Dask Arrays * Raise `ValueError` if `concatenate` gets no arrays NumPy will raise if no arrays are provided to concatenate as it is unclear what to do. This adds a similar exception for Dask Arrays. Also this short circuits handling unusual cases later. Plus raises a clearer exception than one might see if this weren't raised. * Test `concatenate` raises when no arrays are given * Determine the concatenated array's shape Needed to handle the case where all arrays have trivial shapes. * Handle special sequence cases together * Update dask/array/core.py Co-Authored-By: James Bourbeau <[email protected]> * Drop outdated comment * Assume valid `_meta` in `concatenate` Simplifies the `_meta` handling logic in `concatenate` to assume that `_meta` is valid. As all arguments have been coerced to Dask Arrays, this is a reasonable assumption to make. commit 46aef58 Author: James Bourbeau <[email protected]> Date: Thu Jun 13 11:04:47 2019 -0500 Overload HLG values method (dask#4918) * Overload HLG values method * Return lists for keys, values, and items * Add tests for keys and items commit f9cd802 Author: mcsoini <[email protected]> Date: Thu Jun 13 18:03:55 2019 +0200 Merge dtype warning (dask#4917) * add test covering the merge column dtype mismatch warning * for various merge types: checks that the resulting dataframe has either no nans or that a UserWarning has been thrown * Add warning for mismatches between column data types * fixes issue dask#4574 * Warning is thrown if the on-columns of left and right have different dtypes * flake8 fixes * fixes * use asciitable for warning string commit c400691 Author: Hugo <[email protected]> Date: Thu Jun 13 17:38:37 2019 +0300 Docs: Drop support for Python 2.7 (dask#4932) commit 985cdf2 Author: Benjamin Zaitlen <[email protected]> Date: Thu Jun 13 10:38:15 2019 -0400 Groupby Covariance/Correlation (dask#4889) commit 6e8c1b7 Author: Jim Crist <[email protected]> Date: Wed Jun 12 15:55:11 2019 -0500 Drop Python 2.7 (dask#4919) * Drop Python 2.7 Drops Python 2.7 from our `setup.py`, and from our test matrix. We don't drop any of the compatability fixes (yet), but won't be adding new ones. * fixup commit 7a9cfaf Author: Ian Bolliger <[email protected]> Date: Wed Jun 12 11:44:26 2019 -0700 keep index name with to_datetime (dask#4905) * keep index name with to_datetime * allow users to pass meta * Update dask/dataframe/core.py put meta as explicit kwarg Co-Authored-By: Matthew Rocklin <[email protected]> * Update dask/dataframe/core.py remove meta kwargs.pop Co-Authored-By: Matthew Rocklin <[email protected]> * remove test for index * allow index commit abc86d3 Author: jakirkham <[email protected]> Date: Wed Jun 12 14:20:59 2019 -0400 Raise ValueError if concatenate is given no arrays (dask#4927) * Raise `ValueError` if `concatenate` gets no arrays NumPy will raise if no arrays are provided to concatenate as it is unclear what to do. This adds a similar exception for Dask Arrays. Also this short circuits handling unusual cases later. Plus raises a clearer exception than one might see if this weren't raised. * Test `concatenate` raises when no arrays are given commit ce2f866 Author: jakirkham <[email protected]> Date: Wed Jun 12 14:09:35 2019 -0400 Promote types in `concatenate` using `_meta` (dask#4925) * Promote types in `concatenate` using `_meta` There was some left over type promotion code for the arrays to concatenate using their `dtype`s. However this should now use the `_meta` information instead since that is available. * Ensure `concatenate` is working on Dask Arrays Merge remote-tracking branch 'upstream/master' into dataframe-warnings

jakirkham · 2019-06-21T01:59:41Z

dask/array/core.py

-    if n == 1:
+    n = len(seq)
+    if n == 0:
+        return from_array(np.empty(shape=shape, dtype=meta.dtype))


This isn't very meta-friendly. Fixing in PR ( #4979 ).

jakirkham added 2 commits November 1, 2018 20:32

Test da.concatenate with size 0 array

15cd8da

Make sure that `da.concatenate` does not include empty arrays in the result as they don't contribute any data.

Drop size 0 arrays from da.concatenate

da76f90

If any of the arrays passed to `da.concatenate` has a size of 0, then it won't contribute anything to the array created by concatenation. As such make sure to drop any size 0 arrays from the sequence of arrays to concatenate before proceeding.

jakirkham mentioned this pull request Nov 2, 2018

Rewrite Dask Array's pad to add only new chunks #4152

Merged

2 tasks

hmaarrfk reviewed Nov 2, 2018

View reviewed changes

dask/array/core.py Outdated Show resolved Hide resolved

jrbourbeau added 3 commits May 21, 2019 14:32

Merge remote-tracking branch 'upstream/master' into concat_drop_0_siz…

5f8d949

…e_arrs

Handle dtype and all 0 size case

6158fe4

Cast inputs with asarray

25383b4

TomAugspurger added the array label May 22, 2019

jrbourbeau changed the title ~~WIP: Drop size 0 arrays in concatenate~~ Drop size 0 arrays in concatenate May 23, 2019

jakirkham added 6 commits May 23, 2019 07:03

Coerce all arrays to concatenate to the same type

7ea25e3

Drop obsoleted type handling code

b50ba60

Comment on why arrays are being dropped

b8169c6

Use np.promote_types for parity w/old behavior

b236149

Handle endianness during type promotion

a9a56af

Construct empty array of right type

3e1653e

Avoids the need to cast later and the addition of another node to the graph.

jakirkham commented May 23, 2019

View reviewed changes

dask/array/core.py Outdated Show resolved Hide resolved

jakirkham self-assigned this Jun 4, 2019

jakirkham added 2 commits June 12, 2019 11:14

Promote types in concatenate using _meta

406e49a

There was some left over type promotion code for the arrays to concatenate using their `dtype`s. However this should now use the `_meta` information instead since that is available.

Merge dask/master into jakirkham/concat_drop_0_size_arrs

79690e2

jakirkham force-pushed the concat_drop_0_size_arrs branch from 476f203 to 79690e2 Compare June 12, 2019 15:50

jakirkham mentioned this pull request Jun 12, 2019

Promote types in concatenate using _meta #4925

Merged

2 tasks

jakirkham added 3 commits June 12, 2019 12:01

Ensure concatenate is working on Dask Arrays

32223d6

Test concatenate raises when no arrays are given

559392e

jakirkham mentioned this pull request Jun 12, 2019

Raise ValueError if concatenate is given no arrays #4927

Merged

2 tasks

jakirkham added 5 commits June 12, 2019 12:25

Merge jakirkham/concat_meta_touchup into jakirkham/concat_drop_0_size…

4c14aa2

…_arrs

Merge jakirkham/concat_ensure_1_arr into jakirkham/concat_drop_0_size…

a4e915b

…_arrs

Determine the concatenated array's shape

c55e7cf

Needed to handle the case where all arrays have trivial shapes.

Merge 'dask/master' into 'jakirkham/concat_drop_0_size_arrs'

c466fb1

Handle special sequence cases together

842a5ff

jakirkham mentioned this pull request Jun 12, 2019

Ignoring size 0 arrays in stack #4928

Closed

jrbourbeau reviewed Jun 12, 2019

View reviewed changes

jakirkham and others added 2 commits June 12, 2019 16:31

Update dask/array/core.py

aa9004f

Co-Authored-By: James Bourbeau <[email protected]>

Drop outdated comment

97e9b2b

Merge dask/master into jakirkham/concat_drop_0_size_arrs

e4ec5fd

Assume valid _meta in concatenate

4738c06

Simplifies the `_meta` handling logic in `concatenate` to assume that `_meta` is valid. As all arguments have been coerced to Dask Arrays, this is a reasonable assumption to make.

jrbourbeau approved these changes Jun 13, 2019

View reviewed changes

jrbourbeau merged commit 66531ba into dask:master Jun 13, 2019

jakirkham deleted the concat_drop_0_size_arrs branch June 13, 2019 16:22

jakirkham commented Jun 21, 2019

View reviewed changes

jakirkham mentioned this pull request Jun 24, 2019

da.pad().flatten().compute() crashes when zeros are involved in the padding width #4982

Closed

jakirkham mentioned this pull request Oct 14, 2021

min/max fail on empty chunks #2794

Closed

Uh oh!

Drop size 0 arrays in concatenate #4167

Drop size 0 arrays in concatenate #4167

Uh oh!

Conversation

jakirkham commented Nov 2, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Uh oh!

shoyer commented Nov 2, 2018

Uh oh!

jakirkham commented Nov 2, 2018

Uh oh!

hmaarrfk commented Nov 2, 2018

Uh oh!

jakirkham commented Nov 3, 2018

Uh oh!

jakirkham commented Nov 5, 2018

Uh oh!

jrbourbeau commented May 20, 2019

Uh oh!

jakirkham commented May 20, 2019

Uh oh!

mrocklin commented May 20, 2019

Uh oh!

jakirkham commented May 20, 2019

Uh oh!

jrbourbeau commented May 22, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

jakirkham left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

jakirkham commented Jun 12, 2019

Uh oh!

jrbourbeau left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

jakirkham commented Jun 12, 2019

Uh oh!

jrbourbeau commented Jun 12, 2019

Uh oh!

jakirkham commented Jun 13, 2019

Uh oh!

jakirkham commented Jun 13, 2019

Uh oh!

jrbourbeau left a comment

Choose a reason for hiding this comment

Uh oh!

jakirkham commented Jun 13, 2019

Uh oh!

jakirkham Jun 21, 2019

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

7 participants

jakirkham commented Nov 2, 2018 •

edited

Loading

jrbourbeau commented May 22, 2019 •

edited

Loading