Feasability of fork topology without `split`

[romintomasetti]

We'd like to represent the following topology (each node represents some work):

graph TD
    A --> B
    A --> C
    B --> D
    C --> D
    C --> E

    D --> END
    E --> END

Loading

It seems that for such a case, it is possible to use split:

auto A = just() | then(...) | split();

auto B = A | then(...);
auto C = A | then(...) | split();

auto D = when_all(B, C) | then(...);
auto E = C | then(...);

sync_wait(when_all(D, E));

However, P3682 (written by @RobertLeahy) proposed to remove std::execution::split and as far as we understand it, it was approved.

Therefore, how would we represent the above topology, without introducing other dependencies ?

Joint question with @maartenarnst.

[Cra3z]

Maybe

simple_counting_scope scope;
sync_wait(A | let_value([&]{
  return when_all(
    associate(B, scope.get_token()), 
    C | let_value([&]{
      return when_all(
        scope.join() | let_value([&]{ 
          return D;
        }),
        E
      );
    })
  );
}));

[romintomasetti]

Hi @Cra3z! Thanks for the suggestion.

However, I believe this approach will actually deadlock. I'm not deeply familiar with P3149R11 yet, but according to the specification (emphasis mine):

the association ends when the associate-sender is destroyed or, if it is connected, when the resulting operation state is destroyed

My understanding is that the operation state of the when_all branch containing work B will not be destroyed at least until control exits the parent when_all. Therefore, the branch performing scope.join() will wait indefinitely.

Here is my code demonstrating the issue. It compiles but deadlocks: while B prints its message, D never executes.

template <char ID>
struct Work {
    void operator()() const {
        std::printf("Hello from the work of %c.\n", ID);
    }
};

TEST(SimpleCountingScope, diamond_with_tail) {
    ::exec::static_thread_pool pool{5};

    ::stdexec::simple_counting_scope scope;

    auto schd = pool.get_scheduler();

    //! Run node A first.
    auto sndr =
        ::stdexec::schedule(schd) | ::stdexec::then(Work<'A'>{}) | ::stdexec::let_value([&] {
            //! Use @c when_all to allow nodes B and C to run concurrently.
            return ::stdexec::when_all(
                //! Node B.
                ::stdexec::associate(::stdexec::schedule(schd) | ::stdexec::then(Work<'B'>{}), scope.get_token()),
                //! Node C.
                ::stdexec::schedule(schd) | ::stdexec::then(Work<'C'>{}) | ::stdexec::let_value([&] {
                    //! Use @c when_all to allow nodes D and E to run concurrently.
                    return ::stdexec::when_all(
                        //! Join the scope to ensure node D runs only once node B is finished.
                        scope.join() | ::stdexec::continues_on(schd) | ::stdexec::then(Work<'D'>{}),
                        //! Node E.
                        ::stdexec::schedule(schd) | ::stdexec::then(Work<'E'>{}));
                }));
        });

    ::stdexec::sync_wait(std::move(sndr));
}

Beyond the deadlock issue, I have additional concerns about this approach:

1. Readability and reasoning: Relying on scope.join(), nested let_value, and when_all to express graph topology is overly complex and difficult to reason about. The control flow dependencies are obscured by the scope.join and nesting structure.
2. Scalability: I don't believe this pattern will scale to more complex DAGs. As the graph grows, the nesting depth and interdependencies become increasingly difficult to manage and verify for correctness.
3. Scheduler optimization opportunities: Consider a scheduler implementation e.g. performs DAG analysis for fusion opportunities. The use of let_value is problematic here because it defers evaluation of its lambda until completion time, preventing the scheduler from seeing the full dependency graph upfront. This fundamentally limits what optimizations are possible at graph construction time.

For these reasons, I think we need a more declarative approach to expressing DAG topologies that separates graph structure from execution semantics.

[Cra3z]

@romintomasetti Indeed. We should perhaps use spawn or spawn_future instead of associate.

simple_counting_scope scope;
sync_wait(A | let_value([&]{
  spawn(B, scope.get_token());
  return C | let_value([&]{
    return when_all(
      scope.join() | let_value([&]{ 
        return D;
      }),
      E
    );
  });
}));

[romintomasetti]

@Cra3z Thanks for the clarification!

