FazBrowse GitHub Viewer | Trending |
URL:
| Home
Tools: [Download Repo ZIP]   [Original HTTPS Page]

Why does Executor restore the join counter with fetch_add instead of store? · Issue #810 · taskflow/taskflow · GitHub

Why does Executor restore the join counter with fetch_add instead of store? #810

Description

Hi, I have a question about the following code in `Executor::_invoke`:

```cpp
// Reset the join counter with strong dependencies to support cycles.
// + We must do this before scheduling the successors to avoid race
//   condition on _predecessors.
// + We must use fetch_add instead of direct assigning
//   because the user-level call on "invoke" may explicitly schedule
//   this task again (e.g., pipeline) which can access the join_counter.
node->_join_counter.fetch_add(
  node->_nstate & NSTATE::STRONG_DEPENDENCIES_MASK,
  std::memory_order_relaxed
);

I understand why the join counter needs to be restored before scheduling successors.

For example, in a cycle:

A -> B -> A

after A becomes ready, its join counter is 0. Before B is allowed to run and potentially decrement A again, A needs to restore its strong dependency count for the next iteration.

However, for this purpose alone, it seems that:

node->_join_counter.store(
  node->_nstate & NSTATE::STRONG_DEPENDENCIES_MASK,
  std::memory_order_relaxed
);

would also work, assuming the current invocation exclusively owns the node's join-counter state.

So I am trying to understand the exact concurrency scenario that requires fetch_add.

My current understanding is that the important case may be something like this:

A ----\
       -> D
B ----/

where D has two strong dependencies:

D.join_counter = 2

Then another runtime task explicitly schedules D:

rt.schedule(D);

and Runtime::schedule resets the target counter to zero before scheduling it:

node->_join_counter.store(0, std::memory_order_relaxed);

Suppose D is executing while one of its normal strong predecessors finishes:

Runtime::schedule(D):
2 -> 0

A finishes:
0 -> size_t(-1)

Then when the explicitly scheduled invocation of D completes:

D.join_counter.fetch_add(2);

the counter becomes logically:

-1 + 2 = 1

which preserves the fact that A has already finished.

If this were instead:

D.join_counter.store(2);

then the decrement caused by A would be overwritten, and the counter would incorrectly become 2.

Is this the main reason fetch_add is required here?

I also have a related question about activation semantics.

Continuing the example above, after the explicitly scheduled invocation of D finishes, the counter becomes 1. When B later finishes:

1 -> 0

the normal dependency path may schedule D again.

So D may execute once because of Runtime::schedule(D) and later execute again because its normal strong dependencies become satisfied.

Is this intentional semantics of Runtime::schedule?

In other words, is the intended model:

  1. Runtime::schedule(task) creates an additional execution of an active task, independently of its normal dependency-triggered execution;
  2. fetch_add(strong_dependencies) preserves concurrent dependency-counter updates that occurred while that explicit execution was running;
  3. fetch_add is not intended to prevent duplicate/overlapping activations of the same node.

The comment mentions pipeline as an example:

// user-level call on "invoke" may explicitly schedule
// this task again (e.g., pipeline)

I noticed that Pipeline also maintains its own per-cell counters:

_lines[line][pipe].join_counter

while its line tasks are scheduled through NonpreemptiveRuntime::schedule.

So I am also wondering whether pipeline is only an example showing that invoke() may modify task scheduling state, rather than a direct example where a non-zero Node::_join_counter specifically requires this fetch_add.

Could you clarify the intended invariant of Node::_join_counter around:

normal dependency scheduling
Runtime::schedule
task invocation
join-counter restoration

and the exact race that fetch_add is designed to handle?

Thanks!

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions


      Back | FazBrowse Home | New Git URL