何时在Haskell中进行严格评估？

Question

据我所知，!（称为bang）用于表示表达式应该被严格评估。但是对我来说，究竟在哪里放置它们或者是否需要放置它们并不那么明显。

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这样一次性评估所有内容的简单函数有意义吗？

- TomTom

---

如果您使用-O2而没有任何惊叹号模式呢？ - dfeuer

@dfeuer 刚刚添加了它。就像那个1.75秒时的错误放置的感叹号一样。 - TomTom

你是如何调用这个函数的，使用了什么参数？我发现结果有些出乎意料。我猜测 GHC 的严格性分析在这里并没有很好地工作！ - dfeuer

@dfeuer 我使用 stack build --ghc-options -O2 && time stack exec <project> 命令在 shell 中构建并运行它。 - TomTom

我最惊讶的是第一个，将最终结果对打，居然会有任何有用的作用；显然最终结果是严格的！ - dfeuer

Answer 1

在您的示例中，惊叹号模式在计算平均值或其组成部分周围移动：

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

但是（除了一个明显的例外），第二个项目并没有被包括在内，即折叠函数本身：

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

但是这里的f才是关键。在你的例子中，你注释(len, acc)的不同方式似乎会触发编译器对f要做什么的微妙不同的看法。这就是为什么一切似乎都有点神秘。应该直接处理f。

主要问题是，在左折叠或累加循环中，所有累积材料都必须被严格评估。否则，你基本上只是用foldl'建立一个大表达式，然后在最终计算平均值时要求它被折叠。

然而，在你的例子中，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)

在第一个参数中，即一对值中已经严格了，因为您可以看到最外层的构造函数(,)，并且不需要严格性标注（基本上只是告诉编译器去找它）。但是，该构造函数仅构造了一个惰性元组，因此len和acc在明确情况下并未被强制执行。

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

然而在我的机器上，您的最佳平均值是：

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

- Michael

---

你之前给我的一个问题写了一个很长的答案，但是你把它删除了。我找到了你，只是想说谢谢你的努力。它真的帮了我很多！ - matt

Answer 2

不是一成不变的规定，但当前最佳实践是使数据结构中的所有字段都是严格的（strict），但对于函数参数和返回结果采用惰性（lazy）方式（除了累加器）。

这样的效果是，只要您不触及返回值的某个部分，就不会进行任何评估。一旦您需要严格从中提取一点，整个结构就会立即被评估，这比在执行过程中惰性评估整个结构导致更可预测的内存/ CPU使用模式。

Johan Tibell 的性能指南是指出微妙之处的最佳方法：http://johantibell.com/files/haskell-performance-patterns.html#(1)。请注意，最近的 GHC 会自动执行小的严格字段展开，无需注释。还请参见严格编译选项。

关于何时引入严格字段：从一开始就做，因为事后强制执行它要困难得多。您仍然可以使用惰性字段，但仅当您明确需要它们时。

请注意：[]是惰性的，并且更多用作控制结构，预计会内联，而不是作为容器。对于后者，请使用vector等。

注2：有专门的库让您处理严格折叠（见foldl），或流式计算（conduit，pipes）。

更新

稍微解释一下原理，这样您就可以知道这不仅仅是为了天上的橡皮鸭子，还可以知道何时/为什么需要偏离规范。

为什么要评估严格？

一个案例是 严格积累，正如问题所述。这也有不太明显的形式 - 比如计算应用程序状态中发生某些事件的次数。如果您不存储严格计数，则会建立起一长串的 +1 thunks，造成很大的内存消耗，而没有任何好处（与只存储更新的计数相比）。

以上被非正式地称为 内存泄漏，即使它不是技术上的泄漏（没有丢失内存，只是保存时间比需要的长）。

另一种情况是 并行计算，其中工作被分配给多个线程。现在，很容易遇到这样的情况：您认为将计算分叉到了一个单独的线程中（使您的程序非常高效地并发），但后来意识到并发线程仅计算了惰性数据结构的最外层，而当值被强制时，大部分计算仍然在主线程上进行。

解决方案路径是使用来自 deepseq 的 NFData。但是，想象一下最终数据结构为 A (B (C)) 的层次结构，其中每个层由单独的线程计算，在返回前深度强制。现在，C 被深度强制（实际上在内存中遍历）三次，B 两次。如果 C 是一个深层/大型结构，则这是浪费的。这时您可以添加Once trick，或者只使用深度严格的数据结构，其中进行浅层强制到WHNF（而不是深度NF）具有与深度强制相同的效果，但 Once-trick 已由编译器处理，可以说。

现在，如果您保持一致和警觉，那么使用 deepseq+Once 可能会很好。

注意：在出现类似于并发评估的情况下，单线程评估也是一种非常相似的用例，尤其是在纯错误的可怕情况下，例如 undefined 和 error。理想情况下应该避免使用这些，但如果必须使用，解决问题的方法与上述类似（另请参见spoon包）。

- ron

---

拥有惰性字段通常非常有帮助。如果您想在其中存储函数，那么通常应该这样做。而且，与严格结构相比，惰性结构支持某些操作更好。通常包括任何类似于fmap、(<*>)或traverse的操作，包括镜头。 - dfeuer

不过，反过来不应该更好吗？显式地引入严格性和隐式地引入惰性？ - TomTom

您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - ron

TomTom：不确定您指的是什么。我建议的方法是明确注释严格性（但默认情况下这样做）。 - ron

我会包含Tibbe的懒惰风格指南部分。 - mucaho