{"id":2593,"date":"2008-06-06T00:16:00","date_gmt":"2008-06-06T00:16:00","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/pfxteam\/2008\/06\/06\/more-powerful-aggregations-in-plinq\/"},"modified":"2008-06-06T00:16:00","modified_gmt":"2008-06-06T00:16:00","slug":"more-powerful-aggregations-in-plinq","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/dotnet\/more-powerful-aggregations-in-plinq\/","title":{"rendered":"More Powerful Aggregations in PLINQ"},"content":{"rendered":"

In the June 2008 CTP, PLINQ aggregations are more powerful than they were in the December 2007 CTP. The reason why they are more powerful is a bit subtle, but this new power enables many useful scenarios, so it is worth it to follow along with the explanation.<\/p>\n

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

To understand where the difference is coming from, let’s quickly review how aggregations work in LINQ to objects. As an example, consider a possible implementation of the Average operator, sans error handling:<\/p>\n

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

    <\/span>public<\/span> static<\/span> double<\/span> Average(this<\/span> IEnumerable<\/span><int<\/span>> source)<\/p>\n

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

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

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

        <\/span>return<\/span> source.Aggregate(<\/p>\n

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

            <\/span>new<\/span> double<\/span>[2],<\/p>\n

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

            <\/span>(acc, elem) => {<\/span><\/p>\n

                acc[0] += elem; acc[1]++; return<\/span> acc;<\/span><\/p>\n

            },<\/p>\n

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

            <\/span>acc => acc[0] \/ acc[1]);<\/p>\n

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

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

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

<\/p>\n

 <\/p>\n

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

The call to Aggregate takes three arguments:<\/p>\n

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

–<\/font>          <\/span><\/span><\/span>The initial accumulator value.<\/p>\n

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

–<\/font>          <\/span><\/span><\/span>A fold function that updates the accumulator for each element.<\/p>\n

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

–<\/font>          <\/span><\/span><\/span>A result conversion function that converts the final accumulator value to the actual answer.<\/p>\n

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

\n

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

Aggregate will initialize an accumulator to the value passed in the first argument: an array containing two doubles. Then, it will iterate over all elements in the input sequence, and maintain the sum of the elements seen so far in the first element of the accumulator array, and their count in the second element.  <\/span>Finally, to produce the desired answer, Aggregate will call the result conversion function, which divides the sum by the count, and returns the result.<\/p>\n

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

\n

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

Unfortunately, to parallelize the above example in PLINQ, it is not sufficient to simply add AsParallel on the data source. The problem is with the first argument in the Aggregate call. The user only gives us one array of doubles, and then reads and writes to it in the fold function. That is all fine if the fold function is always called from the same thread (and thus sequentially), but breaks down if we have multiple threads calling it concurrently.<\/p>\n

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

\n

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

In the December CTP, the aggregation APIs provided assumed that the user will never do such a thing. We always expected the fold function to return a new instance of the enumerator, like this:<\/p>\n

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

\n

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

    <\/span>public<\/span> static<\/span> double<\/span> Average(this<\/span> IEnumerable<\/span><int<\/span>> source)<\/p>\n

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

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

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

        <\/span>return<\/span> source.AsParallel().Aggregate(<\/p>\n

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

            <\/span>new<\/span> double<\/span>[2],<\/p>\n

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

            <\/span>(acc, elem) => {<\/p>\n

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

                <\/span>return<\/span> new<\/span> double<\/span>[] { acc[0] + elem, acc[1] + 1 };<\/span><\/p>\n

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

            <\/span>},<\/p>\n

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

            <\/span>(acc1, acc2) => {<\/p>\n

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

                <\/span>return<\/span> new<\/span> double<\/span>[] { acc1[0] + acc2[0], acc1[1] + acc2[1]};<\/p>\n

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

            <\/span>},<\/span><\/p>\n

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

            <\/span>acc => acc[0] \/ acc[1]);<\/p>\n

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

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

Notice that to help parallelize the aggregation, the user also gives us a function to combine two accumulators. That way, after each thread has iterated over a subset of the input, we can combine the partial answers to get the final result.<\/p>\n

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

\n

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

However, the main point of this example is to illustrate inefficiency in the above code. A small array has to be allocated for each element in the input. That is very likely to significantly hurt the performance of the aggregation, especially for aggregations like this one where the work involved in the actual aggregation operation (in this case, a few additions) is minimal.<\/p>\n

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

\n

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

To address this situation, the June 2008 CTP of PLINQ supports a new overload of aggregate. Rather than expecting a value<\/b> to initialize the accumulator to, the user gives us a factory function <\/b>that <\/b>generates the value:<\/p>\n

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

\n

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

    <\/span>public<\/span> static<\/span> double<\/span> Average(this<\/span> IEnumerable<\/span><int<\/span>> source)<\/p>\n

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

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

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

        <\/span>return<\/span> source.AsParallel().Aggregate(<\/p>\n

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

            <\/span>() => new<\/span> double<\/span>[2]<\/span>,<\/p>\n

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

            <\/span>(acc, elem) => { acc[0] += elem; acc[1]++; return<\/span> acc; },<\/p>\n

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

            <\/span>(acc1, acc2) => { acc1[0] += acc2[0]; acc1[1] += acc2[1]; return<\/span> acc1; },<\/p>\n

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

            <\/span>acc => acc[0] \/ acc[1]);<\/p>\n

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

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

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

\n

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

Now, PLINQ can initialize an independent accumulator for each thread. Now that each thread gets its own accumulator, both the folding function and the accumulator combining function are free to mutate the accumulators. PLINQ guarantees that accumulators <\/font>will not be accessed concurrently from multiple threads<\/font><\/a> <\/font><\/span><\/span><\/span>.<\/p>\n

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

\n

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

Here are several algorithms that can be efficiently implemented with the new Aggregate overload:<\/p>\n

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

\n

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

–<\/font>          <\/span><\/span><\/span>Randomly choose N elements from the input<\/font><\/a>.<\/p>\n

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

–<\/font>          <\/span><\/span><\/span>Aggregate statistics over the input sequence. E.g., compute the letter frequencies in a string.<\/p>\n

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

–<\/font>          <\/span><\/span><\/span>Find N smallest or largest element in the input, for a small N.<\/p>\n

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

\n

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

Also, it is worth pointing out that there is a strong similarity between the new Aggregate overload and the <\/font>Parallel.For overloads that manipulate thread-local state<\/font><\/a>. They both address the same type of issue – to allow different threads to mutate some local state.<\/p>\n

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

\n

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

Hope you enjoyed reading about the new capabilities of PLINQ aggregations. If you have comments on the API, or ideas on how aggregations apply to problems in your domain, make sure to let us know in the comments!<\/font><\/font><\/p><\/p>\n","protected":false},"excerpt":{"rendered":"

In the June 2008 CTP, PLINQ aggregations are more powerful than they were in the December 2007 CTP. The reason why they are more powerful is a bit subtle, but this new power enables many useful scenarios, so it is worth it to follow along with the explanation. To understand where the difference is coming […]<\/p>\n","protected":false},"author":481,"featured_media":58792,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[7908],"tags":[],"class_list":["post-2593","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-pfxteam"],"acf":[],"blog_post_summary":"

In the June 2008 CTP, PLINQ aggregations are more powerful than they were in the December 2007 CTP. The reason why they are more powerful is a bit subtle, but this new power enables many useful scenarios, so it is worth it to follow along with the explanation. To understand where the difference is coming […]<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/dotnet\/wp-json\/wp\/v2\/posts\/2593","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\/481"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/dotnet\/wp-json\/wp\/v2\/comments?post=2593"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/dotnet\/wp-json\/wp\/v2\/posts\/2593\/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=2593"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/dotnet\/wp-json\/wp\/v2\/categories?post=2593"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/dotnet\/wp-json\/wp\/v2\/tags?post=2593"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}