i'm trying learn f# , first attempt @ parallel programming. i'm working on puzzle find longest path through grid. pathfinding solution seems straightforward recursive algorithm. map/reduce find paths , return longest.
i have serial implementation , 3 different parallel implementations of map/reduce portion. on smaller grids, see marginal improvement in speed parallel implementations. on larger grid, parallel implementations slower! doing wrong?
the 3 parallel implementations are:
- array.parallel.map
- a map implementation using parallel.for came question: using array.parallel.map decreasing running time
- pseq.map f# powerpack
here typical timings 4 implementations using different size input grids:
4x4 grid getlongestpath 19.845400 getlongestpathparallelarray 18.626200 getlongestpathparallelfor 7.084200 getlongestpathpseq 163.271000 5x5 grid getlongestpath 818.967500 getlongestpathparallelarray 629.563000 getlongestpathparallelfor 725.072500 getlongestpathpseq 772.961300 6x6 grid getlongestpath 3941.354000 getlongestpathparallelarray 3609.441800 getlongestpathparallelfor 3509.890500 getlongestpathpseq 3295.218600 7x7 grid getlongestpath 24466.655300 getlongestpathparallelarray 32098.823200 getlongestpathparallelfor 35274.629500 getlongestpathpseq 24980.553600 here's code:
module pathfinder open system open system.threading.tasks open microsoft.fsharp.collections let listcontains item list = list.exists (fun x -> x = item) list let longestlist (x:int list) (y:int list) = if x.length >= y.length x else y let getneighborsnotalreadyinpath (neighbormap: map<int, int list>) path = neighbormap.[list.head path] |> list.filter (fun item -> not (listcontains item path)) let rec getlongestpathfromallneighbors neighbormap currentpath longestpath = let neighbors = getneighborsnotalreadyinpath neighbormap currentpath if neighbors = [] longestlist currentpath longestpath else neighbors |> list.map (fun neighbor -> getlongestpathfromallneighbors neighbormap (neighbor::currentpath) longestpath) |> list.reduce longestlist let getlongestpathfromposition neighbormap = getlongestpathfromallneighbors neighbormap [i] [] let getlongestpath (neighbormap: map<int, int list>) = [| 0..neighbormap.count-1 |] |> array.map (fun -> getlongestpathfromposition neighbormap i) |> array.reduce longestlist let getlongestpathparallelarray (neighbormap: map<int, int list>) = [| 0..neighbormap.count-1 |] |> array.parallel.map (fun -> getlongestpathfromposition neighbormap i) |> array.reduce longestlist let getlongestpathparallelfor (neighbormap: map<int, int list>) = let inline parallelmap (f: 't -> 'u) (array : 't[]) : 'u[]= let inputlength = array.length let result = array.zerocreate inputlength parallel.for(0, inputlength, fun -> result.[i] <- f array.[i]) |> ignore result [| 0..neighbormap.count-1 |] |> parallelmap (fun -> getlongestpathfromposition neighbormap i) |> array.reduce longestlist let getlongestpathpseq (neighbormap: map<int, int list>) = [| 0..neighbormap.count-1 |] |> pseq.map (fun -> getlongestpathfromposition neighbormap i) |> pseq.reduce longestlist here code build map input grid:
module gobstoppers open system type gobstoppercollection = { items: string[]; width: int; neighbormap: map<int, int list> } type gobstopper = { position: int; color: string; shape: string; } let creategobstopperfromstring (text:string) = { position = i; color = text.[0].tostring(); shape = text.[1].tostring() } let creategobstopper (itemarray: string[]) = creategobstopperfromstring itemarray.[i] let findneighbors (itemarray: string[]) rowwidth = let onleft = (i % rowwidth = 0) let onright = (i % rowwidth = rowwidth - 1) let ontop = (i < rowwidth) let onbottom = (i >= itemarray.length - rowwidth) [(if ontop || onleft -1 else - rowwidth - 1); (if ontop -1 else - rowwidth); (if ontop || onright -1 else - rowwidth + 1); (if onleft -1 else - 1); (if onright -1 else + 1); (if onbottom || onleft -1 else + rowwidth - 1); (if onbottom -1 else + rowwidth); (if onbottom || onright -1 else + rowwidth + 1)] |> list.filter (fun x -> x > -1) let findcompatibleneighbors itemarray rowwidth = let arecompatible (a:gobstopper) (b:string) = a.color = b.[0].tostring() || a.shape = b.[1].tostring() findneighbors itemarray rowwidth |> list.map (fun x -> creategobstopper itemarray x) |> list.filter (fun x -> arecompatible x itemarray.[i]) |> list.map (fun x -> x.position) let load (text:string) = let itemarray = text.split('|') |> array.map (fun x -> x.trim()) |> array.filter (fun x -> x <> "") let rowwidth = int (sqrt (float itemarray.length)) let neighbormap = itemarray |> array.mapi (fun x -> i, findcompatibleneighbors itemarray rowwidth i) |> map.ofarray { items = itemarray; width = rowwidth; neighbormap = neighbormap } here's test input:
module testdata let testgrid3 = "|yr|rr|rs| |yr|gb|rp| |bs|gr|yb|" let testgrid4 = "|yr|rr|rs|gp| |yr|gb|rp|pp| |bs|gr|yb|bs| |br|rs|yb|bb|" let testgrid5 = "|yr|rr|rs|gp|rb| |yr|gb|rp|pp|gr| |bs|gr|yb|bs|bp| |br|rs|yb|bb|bc| |gs|yr|yr|rp|br|" let testgrid6 = "|yr|rr|rs|gp|rb|bc| |yr|gb|rp|pp|gr|pb| |bs|gr|yb|bs|bp|ps| |br|rs|yb|bb|bc|rs| |gs|yr|yr|rp|br|rb| |pp|gr|ps|pb|pr|ps|" let testgrid7 = "|yr|rr|rs|gp|rb|bc|rb| |yr|gb|rp|pp|gr|pb|rs| |bs|gr|yb|bs|bp|ps|pp| |br|rs|yb|bb|bc|rs|pb| |gs|yr|yr|rp|br|rb|br| |pp|gr|ps|pb|pr|ps|bp| |gc|rb|gs|pp|bc|gb|rp|" let testgrid8 = "|yr|rr|rs|gp|rb|bc|rb|bp| |yr|gb|rp|pp|gr|pb|rs|rp| |bs|gr|yb|bs|bp|ps|pp|gb| |br|rs|yb|bb|bc|rs|pb|pb| |gs|yr|yr|rp|br|rb|br|pr| |pp|gr|ps|pb|pr|ps|bp|rs| |gc|rb|gs|pp|bc|gb|rp|pp| |rp|gb|rs|ys|yc|yp|rb|bb|" here's console app timing:
open system open system.diagnostics let runtimer runcount title testfunc = printfn title let runtimedtest n = let stopwatch = stopwatch.startnew() let result = testfunc() stopwatch.stop() printfn "%i - %f" n stopwatch.elapsed.totalmilliseconds result let results = [| 1..runcount |] |> array.map (fun x -> runtimedtest x) printfn "%a" results.[0] let runcount = 1 let gobs = gobstoppers.load testdata.testgrid6 runtimer runcount "getlongestpath" (fun _ -> pathfinder.getlongestpath gobs.neighbormap) runtimer runcount "getlongestpathparallelarray" (fun _ -> pathfinder.getlongestpathparallelarray gobs.neighbormap) runtimer runcount "getlongestpathparallelfor" (fun _ -> pathfinder.getlongestpathparallelfor gobs.neighbormap) runtimer runcount "getlongestpathpseq" (fun _ -> pathfinder.getlongestpathpseq gobs.neighbormap) let line = console.readline()
if work scheduled cannot distributed in way can executed in parallel, add overhead when split work.
if work can executed in parallel across multiple cores, or waiting/idle time can used execute task while waiting, when might gain time.
in case calculation there no waiting on io. why code benefit multiple cores (if keep synchronisation low possible)
try executing code on more cores.
Comments
Post a Comment