Repository: dask/dask
Pull request #6154 (2020-04-30 12:49:22)

Estimate dict sizes properly
This would be the implementation alternative for #6149 which is supposed to address the issue that the size of intermediate shuffle tasks are not measured since they are usually dicts with > 10 keys.

This issue has been frequently discussed and there were some concerns about performance, most notably https://github.com/dask/distributed/pull/1626

For the sampling I also tried to use `(cy)toolz.itertoolz.random_sample` but the builtin random performed the same so I chose to go this way.

Regarding mirco benchmarks of the function this code is useful

```python
import sys
from distutils.version import LooseVersion
from dask.sizeof import sizeof

from cytoolz.itertoolz import map
getsizeof = sys.getsizeof

import random
def sizeof_python_collection(seq):
    
    num_items = len(seq)
    samples = 10
    if num_items > samples:
        return getsizeof(seq) + num_items / samples * sum(
            map(sizeof, random.sample(seq, samples))
        )
    else:
        return getsizeof(seq) + sum(map(sizeof, seq))


def sizeof_python_dict(d):
    return (
        getsizeof(d)
        + sizeof_python_collection(list(d.keys()))
        + sizeof_python_collection(list(d.values()))
        - 2 * sizeof_python_collection(list())
    )

def sizeof_python_dict_orig(d):
    if len(d) > 10:
        return getsizeof(d) + 1000 * len(d)
    else:
        return getsizeof(d) + sum(map(sizeof, d.keys())) + sum(map(sizeof, d.values()))
```

Benchmarks from https://github.com/dask/dask-benchmarks will follow

xref https://github.com/dask/dask/issues/2456

fjetter: In terms of microbenchmarks of the new code, see the screenshot below.

What we can observe is that the new function is consistently slower (even for the sample_dict_very_small) case which is something I haven't understood, yet.

![image](https://user-images.githubusercontent.com/8629629/80712683-a00ac300-8af2-11ea-9bde-b5f3dde47a1d.png)

The  [dask-benchmarks](https://github.com/dask/dask-benchmarks) for distributed stay the same within margin of error so I'll refrain from posting the results here. Not sure if the benchmarks include everything relevant

mrocklin: This looks good to me.  I suggest two small changes:

1.  unless using cytoolz.map makes this significantly faster than builtins.map let's just use builtins for simplicity
2.  Maybe add a test with a dictionary with 100 numpy arrays?

Thank you for doing this @fjetter 
fjetter: Regarding benchmarks the numpy arrays behave similar to the lists but a bit faster
![image](https://user-images.githubusercontent.com/8629629/80723773-5675a480-8b01-11ea-9e31-b2a4c91a28d9.png)

Did you mean an actual unit test? Numpy arrays take another code path via the dispatch and should generally not be affected by this change. note that the benchmark code above is slightly different than the actual code in the PR. The PR code uses the proper dispatch, the benchmark code above doesn't to allow running both pieces in the same interpreter
mrocklin: > Did you mean an actual unit test? Numpy arrays take another code path via the dispatch and should generally not be affected by this change

Even if the dictionary is larger than ten elements?

Patch:
diff --git a/dask/array/routines.py b/dask/array/routines.py
index 3e54428b5..1a1f75d67 100644
--- a/dask/array/routines.py
+++ b/dask/array/routines.py
@@ -1266,20 +1266,19 @@ def _unravel_index_kernel(indices, func_kwargs):
 
 
 @derived_from(np)
-def unravel_index(indices, dims, order="C"):
-    # TODO: deprecate dims as well?
-    if dims and indices.size:
+def unravel_index(indices, shape, order="C"):
+    if shape and indices.size:
         unraveled_indices = tuple(
             indices.map_blocks(
                 _unravel_index_kernel,
                 dtype=np.intp,
-                chunks=(((len(dims),),) + indices.chunks),
+                chunks=(((len(shape),),) + indices.chunks),
                 new_axis=0,
-                func_kwargs={_unravel_index_keyword: dims, "order": order},
+                func_kwargs={_unravel_index_keyword: shape, "order": order},
             )
         )
     else:
-        unraveled_indices = tuple(empty((0,), dtype=np.intp, chunks=1) for i in dims)
+        unraveled_indices = tuple(empty((0,), dtype=np.intp, chunks=1) for i in shape)
 
     return unraveled_indices
 
diff --git a/dask/sizeof.py b/dask/sizeof.py
index 1cf5168d6..146fb0030 100644
--- a/dask/sizeof.py
+++ b/dask/sizeof.py
@@ -1,3 +1,4 @@
+import random
 import sys
 from distutils.version import LooseVersion
 
@@ -25,15 +26,24 @@ def sizeof_default(o):
 @sizeof.register(set)
 @sizeof.register(frozenset)
 def sizeof_python_collection(seq):
-    return getsizeof(seq) + sum(map(sizeof, seq))
+    num_items = len(seq)
+    samples = 10
+    if num_items > samples:
+        return getsizeof(seq) + num_items / samples * sum(
+            map(sizeof, random.sample(seq, samples))
+        )
+    else:
+        return getsizeof(seq) + sum(map(sizeof, seq))
 
 
 @sizeof.register(dict)
 def sizeof_python_dict(d):
-    if len(d) > 10:
-        return getsizeof(d) + 1000 * len(d)
-    else:
-        return getsizeof(d) + sum(map(sizeof, d.keys())) + sum(map(sizeof, d.values()))
+    return (
+        getsizeof(d)
+        + sizeof(list(d.keys()))
+        + sizeof(list(d.values()))
+        - 2 * sizeof(list())
+    )
 
 
 @sizeof.register_lazy("cupy")
diff --git a/docs/source/index.rst b/docs/source/index.rst
index a8db5d8c0..d5d2d3106 100644
--- a/docs/source/index.rst
+++ b/docs/source/index.rst
@@ -186,6 +186,7 @@ messy situations in everyday problems.
    spark.rst
    caching.rst
    graphs.rst
+   phases-of-computation.rst
    remote-data-services.rst
    gpu.rst
    cite.rst


Test patch:
diff --git a/dask/tests/test_sizeof.py b/dask/tests/test_sizeof.py
index 73640b2fc..a911d6396 100644
--- a/dask/tests/test_sizeof.py
+++ b/dask/tests/test_sizeof.py
@@ -129,3 +129,5 @@ def test_dict():
     assert sizeof({"x": x}) > x.nbytes
     assert sizeof({"x": [x]}) > x.nbytes
     assert sizeof({"x": [{"y": x}]}) > x.nbytes
+
+    assert sizeof({i: x for i in range(100)}) > x.nbytes * 100