在Haskell中是否有并行查找？

Question

我有一些我想在Haskell中解决的暴力问题.我的机器有16个内核,所以我想加快我当前的算法.

我有一个方法"tryCombination",它返回一个Just(String)或Nothing.我的循环看起来像这样:

findSolution = find (isJust)  [tryCombination a1 a2 a3 n z p |
                               a1 <- [600..700],
                               a2 <- [600..700],
                               a3 <- [600..700],
                               n  <- [1..100],
                               ....

我知道有一个特殊的parMap可以并行化地图功能.如果一个线程确实发现了第一次出现,那么mapFind可能很棘手,因为它是不可预测的.但是有没有类似mapAny的东西来加速搜索？

编辑:

我使用"withStrategy(parList rseq)"片段重写了代码.状态报告如下所示:

38,929,334,968 bytes allocated in the heap
 2,215,280,048 bytes copied during GC
     3,505,624 bytes maximum residency (795 sample(s))
       202,696 bytes maximum slop
            15 MB total memory in use (0 MB lost due to fragmentation)

                                  Tot time (elapsed)  Avg pause  Max pause
Gen  0     44922 colls, 44922 par   37.33s    8.34s     0.0002s    0.0470s
Gen  1       795 colls,   794 par    7.58s    1.43s     0.0018s    0.0466s

Parallel GC work balance: 4.36% (serial 0%, perfect 100%)

TASKS: 10 (1 bound, 9 peak workers (9 total), using -N8)

SPARKS: 17576 (8198 converted, 9378 overflowed, 0 dud, 0 GC'd, 0 fizzled)

INIT    time    0.00s  (  0.00s elapsed)
MUT     time   81.79s  ( 36.37s elapsed)
GC      time   44.91s  (  9.77s elapsed)
EXIT    time    0.00s  (  0.00s elapsed)
Total   time  126.72s  ( 46.14s elapsed)

Alloc rate    475,959,220 bytes per MUT second

Productivity  64.6% of total user, 177.3% of total elapsed

gc_alloc_block_sync: 834851
whitehole_spin: 0
gen[0].sync: 10
gen[1].sync: 3724

正如我已经提到的(参见我的评论),所有核心只工作了三秒钟(所有火花都被处理).以下30s所有工作都由一个核心完成.我怎样才能进一步优化？

更多编辑:

我现在尝试了"withStrategy(parBuffer 10 rdeepseq)"并尝试使用不同的缓冲区大小:

Buffersize    GC work Balance     MUT     GC
       10              50%     11,69s  0,94s
      100              47%     12,31s  1,67s
      500              40%     11,5 s  1,35s
     5000              21%     11,47s  2,25s

首先,我可以说,这是对没有任何多线程的59s的重大改进.第二个结论是,缓冲区大小应尽可能小,但要大于核心数.但最好的是,我既没有溢出也没有失败的火花.全部转换成功.

Answer 1

根据tryCombination所需的并行性和所需的并行化,其中一个可能会执行您想要的操作:

import Control.Parallel.Strategies
findSolution =
    find (isJust) $
    withStrategy (parList rseq) $
    [ tryCombination a1 a2 a3 n z p
    | a1 <- [600..700]
    , a2 <- [600..700]
    , a3 <- [600..700]
    , n  <- [1..100]]

这与执行的工作平行,tryCombination以确定它是a Just还是a Nothing,而不是实际结果Just.

如果没有这种懒惰可以被利用并且结果类型很简单,那么编写它可能会更好

findSolution =
    find (isJust) $
    withStrategy (parList rdeepseq) $
    [ tryCombination a1 a2 a3 n z p
    | a1 <- [600..700]
    , a2 <- [600..700]
    , a3 <- [600..700]
    , n  <- [1..100]]