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

Recently I had an opportunity to do some refactoring in a raytracer that we use for demos at work.  I don’t how you feel about refactoring, but I personally find it an immensely calming and rewarding experience because it allows me to make improvements to quality and design in a very incremental and manner, even to old or large code bases.

I also really enjoy generic programming and I wanted to share this refactoring because it is a simple example of how using generic programming to rely on a compile time interface can reduce overall code. It also doesn’t rely on techniques that can make generic programming inaccessible like compile time polymorphism, typelists or the curiously recurring template pattern.

It’s borderline too simple to write down, but I’m doing it anyways so here it is…

Two similar classes a float3 and a color3

Before the refactoring, the raytracer had 2 classes that were used all over the place in the code, float3 and color.  Both of these are simple structs that had 3 data members.  Their definitions are incredibly similar and looked like this:

struct color3{
   float r;
   float g;
   float b;
   color3(){}
   color3(float r_, float g_, float b_):r(r_),g(g_),b(b_){}
};
struct float3{
   float x;
   float y;
   float z;
   float3(){}
   float3(float x_, float y_, float z_):x(x_),y(y_),z(z_){}
};

Sadly, 2 sets of methods to operate on the classes

Unfortunately, both of these classes also initially had strongly typed supporting functions like ‘add’ which were incredibly similar, only the float3 version used x,y and z while the color version used r, g, b:

color3 add(color3& c1, color3& c2)
{
   return color3(c1.r + c2.r, c1.g + c2.g, c1.b + c2.b);
}
float3 add(float3& v1, float3& v2)
{
   return color3(v1.x + v2.x, v1.y + v2.y, v1.z + v2.z);
}

Unfortunately while incredibly straightforward and seemingly simple, this isn’t very desirable. There were 4 or 5 functions like this that were essentially identical with the only difference being the types and member variable names.

These methods can be made generic

What I wanted was a simple way to write the add function once that added no additional size or instruction overheads to the structs, since both of these structs are used frequently inside a very tight loop, even small changes will have a noticable performance impact.  For example one of the refactorings I did removed a single call to the copy constructor and that increased the performance by about 50ms per frame ~12.5% (seriously) the scene I was looking at went from ~4 fps to ~5 fps on my quad core.

Here’s what I decided to do, I’ll explain in a moment, first I created a template function ‘add’:

template <class vec>
inline vec add(vec& v1, vec& v2)
{
    return vec(v1.first()  + v2.first(),
               v1.second() + v2.second(),
               v1.third()  + v2.third());
}

// implementation of first for float3
inline float first()
{
    return x;
}

// implementation of first for color3
inline float first()
{
    return r;
}

Did it make a difference?