Last active
August 29, 2015 14:13
-
-
Save Thorium/9bf54b83cb31e0677f17 to your computer and use it in GitHub Desktop.
Idea from Guy L. Steele - Organizing Functional Code for Parallel Execution; or, foldl and foldr Considered Slightly Harmful - https://vimeo.com/6624203
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Reduce / Aggregate / Fold | |
// Usual way makes deep recursion and trusts tail-opt: | |
// (a,b,c,d,e,f,g,h) => (((((((a + b) + c) + d) + e) + f) + g) + h) | |
// This more is quicksort-style parallel: | |
// (a,b,c,d,e,f,g,h) => (((a + b) + (c + d)) + ((e + f) + (g + h))) | |
// No Haskell Kinds support for F# so List and Array are easiest to make as separate methods. | |
open System.Threading.Tasks | |
module List = | |
let reduceParallel<'a> f (ie :'a list) = | |
let rec reduceRec f (ie :'a list) = function | |
| 1 -> ie.[0] | |
| 2 -> f ie.[0] ie.[1] | |
| len -> | |
let h = len / 2 | |
let o1 = Task.Run(fun _ -> reduceRec f (ie |> List.take h) h) | |
let o2 = Task.Run(fun _ -> reduceRec f (ie |> List.skip h) (len-h)) | |
Task.WaitAll(o1, o2) | |
f o1.Result o2.Result | |
match ie.Length with | |
| 0 -> failwith "Sequence contains no elements" | |
| c -> reduceRec f ie c | |
module Array = | |
let reduceParallel<'a> f (ie :'a array) = | |
let rec reduceRec f (ie :'a array) = function | |
| 1 -> ie.[0] | |
| 2 -> f ie.[0] ie.[1] | |
| len -> | |
let h = len / 2 | |
let o1 = Task.Run(fun _ -> reduceRec f (ie |> Array.take h) h) | |
let o2 = Task.Run(fun _ -> reduceRec f (ie |> Array.skip h) (len-h)) | |
Task.WaitAll(o1, o2) | |
f o1.Result o2.Result | |
match ie.Length with | |
| 0 -> failwith "Sequence contains no elements" | |
| c -> reduceRec f ie c | |
(* | |
Show case in F#-interactive with #time | |
> [1 .. 500] |> List.fold(fun a -> fun x -> System.Threading.Thread.Sleep(30);x+a) 0;; | |
Real: 00:00:15.654, CPU: 00:00:00.015, GC gen0: 0, gen1: 0, gen2: 0 | |
val it : int = 125250 | |
> [1 .. 500] |> List.reduceParallel(fun a -> fun x -> System.Threading.Thread.Sleep(30);x+a);; | |
Real: 00:00:02.710, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0 | |
val it : int = 125250 | |
> [|1 .. 500|] |> Array.fold(fun a -> fun x -> System.Threading.Thread.Sleep(30);x+a) 0;; | |
Real: 00:00:15.639, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0 | |
val it : int = 125250 | |
> [|1 .. 500|] |> Array.reduceParallel(fun a -> fun x -> System.Threading.Thread.Sleep(30);x+a);; | |
Real: 00:00:02.537, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0 | |
val it : int = 125250 | |
*) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment