{"id":2743,"date":"2008-03-12T00:52:00","date_gmt":"2008-03-12T00:52:00","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/pfxteam\/2008\/03\/12\/ordering-the-output-of-parallel-computations\/"},"modified":"2008-03-12T00:52:00","modified_gmt":"2008-03-12T00:52:00","slug":"ordering-the-output-of-parallel-computations","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/dotnet\/ordering-the-output-of-parallel-computations\/","title":{"rendered":"Ordering the output of parallel computations"},"content":{"rendered":"

Frequently when attempting to do multiple operations in parallel, ordering becomes an issue.  Consider an application where I’m rendering and writing out to a video file frames of a movie:<\/p>\n

\n

for<\/span> (int<\/span> i = 0; i < numberOfFrames; i++)
<\/span>{
<\/span>    <\/span>var<\/span> frame = GenerateFrame(i);
<\/span>    <\/span>WriteToMovie(frame);
<\/span>}<\/span><\/p>\n<\/blockquote>\n

For a bit of pizzazz, I’ll show the same thing with LINQ:<\/p>\n

\n

var<\/span> frames = from<\/span> i in<\/span> Enumerable<\/span>.Range(0, numberOfFrames)
<\/span>             <\/span>select<\/span> GenerateFrame(i);
<\/span>foreach<\/span> (var<\/span> frame in<\/span> frames) WriteToMovie(frame);<\/span><\/p>\n<\/blockquote>\n

Now, my GenerateFrame method is expensive and computationally intensive, so I’d like to generate frames in parallel. For this example, we’ll assume that my GenerateFrame method is thread-safe and can be called concurrently (rendering one frame doesn’t modify any state used to render another frame), but access to my WriteToMovie method must be serialized:<\/p>\n

\n

using<\/span> (ManualResetEvent<\/span> mre = new<\/span> ManualResetEvent<\/span>(false<\/span>))
<\/span>{
<\/span>    <\/span>int<\/span> count = numberOfFrames;
<\/span>    <\/span>object<\/span> obj = new<\/span> object<\/span>();
<\/span>    <\/span>for<\/span> (int<\/span> i = 0; i < numberOfFrames; i++)
<\/span>    <\/span>{
<\/span>        <\/span>ThreadPool<\/span>.QueueUserWorkItem(state =>
<\/span><\/span>        <\/span>{
<\/span>            <\/span>var<\/span> frame = GenerateFrame((int<\/font>)state);
<\/span>            <\/span><\/span>lock<\/span>(obj) <\/span>WriteToMovie(frame);
<\/span><\/p>\n

 
<\/p>\n

<\/span>            <\/span>if<\/span> (Interlocked<\/span>.Decrement(ref<\/span> count) == 0)
                mre.Set();<\/p>\n

<\/span>        <\/span>}, state);
<\/span>    <\/span>}
<\/span> <\/span>   <\/span>mre.WaitOne();
<\/span>}<\/span><\/p>\n<\/blockquote>\n

Unfortunately, that’s quite a bit of code overhead, and it also suffers from a fundamental ordering problem: the frames may end up being written to the output movie file in an arbitrary order, based on when the frame generation completes.  A version with this ordering issue fixed might look like the following:<\/p>\n

\n

var<\/span> frames = new<\/span> Bitmap<\/span>[numberOfFrames];
<\/span>var<\/span> events = (from<\/span> i in<\/span> Enumerable<\/span>.Range(0, numberOfFrames)
<\/span>              <\/span>select<\/span> new<\/span> ManualResetEvent<\/span>(false<\/span>)).ToArray();<\/p>\n

<\/span>for<\/span> (int<\/span> i = 0; i < numberOfFrames; i++)
<\/span>{
<\/span>    <\/span>ThreadPool<\/span>.QueueUserWorkItem(state =>
<\/span>    <\/span>{
<\/span>        <\/span>int<\/span> frameNum = (int<\/span>)state;
<\/span>        <\/span>frames[frameNum] = GenerateFrame(frameNum);
<\/span>        <\/span>events[frameNum].Set();
<\/span>    <\/span>}, i);
<\/span>}
<\/span><\/p>\n

 
<\/p>\n

<\/span>for<\/span> (int<\/span> i = 0; i < numberOfFrames; i++)
<\/span>{
<\/span>    <\/span>events[i].WaitOne();
<\/span>    <\/span>WriteToMovie(frames[i]);
<\/span>}<\/span><\/p>\n<\/blockquote>\n

This has the general effect I want, but there are still some unfortunately overheads here (for example, I’m creating, setting, and waiting on a ManualResetEvent per frame). It’s also verbose.  Instead, I can use Future<T> from Parallel Extensions<\/a> to solve the same problem:<\/p>\n

\n

var<\/span> frames = (from<\/span> i in<\/span> Enumerable<\/span>.Range(0, numberOfFrames)
<\/span>              <\/span>select<\/span> Future<\/span>.Create(() => GenerateFrame(i))).
             ToArray();
<\/span>foreach<\/span> (var<\/span> frame in<\/span> frames) WriteToMovie(frame.Value);<\/span><\/p>\n<\/blockquote>\n

I love how close this is to the original LINQ version (and how much less code it is the than my previous ThreadPool sample).  Rather than selecting GenerateFrame(i), I’m selecting Future.Create(() => GenerateFrame(i)), and rather than calling WriteToMovie(frame), I’m calling WriteToMovie(frame.Value).  With those changes, the frames are now being computed in parallel (note I’m also using ToArray to calls the entire query to be enumerated), and they’re being written out to the movie file in the correct order without having to do any explicit locking or coordination.  Sweet!<\/p>\n

If I wanted to, I could do the same thing without LINQ, tracking the collection of futures explicitly:<\/p>\n

\n

var<\/span> frames = new<\/span> Queue<\/span><Future<\/span><Bitmap<\/span>>>();
<\/span>for<\/span> (int<\/span> i = 0; i < numberOfFrames; i++)
<\/span>{
    var<\/span> <\/span>num = i;
<\/span>    <\/span>frames.Enqueue(Future<\/span>.Create(() => GenerateFrame(num)));
<\/span>}
<\/span>while<\/span> (frames.Count > 0) WriteToMovie(frames.Dequeue().Value);<\/span><\/p>\n<\/blockquote>\n

I could also use PLINQ:<\/p>\n

\n

var<\/span> frames = from<\/span> i in<\/span> Enumerable<\/span>.Range(0, numberOfFrames).
    AsParallel(ParallelQueryOptions<\/span>.PreserveOrdering)
<\/span>             <\/span>select<\/span> GenerateFrame(i);
<\/span>foreach<\/span> (var<\/span> frame in<\/span> frames) WriteToMovie(frame);<\/span><\/p>\n<\/blockquote>\n

Three different approaches to solving the same problem with Parallel Extensions, and all of them requiring less code (and less complicated code) than my ThreadPool example.  Just makes you smile, doesn’t it? \ud83d\ude42<\/p><\/p>\n","protected":false},"excerpt":{"rendered":"

Frequently when attempting to do multiple operations in parallel, ordering becomes an issue.  Consider an application where I’m rendering and writing out to a video file frames of a movie: for (int i = 0; i < numberOfFrames; i++){    var frame = GenerateFrame(i);    WriteToMovie(frame);} For a bit of pizzazz, I’ll show the same thing with […]<\/p>\n","protected":false},"author":360,"featured_media":58792,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[7908],"tags":[7911,7909,7913,7910,7912,7914],"class_list":["post-2743","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-pfxteam","tag-code-samples","tag-parallel-extensions","tag-parallelism-blockers","tag-plinq","tag-task-parallel-library","tag-threadpool"],"acf":[],"blog_post_summary":"

Frequently when attempting to do multiple operations in parallel, ordering becomes an issue.  Consider an application where I’m rendering and writing out to a video file frames of a movie: for (int i = 0; i < numberOfFrames; i++){    var frame = GenerateFrame(i);    WriteToMovie(frame);} For a bit of pizzazz, I’ll show the same thing with […]<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/dotnet\/wp-json\/wp\/v2\/posts\/2743","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/dotnet\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/dotnet\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/dotnet\/wp-json\/wp\/v2\/users\/360"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/dotnet\/wp-json\/wp\/v2\/comments?post=2743"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/dotnet\/wp-json\/wp\/v2\/posts\/2743\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/dotnet\/wp-json\/wp\/v2\/media\/58792"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/dotnet\/wp-json\/wp\/v2\/media?parent=2743"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/dotnet\/wp-json\/wp\/v2\/categories?post=2743"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/dotnet\/wp-json\/wp\/v2\/tags?post=2743"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}