Flow Graph - Suggestion

[ronag89]

I've noticed what seems to me a suboptimal semantics of the flow graph api.

In particular when a node switches set (push/pull) the switch is possibly unnecessarily complicated.

Given two nodes S (s) (sender) and R (r) (receiver).

All nodes start out in the push set.

S tries to push to R and fails. S then removes R from it's successors and adds itself to Rs predecessors. 

// s

args : {v}

if (!r.try_put(v))
{
     succesors.remove(r);
     r.register_predecessor(*this);
}

// r

args : {s}

predecessors.add(s);

The inherent problem here is that between "try_put" failing and "register_predecessor"  things can happen. So we need to add some stuff.

// s

args : {v}

if (!r.try_put(v))
{
     if(r.register_predecessor(*this))
         succesors.remove(r);
     else
         break;
}

// r

args : {s}

if (can_process_new_items && s.try_get(v))
{
      process(v);
      return false;
}

predecessors.add(s);

return true;

It think this extra complexity can be avoided by changing the API by allowing nodes to take ownership of edges directly in the try_put/try_get methods.

e.g.

 

// s

args : {v}

if (!r.try_put(v, this))
     succesors.remove(r);

// r

args : {s}

if (!can_process_item)
{
    predecessors.add(s);
    return false;
}

Soo, the sender/receiver interface would be change to something like:

 

template<typename T>
struct receiver
{
      using input_type = T;
      using predecessor_type = sender<input_type>;

      bool try_put(input_value& v, predecessor* s = nullptr);
}

template<typename T>
struct sender
{
      using output_type = T;
      using successor_type = receiver<output_type>;

      bool try_get(output_type& v, successor_type r = nullptr);

      void register_sucessor(sucessor_type& r); // only used by make_edge
}

Any thoughts? Is this a good idea? Am I missing something?

[ronag89]

Here is a more complete example of how it could look. Probably buggy and a lot slower than the real tbb implementation but it does show the basic idea.

https://github.com/ronag/tasket/blob/master/tasket.h