F #: Скажите мне, что мне не хватает в использовании Async.Parallel

Question

хорошо, так что я делаю ProjectEuler Problem # 14, и я возился с оптимизацией, чтобы почувствовать себя f # out.

в следующем коде:

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()

Почему код Async.Parallel ДЕЙСТВИТЕЛЬНО работает медленно по сравнению с картой прямого доступа? Я знаю, что не должен видеть такого эффекта, так как я использую только двухъядерный Mac.

Обратите внимание, что мне НЕ нужна помощь в решении проблемы # 14, я просто хочу знать, что случилось с моим параллельным кодом.

Answer 1

Использование Async.Parallel представляется правильным. Цифры действительно выглядят подозрительно, но я не сразу вижу, в чем здесь проблема.

В любом случае асинхронные рабочие процессы действительно больше подходят для вычислений, которые включают в себя некоторые асинхронные операции (такие как ввод-вывод, обмен данными, ожидание событий и т. Д.). Для задач, интенсивно использующих процессор, лучше использовать Parallel Extensions to .NET (которые теперь являются частью .NET 4.0; к сожалению, нет версии .NET 2.0).

Чтобы сделать это из F #, вам понадобится F # PowerPack и сборка FSharp.PowerPack.Parallel.Seq.dll, которая содержит параллельные версии функций высшего порядка для работы с последовательностями (например, map :-) )

Эти функции возвращают значение типа pseq<'a> (называемое ParallelQuery<T> в C #), которое представляет отложенное вычисление, выполняемое параллельно (это обеспечивает лучшую оптимизацию при использовании нескольких операций в конвейере). Также есть функция PSeq.reduce, поэтому вы можете использовать ее и при обработке (кроме PSeq.map).

Answer 2

На моем ящике требуется около полсекунды, чтобы запустить не асинхронный. Поскольку здесь имеется около полумиллиона рабочих элементов, это означает, что каждый из них выполняется в среднем около 1 микросекунды.

Эти элементы слишком малы, чтобы пытаться распараллелить их по отдельности. Затраты на выполнение потокового планирования и синхронизации будут доминировать в реальной работе. Вам нужно выбрать лучшую зернистость.

(я поработаю над некоторым быстрым кодом ...)

EDIT:

Хорошо, код «как есть» не так-то просто сделать заново, чтобы изменить гранулярность пакета без какой-либо серьезной перезаписи, поэтому у меня нет нового кода, которым можно поделиться, который не выдает слишком много. Но я смог заставить его работать почти вдвое быстрее на моем 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]

Эта программа использует умозрительный параллелизм с безопасным условием гонки и обеспечивает умеренное ускорение в два раза на моих 8 ядрах.