{"id":530,"date":"2008-10-23T18:25:37","date_gmt":"2008-10-23T16:25:37","guid":{"rendered":"http:\/\/www.navision-blog.de\/2008\/10\/23\/using-plinq-in-f-parallel-map-and-fold-functions\/"},"modified":"2009-05-04T17:20:50","modified_gmt":"2009-05-04T15:20:50","slug":"using-plinq-in-fsharp-parallel-map-and-reduce-fold-functions","status":"publish","type":"post","link":"http:\/\/www.navision-blog.de\/blog\/2008\/10\/23\/using-plinq-in-fsharp-parallel-map-and-reduce-fold-functions\/","title":{"rendered":"Using PLINQ in F# \u2013 Parallel Map and Reduce (Fold) functions – part 1"},"content":{"rendered":"

If your wondering how Google computes query results in such a short time you have to read the famous \u201cMapReduce\u201d-Paper by Jeffrey Dean and Sanjay Ghemawat<\/a> (2004). It shows how one can split large tasks into a mapping and a reduce step which could then be processed in parallel.<\/p>\n

With PLINQ (part of the Parallel Extensions to the .NET Framework<\/a>) you can easily use \u201cMapReduce\u201d-pattern in .NET and especially F#. PLINQ will take care of all the MultiThreading and load balancing stuff. You only have to give PLINQ a map and a reduce (or fold) function.<\/p>\n

Lets consider a small example. Someone wants to compute the sum of the factorials of all integers from 1 to 3000. With List.map<\/em> and List.fold_left<\/em> this is a very easy task in F#:<\/p>\n

\n
#light<\/span><\/pre>\n
open<\/span> System<\/pre>\n
<\/pre>\n
let<\/span> add a b = a + b<\/pre>\n
let<\/span> fac (x:bigint) = [1I..x] |> List.fold_left (*) 1I<\/pre>\n
<\/pre>\n
let<\/span> sum =<\/strong><\/pre>\n
\u00a0 [1I..3000I]<\/strong><\/pre>\n
\u00a0\u00a0\u00a0 |> List.map fac<\/strong><\/pre>\n
\u00a0\u00a0\u00a0 |> List.fold_left add 0I<\/strong><\/pre>\n
<\/pre>\n
printfn \"Sum of Factorials: %A\"<\/span> sum<\/pre>\n
<\/pre>\n<\/div>\n
Of course you could do much much better if you don\u2019t compute every factorial on its own (I will show this in one of the next parts) – but for this time I need an easy function that is time consuming.<\/p>\n
This simple Task needs 27 sec. on my Core 2 Duo E6550 with 2.33 GHz and 3.5 GB RAM.<\/p>\n
But we can do better if we use parallel map and fold functions with help of PLINQ:<\/p>\n
\n
let<\/span> pMap (mapF:'a -><\/span> 'b) (data:IParallelEnumerable<'a>) =<\/pre>\n
\u00a0 ParallelEnumerable.Select(data, mapF)<\/pre>\n
<\/pre>\n
let<\/span> pFold foldF seed (data:IParallelEnumerable<'a>)=<\/pre>\n
\u00a0 ParallelEnumerable.Aggregate<'a,'b>(<\/pre>\n
    data, seed, new<\/span> Func<'b,'a,'b>(foldF))<\/pre>\n<\/div>\n
Now we can easily transform our calculation to a parallel version:<\/p>\n
\n
let<\/span> sum =<\/strong><\/pre>\n
\u00a0 [1I..3000I].AsParallel<bigint>()<\/strong><\/pre>\n
\u00a0\u00a0\u00a0 |> pMap fac <\/strong><\/pre>\n
\u00a0\u00a0\u00a0 |> pFold add 0I<\/strong><\/pre>\n<\/div>\n
Putting all together we can write a small test application:<\/p>\n
\n
#light <\/span><\/pre>\n
open<\/span> System<\/pre>\n
open<\/span> System.Linq<\/pre>\n
open<\/span> System.Diagnostics<\/pre>\n
<\/pre>\n
let<\/span> testRuntime f =<\/pre>\n
\u00a0 let<\/span> watch = new<\/span> Stopwatch()<\/pre>\n
\u00a0 watch.Start()<\/pre>\n
\u00a0 (f(),watch.Elapsed)<\/pre>\n
<\/pre>\n
let<\/span> add a b = a + b<\/pre>\n
let<\/span> fac (x:bigint) = [1I..x] |> List.fold_left (*) 1I<\/pre>\n
<\/pre>\n
let<\/span> list = [1I..3000I]<\/pre>\n
<\/pre>\n
let<\/span> pMap (mapF:'a -><\/span> 'b) (data:IParallelEnumerable<'a>)=<\/pre>\n
\u00a0 ParallelEnumerable.Select(data, mapF)<\/pre>\n
<\/pre>\n
let<\/span> pFold foldF seed (data:IParallelEnumerable<'a>)=<\/pre>\n
\u00a0 ParallelEnumerable.Aggregate<'a,'b>(<\/pre>\n
\u00a0\u00a0\u00a0 data, seed, new<\/span> Func<'b,'a,'b>(foldF))<\/pre>\n
<\/pre>\n
let<\/span> PLINQ() =<\/pre>\n
\u00a0 list.AsParallel<bigint>()<\/pre>\n
\u00a0\u00a0\u00a0 |> pMap fac<\/pre>\n
\u00a0\u00a0\u00a0 |> pFold add 0I<\/pre>\n
<\/pre>\n
let<\/span> sequential() =<\/pre>\n
\u00a0 list<\/pre>\n
\u00a0\u00a0 |> List.map fac<\/pre>\n
\u00a0\u00a0 |> List.fold_left add 0I<\/pre>\n
<\/pre>\n
let<\/span> (sumSequential,timeSequential) =<\/pre>\n
\u00a0 testRuntime sequential<\/pre>\n
printfn \"Time Normal: %.3fs\" <\/span>timeSequential.TotalSeconds<\/pre>\n
<\/pre>\n
let<\/span> (sumPLINQ,timePLINQ) =<\/pre>\n
\u00a0 testRuntime PLINQ<\/pre>\n
printfn \"Time PLINQ: %.3fs\"<\/span> timePLINQ.TotalSeconds<\/pre>\n
<\/pre>\n
timePLINQ.TotalSeconds \/ timeSequential.TotalSeconds<\/pre>\n
\u00a0 |> printfn \"Ratio: %.2f\"<\/span><\/pre>\n
<\/pre>\n
sumSequential = sumPLINQ<\/pre>\n
\u00a0 |> printfn \"Same Results: %A\"<\/span><\/pre>\n<\/div>\n
On my machine I get the following results:<\/p>\n
Time Normal: 27.955s<\/p>\n
Time PLINQ: 15.505s<\/p>\n
Ratio: 0.55<\/p>\n
Same Results: true<\/p><\/blockquote>\n
This means I get nearly a perfect load balancing on my two processors for this task.<\/p>\n
In part II<\/a> I describe how one can compute a series of functions in parallel.<\/p>\n","protected":false},"excerpt":{"rendered":"
If your wondering how Google computes query results in such a short time you have to read the famous \u201cMapReduce\u201d-Paper by Jeffrey Dean and Sanjay Ghemawat (2004). It shows how one can split large tasks into a mapping and a reduce step which could then be processed in parallel. With PLINQ (part of the Parallel […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[27,12,448],"tags":[664,534,660,464,463,450,462,665],"_links":{"self":[{"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts\/530"}],"collection":[{"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/comments?post=530"}],"version-history":[{"count":18,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts\/530\/revisions"}],"predecessor-version":[{"id":804,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts\/530\/revisions\/804"}],"wp:attachment":[{"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/media?parent=530"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/categories?post=530"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/tags?post=530"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}