RecursionError after many consecutive additions

[tierriminator]

Running the following code results in a RecursionError.

import dask.array as da
from dask.distributed import Client
import numpy as np

if __name__ == "__main__":
    client = Client()

    x = da.zeros(1)
    out = 0
    n = 1000
    for _ in range(n):
        out += x
    out.compute()

This is the output:

[...]
  File "[...]/python3.10/site-packages/distributed/utils_comm.py", line 225, in unpack_remotedata
    return tuple(unpack_remotedata(item, byte_keys, myset) for item in o)
  File "[...]/python3.10/site-packages/distributed/utils_comm.py", line 225, in <genexpr>
    return tuple(unpack_remotedata(item, byte_keys, myset) for item in o)
  File "[...]/python3.10/site-packages/distributed/utils_comm.py", line 225, in unpack_remotedata
    return tuple(unpack_remotedata(item, byte_keys, myset) for item in o)
  File "[...]/python3.10/site-packages/distributed/utils_comm.py", line 225, in <genexpr>
    return tuple(unpack_remotedata(item, byte_keys, myset) for item in o)
RecursionError: maximum recursion depth exceeded

I use dask from conda with Python 3.10.4 and the following dependency versions:

# Name                    Version                   Build  Channel
dask                      2022.7.0        py310h06a4308_0  
dask-core                 2022.7.0        py310h06a4308_0  
dask-jobqueue             0.8.1              pyhd8ed1ab_0    conda-forge
distributed               2022.7.0        py310h06a4308_0
numpy                     1.23.1          py310h1794996_0 

[wence-]

I suppose that this is a minimised reproducer from an actual problem you encountered. What is going on here is that the loop that increments out += x does not do so eagerly, but instead builds a representation of the computation as a graph. In this particular case, the depth of the graph is linear in n (since for _ in range(n): out += x has a loop-carried dependency).

When the call to out.compute() is made, this graph is unwound and the final result is fetched. The implementation here traverses the graph recursively (here in unpack_remotedata) and we run into a python-level restriction that recursion cannot have more than sys.getrecursionlimit() stack frames (In my interpreter, this returns 1000).

One way to try and work around this is to up the recursion limit somewhat (with sys.setrecursionlimit) though that is more of a band-aid than a real fix.

To avoid this pattern of linear-depth graphs for reduction-like operations you can build the operation in a tree (which has only logarithmic depth):

from __future__ import annotations

import itertools
import operator
from typing import Callable, TypeVar, Iterable

import dask.array as da
from dask.distributed import Client

T = TypeVar("T")


def tree_reduce(
    binop: Callable[[T, T], T], values: Iterable[T], initial: T | None = None
) -> T:
    if initial is not None:
        values = list(itertools.chain([initial], values))
    else:
        values = list(values)
    n = len(values)
    if n == 0:
        raise TypeError("reduce of empty iterable with no initial value")
    elif n == 1:
        return values[0]
    elif n == 2:
        return binop(*values)
    else:
        mid = n // 2
        left = values[:mid]
        right = values[mid:]
        return binop(tree_reduce(binop, left), tree_reduce(binop, right))


if __name__ == "__main__":
    client = Client()
    x = da.full((1,), 1, dtype="float64")
    n = 1000
    out = tree_reduce(operator.add, itertools.repeat(x, n))
    print(out.compute())

[tierriminator]

Thanks for your answer! I did have the suspicion that some recursive graph traversal was happening and that this is the source of the problem. I guess there are multiple ways to work around it. For simple reductions, building a tree is definitely an option, if the operator is associative (thanks for the nice function). Another workaround might be to reduce the graph size with repeated persist() or compute() calls.

Still I have the impression that dask should be able to handle graphs independent of their structure. So I guess I'm challenging the recursive graph traversal and would propose to implement it as a loop.