{"id":2923,"date":"2007-12-07T14:33:00","date_gmt":"2007-12-07T14:33:00","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/pfxteam\/2007\/12\/07\/parallelizing-a-query-with-multiple-from-clauses\/"},"modified":"2007-12-07T14:33:00","modified_gmt":"2007-12-07T14:33:00","slug":"parallelizing-a-query-with-multiple-from-clauses","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/dotnet\/parallelizing-a-query-with-multiple-from-clauses\/","title":{"rendered":"Parallelizing a query with multiple \u201cfrom\u201d clauses"},"content":{"rendered":"

Consider a simplified version of Luke Hoban’s LINQ ray tracer<\/a><\/font><\/span><\/p>\n

var<\/span> Xs = Enumerable<\/span>.Range(1, screenWidth);<\/p>\n

<\/span><\/p>\n

var<\/span> Ys = Enumerable<\/span>.Range(1, screenHeight);<\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

var<\/span> sequentialQuery =   <\/span><\/p>\n

<\/span><\/p>\n

from<\/span> x in<\/span> Xs<\/p>\n

<\/span><\/p>\n

from<\/span> y in<\/span> Ys<\/p>\n

<\/span><\/p>\n

select<\/span> new<\/span> { X = x, Y = y, Color = TraceRay(x, y) };<\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

If the screen width is much larger than the screen height, we would choose to parallelize the computation along the screen width. This is because PLINQ would be more beneficial when the overhead to parallelize a given of piece work into n “chunks” is much lower than the running the “chunk of work” itself. Since the screen width is larger, there is more potential for creating bigger chunks of work and in turn getting a better payoff for the overhead of parallelizing as compared to the height. To change <\/font><\/span>sequentialQuery <\/span>to use PLINQ, we need to modify it to  <\/span> <\/span><\/p>\n

<\/font><\/span><\/p>\n

var<\/span> parallelAlongWidthQuery = <\/p>\n

<\/span><\/p>\n

from<\/span> x in<\/span> Xs.AsParallel() <\/span><\/b>\/\/Parallel along screen width<\/span><\/p>\n

<\/span><\/p>\n

from<\/span> y in<\/span> Ys<\/p>\n

<\/span><\/p>\n

select<\/span> new<\/span> { X = x, Y = y, Color = TraceRay(x, y) };<\/p>\n

<\/span><\/p>\n

Let us look at <\/font><\/span>parallelAlongWidthQuery <\/span>more closely. We can derive the exact methods that will be invoked for this query by referring to the <\/font><\/span>MSDN documentation on C# 3.0<\/font><\/span><\/a> – <\/span>26.7.1 Query Expression Translation. <\/span><\/b>Section 26.7.1.4 <\/b>explains that the <\/span><\/font>parallelAlongWidthQuery <\/span>will be translated to something like – <\/span><\/p>\n

<\/span><\/font><\/p>\n

(Xs.AsParallel()<\/span>)<\/span><\/b>.SelectMany(<\/p>\n

<\/span><\/p>\n

x => Ys, <\/p>\n

<\/span><\/p>\n

(x, y, Color) => new<\/span> {X = x, Y = y, Color = TraceRay(x, y)});<\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

The AsParallel () call converts Xs to an IParallelEnumerable type. [IParallelEnumerable enables the “parallel” implementations of the standard query operators] So, this query will bind to the Parallel version of SelectMany. When we run the application, we will notice that the query executes across all available processors on the machine.<\/p>\n

<\/font><\/span><\/p>\n

We have successfully parallelized the application!!<\/p>\n

<\/font><\/span><\/p>\n

<\/p>\n

 <\/font><\/p>\n

<\/span><\/p>\n

However, assume that our dataset was different to begin with<\/span><\/b> and the screen height was much larger than the screen width. Using the same logic for parallelizing along the larger sized dataset, we would choose Ys this time. To achieve this, it might be tempting to change the query to <\/p>\n

<\/span><\/font><\/p>\n

var<\/span> parallelAlongHeightQuery =      <\/span><\/p>\n

<\/span><\/p>\n

from<\/span> x in<\/span> Xs<\/p>\n

<\/span><\/p>\n

from<\/span> y in<\/span> Ys.AsParallel()<\/span><\/b>\/\/Parallel along screen height??<\/span><\/p>\n

<\/span><\/b><\/span><\/p>\n

select<\/span> new<\/span> { X = x, Y = y, Color = TraceRay(x, y) };<\/p>\n

<\/span><\/p>\n

<\/p>\n

<\/span><\/p>\n

<\/span><\/u><\/b><\/p>\n

<\/font><\/span> <\/p>\n

<\/span>Let us apply the query translation to <\/font><\/span>parallelAlongHeightQuery.<\/span> Using the <\/font><\/span>MSDN documentation on C# 3.0<\/font><\/span><\/a> <\/font>rules, we can say that <\/span><\/font>parallelAlongHeightQuery <\/span>will be translated <\/span>to something like – <\/span><\/p>\n

<\/span><\/font><\/p>\n

(Xs)<\/span><\/b>.SelectMany(<\/p>\n

<\/span><\/p>\n

x => Ys.AsParallel()<\/span><\/b>, <\/p>\n

<\/span><\/p>\n

(x, y, Color) => new<\/span> {X = x, Y = y, Color = TraceRay(x, y)});<\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

Xs is of Enumerable type and the compiler will bind to the LINQ version of SelectMany and not the expected parallel version! <\/span>When we run the application, we will notice that the query does not<\/b> execute across all available processors on the machine.<\/p>\n

<\/span><\/font><\/p>\n

The 2 “from” clauses are not symmetric<\/b> as they seem!<\/span><\/p>\n

<\/span><\/font><\/p>\n

A good way to force parallelization across the screen height is to specify it as the first data source –<\/p>\n

<\/font><\/span><\/p>\n

var<\/span> parallelAlongHeightQuery =      <\/span><\/p>\n

<\/span><\/p>\n

from<\/span> y in<\/span> Ys.AsParallel()<\/span>\/\/Parallel along screen height<\/span><\/p>\n

<\/span><\/p>\n

from<\/span> x in<\/span> Xs<\/p>\n

<\/span><\/p>\n

select<\/span> new<\/span> { X = x, Y = y, Color = TraceRay(x, y) };<\/p>\n

<\/span><\/p>\n

This will translate to something like – <\/p>\n

<\/font><\/span><\/p>\n

(Ys.AsParallel()<\/span>)<\/span><\/b>.SelectMany(<\/p>\n

<\/span><\/p>\n

x => Xs, <\/p>\n

<\/span><\/p>\n

(x, y, Color) => new<\/span> {X = x, Y = y, Color = TraceRay(x, y)});<\/p>\n

<\/span><\/p>\n

Since Ys is now an IParallelEnumerable, this query will bind to the “parallel” version of SelectMany. When executed, we will notice that the query now runs across all available processors.<\/p>\n

<\/font><\/span><\/p>\n

One more point to note is that even though SelectMany accepts mutliple datasources, PLINQ will partition work across the first datasource only. This is because it assumes that partioning across just one of the dataset will give enough parallelization and speedup.<\/p>\n

<\/font><\/span><\/p><\/p>\n","protected":false},"excerpt":{"rendered":"

Consider a simplified version of Luke Hoban’s LINQ ray tracer var Xs = Enumerable.Range(1, screenWidth); var Ys = Enumerable.Range(1, screenHeight);   var sequentialQuery =   from x in Xs from y in Ys select new { X = x, Y = y, Color = TraceRay(x, y) };   If the screen width is much larger than […]<\/p>\n","protected":false},"author":480,"featured_media":58792,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[7908],"tags":[7911,7909,7910],"class_list":["post-2923","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-pfxteam","tag-code-samples","tag-parallel-extensions","tag-plinq"],"acf":[],"blog_post_summary":"

Consider a simplified version of Luke Hoban’s LINQ ray tracer var Xs = Enumerable.Range(1, screenWidth); var Ys = Enumerable.Range(1, screenHeight);   var sequentialQuery =   from x in Xs from y in Ys select new { X = x, Y = y, Color = TraceRay(x, y) };   If the screen width is much larger than […]<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/dotnet\/wp-json\/wp\/v2\/posts\/2923","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\/480"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/dotnet\/wp-json\/wp\/v2\/comments?post=2923"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/dotnet\/wp-json\/wp\/v2\/posts\/2923\/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=2923"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/dotnet\/wp-json\/wp\/v2\/categories?post=2923"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/dotnet\/wp-json\/wp\/v2\/tags?post=2923"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}