比这更通用的parfoldr

Question

我的目标是具有并行折叠功能.起初,它似乎很容易实现,这就是我的想法:

首先根据核心数(numCapabilities)将输入列表分解为分区.然后将foldr应用于每个分区,这将导致每个分区的折叠值列表.然后在该列表上再次执行折叠以获取最终值.

    listChunkSize = numCapabilities

    chunk n [] = []
    chunk n xs = ys : chunk n zs
      where (ys,zs) = splitAt n xs

    parfoldr f z [] = z
    parfoldr f z xs = res
      where
            parts = chunk listChunkSize xs
            partsRs = map (foldr f z) parts `using` parList rdeepseq
            res = foldr f z partsRs

上面的代码不起作用,因为很明显foldr的定义(a -> b -> b) -> b -> [a] -> b意味着输入列表类型(好,可以)与累加器和结果类型不同.

例如,

1)foldr (+) 0 [1..10]=> list type =累加器类型(整数)

2)foldr (\i acc -> (i>5) && acc) True [1..10]=>列表类型(整数)!=累加器类型(布尔)

因此,查看上面的代码,地图将生成一个类型列表,b 然后作为参数传递给第二个折叠器.但第二个foldr接受类型列表a.所以,那是行不通的.

一个丑陋的解决方案是为parfoldr提供不同类型的签名,例如 parfoldr :: (NFData a) => (a -> a -> a) -> a -> [a] -> a

这将有效,但它并不完全等同于foldr.上面的示例1会很好,但不是示例2.因此,问题1是:如何定义parfoldr以具有与foldr相同的类型签名？

比较2折:

    input = [1..1000000]
    seqfold = foldr (+) 0
    parfold = parfoldr (+) 0

我得到了foll.在双核机器上的时间:(无螺纹标志)

    $ ./test
    seqfold: 4.99s
    parfold: 25.16s

(螺纹标志上)

    $ ./test
    seqfold: 5.32s
    parfold: 25.55s
    $ ./test +RTS -N1
    seqfold: 5.32s
    parfold: 25.53s
    $ ./test +RTS -N2
    seqfold: 3.48s
    parfold: 3.68s
    $ ./test +RTS -N3
    seqfold: 3.57s
    parfold: 2.36s
    $ ./test +RTS -N4
    seqfold: 3.03s
    parfold: 1.70s

这些测量的观察结果如下:

• 当核心数量增加时,foldr似乎会降低运行时间.这是为什么？

• 对于N => 3,parfold提供更好的运行时间.

任何建议和改进的想法,赞赏:)

Answer 1

foldr通常不可并行化,因为它的接口允许顺序依赖.为了能够以您描述的方式重新排列计算,您需要将自己限制为具有标识元素的关联运算符.这被称为monoid,你实现的基本上是一个并行的mconcat.