parallel roads

I’ve been thinking a lot about continuations and directed graphs the last couple days and different ways to implement them.  I’ve also been looking closer at std::thread, std::future and std::async to ensure I fully understand them.  So I decided I’d make a (small) multi-part series out of this and show some simple sketches of implementations of continuation using the Parallel Pattern Library, std::future and std::async and the Agents Library.  

This is part 1 which will cover a simple implementation of ‘run_when’ and ‘wait_for_all’ using the PPL. 

First a simple dependency / continuation

Here’s an incredibly simple dependency, task 2 depends on task 1.

void ContinueableTask(int in)
{
   printf("building project: %d\n", in);
};

void SimpleContinuation()
{
   ContinueableTask(1);

   //task 2 depends on task 1
   ContinueableTask(2);
}

void SimpleContinuationTasks()
{
   //task1   task_group task1;
   task1.run([](){ContinueableTask(1);});

   //task2 depends on task 1 
   task_group task2;
   task2.run([&](){
      task1.wait();
      ContinueableTask(2);
   });   

   //wait for task 2
   task2.wait();
}

void SimpleContinuation()
{
   auto task1 = run_task([](){ContinueableTask(1);});    

   //task 2 depends on task 1
   auto task2 = run_when(task1, [](){ContinueableTask(2);});
   wait_for_all(task1, task2);
}

typedef shared_ptr<task_group> shared_task_ptr;

template<typename Func>inline shared_task_ptr run_task(Func& fn)
{
   shared_ptr<task_group> tasks = make_shared<task_group>();
   tasks->run(fn);
   return tasks;
}

template<typename Func>inline shared_task_ptr run_when(shared_task_ptr tasks, Func fn)
{
   tasks->wait();
   return run_task(fn);
}

inline void wait_for_all(shared_task_ptr t1, shared_task_ptr t2)
{
   t1->wait();
   t2->wait();
}

void MoreComplexContinuations()
{
   auto p1 = run_task([](){ContinueableTask(1);});
   auto p2 = run_task([](){ContinueableTask(2);});
   auto p3 = run_task([](){ContinueableTask(3);});
   auto p4 = run_when(p1, [](){ContinueableTask(4);});
   auto p5 = run_when(p2, p3, [](){ContinueableTask(5);});
   auto p6 = run_when(p3, p4, [](){ContinueableTask(6);});
   wait_for_all(p1, p2, p3, p4, p5, p6);
}

I discovered looking through my web logs that folks are getting here searching for the Concurrency Runtime. 

This is my personal blog, but to assist I’ve added links to the documentation, code samples and team blog for ConcRT, PPL and Agents. I hope this helps people find what they are looking for.

-Rick

At the PDC I showed a demo of the new parallel stacks window in Visual Studio 2010 and how task view and method view can make navigating a multi-threaded program in the debugger more intuitive when compared to the existing threads and stacks windows (thought these got better too).  I thought I’d take a moment and share the key points and the code I used for this.

The code is a simple deadlock of 5 tasks waiting on an event that is never set.  I don’t expect that you’ll be able to read the text on many of these pictures, but I believe the point will still clear (and you can always try this in VS 2010 yourself.

Call Stack & Thread Windows

This is the way that we’ve been debugging multi-threaded programs via the Call Stack & Thread windows.  If you’ve been here before it can be difficult if you have more than one thread to orient on and find your location. It’s often a matter of poking through each thread in the Threads window and checking the Call Stack window.

This is one of the reasons why in VS2010 you can now expand the Call Stack inline and search in the Threads window.  The inline expansion looking on and search actually can help significantly if you know what you’re looking for in a particular deep stack, but for this particular issue it’s not the most efficient way of seeing what’s going on…

The Parallel Stacks Window

The Parallel Stacks Window shows you all the stacks for all the threads at once. To help with the immense amounts of screen real estate required for this, it trims the fully qualified callstack name (you can still see it in a tooltip) and it also groups the related stacks so you can start seeing any relationships and in this case hopefully seeing why this app is deadlocked.

The Parallel Stacks Window: task view

Since this is an application build on tasks, we can set the filter to show only the running tasks and now the picture starts getting more clear (and the text is almost readable).   This is because the tasks view filters out the runtime portions of the callstack and only shows the stack frames that are part of the task.  You can see that we have 4 tasks running and it looks like they are waiting in event::wait.

The Parallel Stacks Window: method view

Switching the focus to event::wait and toggling ‘method view’ which will only show callers and callees in a particular method makes this incredibly obvious.

So here’s the code:

This was implemented with template recursion (thanks go to twoscomplement who’s colossal cave inspired tweet: “You are in a maze of twisty template overloads, all alike” inspired the particular code example.

template <int N>
void youre_in_a_maze()
{
    printf(“%dth task\n”,N);
    e.wait();
}

template <int N>
void of_template_overloads()
{
    youre_in_a_maze<N>();
};

template <int N>
void all_alike()
{
    of_template_overloads<N>();
};

template <int N>
struct colossal_task
{
    shared_ptr<colossal_task<N – 1>> task;
    task_group& m_tasks;
    colossal_task(task_group& tasks):m_tasks(tasks),task(new colossal_task<N – 1> (tasks))
    {
        m_tasks.run(*task);
    }
    void operator ()() const
    {
        all_alike<N>();
    }
};

template <>
struct colossal_task <0>
{
    task_group& m_tasks;
    colossal_task(task_group& tasks):m_tasks(tasks)
    {
    }
    void operator ()() const
    {
        printf(“0th task\n”);
    }
};

int main()
{
    task_group tasks;
    colossal_task<5> t(tasks);
    tasks.wait();
    return 0;
}