performance - 何时在 Haskell 中严格评估？

Question

据我所知! (称为 bangs)用于表示应严格评估表达式。但对我来说，把它们放在哪里或者根本就不是那么明显。

import qualified Data.Vector.Unboxed as V

main :: IO ()
main = print $ mean (V.enumFromTo 1 (10^9))

mean :: V.Vector Double -> Double

不同版本的均值:

-- compiled with O2 ~ 1.14s
mean xs = acc / fromIntegral len
    where !(len, acc)    = V.foldl' f (0,0) xs :: (Int, Double)
          f (len, acc) x = (len+1, acc+x)

-- compiled with O2 ~ 1.18s
mean xs = acc / fromIntegral len
    where (!len, !acc)   = V.foldl' f (0,0) xs :: (Int, Double)
          f (len, acc) x = (len+1, acc+x)

-- compiled with O2 ~ 1.75s
mean xs = acc / fromIntegral len
    where (len, acc)      = V.foldl' f (0,0) xs :: (Int, Double)
          f !(len, acc) x = (len+1, acc+x)

-- compiled with O2 ~ 1.75s
mean xs = acc / fromIntegral len
    where (len, acc)      = V.foldl' f (0,0) xs :: (Int, Double)
          f (len, acc) x = (len+1, acc+x)

-- compiled without options ~ 6s
mean xs = acc / fromIntegral len
    where (len, acc)     = V.foldl' f (0,0) xs :: (Int, Double)
          f (len, acc) x = (len+1, acc+x)

-- compiled without options ~ 12s
mean xs = acc / fromIntegral len
    where !(len, acc)    = V.foldl' f (0,0) xs :: (Int, Double)
          f (len, acc) x = (len+1, acc+x)

其中一些在直觉上是有意义的，但我希望它不是一种反复试验的方法。

有什么方法可以检测惰性评估何时会妨碍性能？除了严格测试每一个。

它只对像 mean 这样的简单函数有意义吗？应该一次性评估所有内容？

Answer 1

在您的示例中，爆炸模式围绕平均值的最终计算，或者更确切地说是其成分:

where (!len, !acc)   = V.foldl' f (0,0) xs :: (Int, Double)
where !(len, acc)   = V.foldl' f (0,0) xs :: (Int, Double)

但是(有一个明显的异常(exception))不是第二项，折叠功能本身:

       f (len, acc) x = (len+1, acc+x)

但是这个 f是 Action 的地方。在您的示例中，您注释的不同方式 (len,acc)似乎正在触发编译器对如何处理 f 采取微妙的不同观点。 .这就是为什么一切都显得有些神秘的原因。要做的就是处理 f直接地。

主要的面包和黄油点是在左折叠或累积循环中，必须严格评估所有累积的 Material 。否则你基本上只是用 foldl' 建立一个大表达式。然后当你最终用你积累的 Material 做某事时要求它折叠起来——在这里，最后计算平均值。

但是，在您的示例中， foldl'从未给出明确的严格函数来折叠:累积 len和 acc被困在一个常规的惰性 Haskell 元组中。

这里出现了严格的问题，因为您要积累不止一件东西，但需要将它们捆绑在一起成为您传递给 foldl' 的 f 操作的一个参数。 .这是写严格类型或记录做累加的典型案例；这需要一条短线

data P = P !Int !Double

然后你可以写

mean0 xs = acc / fromIntegral len
    where P len acc    = V.foldl' f (P 0 0) xs 
          f (P len acc) !x = P (len+1) (acc+x)

请注意，我没有标记 (P len acc)砰的一声，因为它明显处于弱头正常形式 - 你可以看到 P 并且不需要要求编译器使用 !/seq 找到它 - 因此 f在第一个参数中是严格的。在将严格性添加到 f 的一种情况下也是如此。

          f !(len, acc) x = (len+1, acc+x)

但是功能

          f (len, acc) x = (len+1, acc+x)

在第一个参数 pair 中已经很严格了，因为你可以看到最外面的构造函数 (,) , 并且不需要严格注解(它基本上只是告诉编译器找到它。)但是构造函数只是构造一个惰性元组，所以它在 len 中不是(明确)严格的和 acc

$ time ./foldstrict
5.00000000067109e8
real    0m1.495s

而在我的机器上，你最好的意思是:

$ time ./foldstrict
5.00000000067109e8
real    0m1.963s