F #: Tell me what I am missing in using Async.Parallel

Question

ok, so I'm doing ProjectEuler task number 14, and I was busy with optimizations to feel f # out.

in the following code:

let evenrule n = n / 2L
let oddrule n = 3L * n + 1L

let applyRule n =
    if n % 2L = 0L then evenrule n
    else oddrule n

let runRules n =
    let rec loop a final =
        if a = 1L then final
        else loop (applyRule a) (final + 1L)
    n, loop (int64 n) 1L


let testlist = seq {for i in 3 .. 2 .. 1000000 do yield i } 

let getAns sq = sq |> Seq.head

let seqfil (a,acc) (b,curr) = if acc = curr then (a,acc) else if acc < curr then (b,curr) else (a,acc)

let pmap f l = 
    seq { for a in l do yield async {return f a} }
    |> Seq.map Async.RunSynchronously

let pmap2 f l = 
    seq { for a in l do yield async {return f a} }
    |> Async.Parallel
    |> Async.RunSynchronously

let procseq f l = l
                  |> f runRules
                  |> Seq.reduce seqfil
                  |> fst

let timer = System.Diagnostics.Stopwatch()
timer.Start()
let ans1 = testlist |> procseq Seq.map // 837799    00:00:08.6251990
printfn "%A\t%A" ans1 timer.Elapsed
timer.Reset()

timer.Start()
let ans2 = testlist |> procseq pmap
printfn "%A\t%A" ans2 timer.Elapsed // 837799   00:00:12.3010250
timer.Reset()

timer.Start()
let ans3 = testlist |> procseq pmap2
printfn "%A\t%A" ans3 timer.Elapsed // 837799   00:00:58.2413990
timer.Reset()

Why is the Async.Parallel code REALLY slow compared to the direct picture? I know that I should not see such an effect, since I am only on a dual-core Mac.

Please note that I do NOT want to help solve problem No. 14, I just want to know what is happening with my parallel code.

Answer 1

Use Async.Parallelseems to be correct. The numbers really look suspicious, but I do not immediately see what might be the problem here.

, (, -, , ..). Parallel Extensions .NET( .NET 4.0, , .NET 2.0).

F #, F # PowerPack FSharp.PowerPack.Parallel.Seq.dll, (, map: -))

pseq<'a> ( ParallelQuery<T> #), , ( ). PSeq.reduce, ( PSeq.map).

Answer 2

. , , 1 .

, . . .

( ...)

EDIT:

, as-is , - , , . 2- , 50 000 " " " " 10 .

.

http://blogs.msdn.com/pfxteam/archive/2008/08/12/8849984.aspx

" ".

Answer 3

,

, .; -)

:

  let rec inside (a : _ array) n =
    if n <= 1L || a.[int n] > 0s then a.[int n] else
      let p =
        if n &&& 1L = 0L then inside a (n >>> 1) else
          let n = 3L*n + 1L
          if n < int64 a.Length then inside a n else outside a n
      a.[int n] <- 1s + p
      1s + p
  and outside (a : _ array) n =
    let n = if n &&& 1L = 0L then n >>> 1 else 3L*n + 1L
    1s + if n < int64 a.Length then inside a n else outside a n

  let euler14 n =
    let a = Array.create (n+1) 0s
    let a = Array.Parallel.init (n+1) (fun n -> inside a (int64 n))
    let i = Array.findIndex (Array.reduce max a |> (=)) a
    i, a.[i]

This program uses speculative parallelism with a safe race condition and achieves modest 2 × acceleration on my 8 cores.