While spawn probably does avoid the deadlock (I haven't tested it), I remain concerned that this approach fundamentally limits what a scheduler implementation can achieve.

The core issue is that, as I understand it (it's an atomic counter):

scope doesn't retain type information about the senders it "manages".

Consider a scheduler that wants to optimize the work represented by scope.join() - for instance, by analyzing its predecessors. With the scope approach, the scheduler has no visibility into what work is associated with the scope (even at runtime). The spawn+scope mechanism means the full DAG topology is not available "from within the code" since it's enforced by counters.

So there seems to be two fundamentally different approaches to expressing such DAGs:

1. "Eager" execution with dynamic synchronization (the approach you propose):
   • Work is launched immediately via spawn.
   • Synchronization happens dynamically through scope counting.
   • The topology emerges at runtime through side effects.
   • Schedulers see only local operation state, not the global structure.
2. Declarative and structured topology with deferred execution (what I'm pursuing):
   • The entire DAG structure is declared upfront.
   • Explicit dependency edges define the topology.
   • Schedulers can analyze the complete graph before execution.
   • Optimization opportunities are broaden.

For my use case—building optimized execution graphs for GPU computing where ahead-of-time analysis is crucial—I need the scheduler to see the complete DAG structure (or as much as possible). The scope.join() approach, while elegant for dynamic parallelism, obscures this structure behind runtime counting mechanisms.

I suspect both patterns have their place depending on whether you're optimizing for expressiveness with dynamic parallelism or for static analysis with graph-level optimizations. For my needs, I'm looking for primitives that preserve the topology information throughout the sender chain.

Does this distinction align with how you see the design space?

[RobertLeahy]

2. Declarative and structured topology with deferred execution (what I'm pursuing):

   • The entire DAG structure is declared upfront.
   • Explicit dependency edges define the topology.
   • Schedulers can analyze the complete graph before execution.
   • Optimization opportunities are broaden.

If we narrow our analysis just to A, B, and C in your example, how are you modeling this is a way that gives you what you want?

I ask because the way I'd implement A, B, and C would be:

A | ::stdexec::let_value([&](auto& a) { return ::stdexec::when_all(B(a), C(a)); });

Which works but in the GPU space my understanding is that this is suboptimal because the graph is formed lazily: You need to invoke the invocable passed to let_value in order to understand the graph, and that needs to occur after A, which inhibits throughput (since the GPU running everything stalls waiting for the next piece of the pipeline to be chosen).

In a universe with split you could write:

auto a = ::stdexec::split(A);
auto b = a | B;
auto c = std::move(a) | C;

But that comes with all the disadvantages of split (including but not limited to the fact that it allocates) as detailed in my paper which removed it.

Let's imagine we have the following functionality:

template<typename T>
struct waitable_value {
  // Produces a sender which runs the asynchronous operation
  // represented by the given sender and then:
  //
  // - Fails or stops if that operation fails or stops (and
  //   causes wait operations to stop, see below), otherwise
  // - Stores the produced value in *this and then sends
  //   set_value_t(T&) with that stored value
  ::stdexec::sender auto produce(::stdexec::sender auto&& snd) &;
  // Produces a sender which either completes with:
  // - set_value_t(T&) if a value is produced (see above), or
  // - set_stopped_t() if the produce operation failed or was
  //   stopped
  ::stdexec::sender auto wait() & noexcept;
};

Then with #1790 (see: P3955R0) we can write:

auto end = ::exec::lifetime(
  [&](auto&& result_of_a, auto&& result_of_c) {
    auto a = result_of_a.produce(A);
    auto b = std::move(a) | B;
    auto c = result_of_c.produce(result_of_a.wait() | C);
    auto d = ::stdexec::when_all(std::move(b), std::move(c)) | D;
    auto e = result_of_c.wait() | E;
    return ::stdexec::when_all(std::move(d), std::move(e));
  },
  ::exec::sync_object<waitable_value<result_of_a_type>>{},
  ::exec::sync_object<waitable_value<result_of_c_type>>{});

How close is that to giving you what you want/need?

[RobertLeahy]

Also note exec::fork (#1541), now renamed exec::fork_join (#1550), which was added in the aftermath of split's removal.

[romintomasetti]

@RobertLeahy Thank you for engaging with this — your perspective is genuinely helpful here.

You are right that std::execution::let_value is unsatisfactory for our use case: the lazily-invoked functor delays work submission and stalls the GPU pipeline. We already customized exec::fork_join, but it is limited to series-parallel graphs.

@maartenarnst and I have been thinking about what would be needed to express arbitrary DAGs and converged on a structured scoping approach, driven by the following goal:

Find a structured replacement for the std::execution::split use-cases where it acts purely as a control-flow fork point, with no memoization semantics.

The idea is to require the user to explicitly delimit a single-entry/single-exit region — similar in spirit to fork_join — within which fork/join edges forming the DAG are permitted and can be validated (as opposed to split that allows an arbitrary number of consumers). This clearly overlaps with what you propose.

One concern with your lifetime approach is that it seems to require the author of the lifetime scope to know all "waitable" nodes upfront. But I guess it could most of the time be addressed if lifetime scopes can be nested — each sub-DAG would then be expressed within its own nested scope, deferring the need for "global knowledge". Is that a supported use case?

To give you more concrete material to work with, here is one DAG we need to express:

graph TD
    A_1 --> B_1
    A_2 --> B_1
    A_2 --> B_2
    A_3 --> B_2
    B_1 --> C_1
    B_1 --> C_2
    B_2 --> C_2
    B_2 --> C_3
    C_1 --> D
    C_2 --> D

Loading

Would you have time to discuss further? We are on Brussels time.