Improve ordering for specific workloads#6779
Conversation
The current ordering algorithm struggles with workloads where there's
a single, common root node that's downstream of a tasks with some shared
dependencies.
s
/ / \ \
/ / \ \
s00 s10 s01 s11
| | | |
b00 b10 b01 b11
/ \ / \ / \ / \
a0 a1 a2 a3 a4 a5
Previously, we started at a0, finished s00, and then jumped down to a3
after deciding that we should work on s01 based on a tiebreaker. We'd
instead like to work on s10, thakns to the shared dependency a1.
The ordering algorithm does just fine in the absence of the common root
node `s`. So this PR proposes to just ignore it, at least in the part of
the ordering where we made the wrong choice previously.
|
Running the original example from #6745 (comment), the memory usage stayed below ~2.5GB the whole time. Finished in 3.5 minutes. And here's the ordering:
|
dask/order.py
Outdated
| item = inner_stack_pop() | ||
| if item in result: | ||
| continue | ||
| if skip_root_node and item in root_nodes: |
There was a problem hiding this comment.
I'm curious, how will this item get processed if we always skip it? Actually, I think I know the answer: it will get processed when we handle finish_now down below.
There was a problem hiding this comment.
I guess the answer is sometimes. As you may see I had to cancel the CI since we got caught in some infinite loops. Hopefully I've caught all those through trial and error.
There was a problem hiding this comment.
Interesting. In that case, this check could probably go a couple lines lower inside the if num_needed[item]: branch.
Co-authored-by: Erik Welch <erik.n.welch@gmail.com>
|
Seems like a pragmatic approach. It would be nice to be able to generalize it somewhat to still work if there are multiple subgraphs that aren't connected. I'll mull this over. |
|
Thanks, no rush at all on this. I am a bit hesitant to add this kind of ad-hoc, special case to |
|
Just noting that some pangeo users are running into this issue as well (as in the sgkit example, they're using We might want to change |
|
And FWIW, I ran the order benchmarks in dask-benchmarks on this. They showed |
|
Just confirming that when there are multiple output nodes, we do revert to the bad ordering: Detailsimport dask
f = lambda *args: None
kwargs = {
"node_attr": {"penwidth": "4"},
"cmap": "autumn",
"color": "order",
}
dsk = {}
for i in range(2):
dsk[(f"a-{i}", 0)] = (0,)
dsk[(f"a-{i}", 1)] = (1,)
dsk[(f"a-{i}", 2)] = (2,)
dsk[(f"b-{i}", 0)] = (f, (f"a-{i}", 0), (f"a-{i}", 1))
dsk[(f"b-{i}", 1)] = (f, (f"a-{i}", 1), (f"a-{i}", 2))
dsk[(f"store-{i}", 0, 0)] = (f"b-{i}", 0)
dsk[(f"store-{i}", 1, 0)] = (f"b-{i}", 1)
# right half
dsk[(f"a-{i}", 3)] = (3,)
dsk[(f"a-{i}", 4)] = (4,)
dsk[(f"a-{i}", 5)] = (5,)
dsk[(f"b-{i}", 2)] = (f, (f"a-{i}", 3), (f"a-{i}", 4))
dsk[(f"b-{i}", 3)] = (f, (f"a-{i}", 4), (f"a-{i}", 5))
dsk[(f"store-{i}", 0, 1)] = (f"b-{i}", 2)
dsk[(f"store-{i}", 1, 1)] = (f"b-{i}", 3)
dsk[f"store-{i}"] = (
f,
(f"store-{i}", 0, 0),
(f"store-{i}", 1, 0),
(f"store-{i}", 0, 1),
(f"store-{i}", 1, 1),
)
dask.visualize(dsk, filename="multi-out", **kwargs)
This is identical to the ordering on master. We'd like for the I'll look a bit more at this today, time permitting, but I'm a bit pessimistic that we'll be able to solve it. Simply expanding the check to skip all the root nodes causes other ordering problems. |
|
I've looked at this again, and agree that doing better than what's currently in this PR would be difficult. I don't see any "easy wins" to be gained from minor tweaks. I'm okay if we merge this PR as is. |
|
Let us not let better be the enemy of the good. Merging. Thanks @TomAugspurger, @eriknw, and others |
The current ordering algorithm struggles with workloads where there's
a single, common root node that's downstream of a tasks with some shared
dependencies.
Previously, we started at a0, finished s00, and then jumped down to a3
after deciding that we should work on s01 based on a tiebreaker. We'd
instead like to work on s10, thanks to the shared dependency a1.
The ordering algorithm does just fine in the absence of the common root
node
s. So this PR proposes to just ignore it, at least in the part ofthe ordering where we made the wrong choice previously.
cc @eriknw and @tomwhite.
Closes #6745