始终保证 `seq` 的评估顺序(另外还有 `pseq` 的奇怪行为)

Always guaranteed evaluation order of `seq` (with strange behavior of `pseq` in addition)

seq 函数的文档说明如下:

A note on evaluation order: the expression seq a b does not guarantee that a will be evaluated before b. The only guarantee given by seq is that the both a and b will be evaluated before seq returns a value. In particular, this means that b may be evaluated before a. If you need to guarantee a specific order of evaluation, you must use the function pseq from the "parallel" package.

所以我有一个带有累加器的 sum 函数的惰性版本:

sum :: Num a => [a] -> a
sum = go 0
  where
    go acc []     = acc
    go acc (x:xs) = go (x + acc) xs

显然,这在大列表上非常慢。现在我正在使用 seq:

重写这个函数
sum :: Num a => [a] -> a
sum = go 0
  where
    go acc []     = acc
    go acc (x:xs) = let acc' = x + acc
                    in acc' `seq` go acc' xs

而且我看到了巨大的性能提升!但我想知道它有多可靠?我是靠运气得到的吗?因为 GHC 可以首先评估递归调用(根据文档)并且仍然会累积 thunk。看起来我需要使用 pseq 来确保 acc' 在递归调用之前总是被评估。但是 pseqseq 版本相比,我发现性能有所下降。我机器上的数字(用于计算 sum [1 .. 10^7]:

我正在使用 GHC-8.2.2 并使用 stack ghc -- File.hs 命令进行编译。

在我尝试使用 stack ghc -- -O File.hs 命令编译后,seqpseq 之间的性能差距消失了。他们现在都 运行 在 0.2s.

那么我的实现是否展示了我想要的属性?还是 GHC 有一些实施怪癖?为什么 pseq 更慢?是否存在一些示例,其中 seq a b 根据评估顺序有不同的结果(相同的代码但不同的编译器 flags/different compilers/etc。)?

我只看到关闭优化后的差异。 使用 ghc -O pseqseq 执行相同的操作。

seq 的宽松语义允许进行转换,这确实会导致代码变慢。我想不出实际发生的情况。我们只是假设 GHC 做了正确的事情。不幸的是,我们没有办法根据 Haskell.

的高级语义来表达该行为

Why pseq is slower?

pseq x y = x `seq` lazy y

pseq因此使用seq实现。观察到的开销是由于调用 pseq.

的额外间接

即使这些最终得到优化,使用 pseq 代替 seq 也未必是个好主意。虽然更严格的排序语义似乎暗示了预期的效果(go 不会累积 thunk),但它可能会禁用一些进一步的优化:也许评估 x 和评估 y 可以分解为低级操作,其中一些我们不介意跨越 pseq 边界。

Does there exist some example where seq a b has different results depending on evaluation order (same code but different compiler flags/different compilers/etc.)?

这可以抛出 "a""b"

seq (error "a") (error "b")

我想论文中解释了 Haskell、A Semantics for imprecise exceptions.

中关于异常的基本原理

编辑: 我的理论失败了,因为我观察到的时间实际上受到分析本身的影响而严重扭曲;关闭分析后,数据与理论相悖。此外,GHC 版本之间的时间差异很大。即使是现在,我也在收集更好的观察结果,当我得出结论时,我会进一步编辑这个答案。


关于"why pseq is slower"这个问题,我有一个理论

    • 让我们将 acc' `seq` go acc' xs 重新表述为 strict (go (strict acc') xs)
    • 同样,acc' `pseq` go acc' xs 重新表述为 lazy (go (strict acc') xs)
    • 现在,让我们在 seq 的情况下将 go acc (x:xs) = let ... in ... 重新表述为 go acc (x:xs) = strict (go (x + acc) xs)
    • go acc (x:xs) = lazy (go (x + acc) xs)pseq 的情况下。

现在,很容易看出,在 pseq 的情况下,go 被分配了一个将在稍后计算的惰性 thunk。在sum的定义中,go从不出现在pseq的左边,因此,在sum的运行期间,根本不会求值被迫。此外,go 的每次递归调用都会发生这种情况,因此 thunk 会累积。

这是凭空而来的理论,但我确实有部分证据。具体来说,我确实发现 gopseq 的情况下分配了线性内存,但在 seq 的情况下却没有。如果您 运行 以下 shell 命令,您可能会亲眼看到:

for file in SumNaive.hs SumPseq.hs SumSeq.hs 
do
    stack ghc                \
        --library-profiling  \
        --package parallel   \
        --                   \
        $file                \
        -main-is ${file%.hs} \
        -o ${file%.hs}       \
        -prof                \
        -fprof-auto
done

for file in SumNaive.hs SumSeq.hs SumPseq.hs
do
    time ./${file%.hs} +RTS -P
done

-- 并比较go成本中心的内存分配。

COST CENTRE             ...  ticks     bytes
SumNaive.prof:sum.go    ...    782 559999984
SumPseq.prof:sum.go     ...    669 800000016
SumSeq.prof:sum.go      ...    161         0

后记

由于在哪些优化实际发挥什么作用的问题上似乎存在分歧,我将提供我的确切源代码和 time 措施,以便有一个共同的基线。

SumNaive.hs

module SumNaive where

import Prelude hiding (sum)

sum :: Num a => [a] -> a
sum = go 0
  where
    go acc []     = acc
    go acc (x:xs) = go (x + acc) xs

main = print $ sum [1..10^7]

SumSeq.hs

module SumSeq where

import Prelude hiding (sum)

sum :: Num a => [a] -> a
sum = go 0
  where
    go acc []     = acc
    go acc (x:xs) = let acc' = x + acc
                    in acc' `seq` go acc' xs

main = print $ sum [1..10^7]

SumPseq.hs

module SumPseq where

import Prelude hiding (sum)
import Control.Parallel (pseq)

sum :: Num a => [a] -> a
sum = go 0
  where
    go acc []     = acc
    go acc (x:xs) = let acc' = x + acc
                    in acc' `pseq` go acc' xs

main = print $ sum [1..10^7]

没有优化的时间:

./SumNaive +RTS -P  4.72s user 0.53s system 99% cpu 5.254 total
./SumSeq +RTS -P  0.84s user 0.00s system 99% cpu 0.843 total
./SumPseq +RTS -P  2.19s user 0.22s system 99% cpu 2.408 total

-O在一起的时间:

./SumNaive +RTS -P  0.58s user 0.00s system 99% cpu 0.584 total
./SumSeq +RTS -P  0.60s user 0.00s system 99% cpu 0.605 total
./SumPseq +RTS -P  1.91s user 0.24s system 99% cpu 2.147 total

-O2在一起的时间:

./SumNaive +RTS -P  0.57s user 0.00s system 99% cpu 0.570 total
./SumSeq +RTS -P  0.61s user 0.01s system 99% cpu 0.621 total
./SumPseq +RTS -P  1.92s user 0.22s system 99% cpu 2.137 total

可以看出:

  • 朴素变体在没有优化的情况下表现不佳,但在 -O-O2 下表现出色——在某种程度上它优于所有其他变体。

  • seq 变体具有良好的性能,通过优化几乎没有改善,因此无论是 -O 还是 -O2 Naive 变体都优于它。

  • pseq 变体的性能一直很差,比没有优化的 Naive 变体好两倍,比其他 -O-O2 变体差四倍。优化对它的影响与 seq 变体一样小。

到目前为止,答案都集中在 seqpseq 性能问题上,但我认为您最初想知道应该使用两者中的哪一个。

简短的回答是:虽然两者在实践中应该生成几乎相同的执行代码(至少在打开适当的优化标志时),原始 seq,而不是 pseq,是适合您情况的正确选择。使用 pseq 是非惯用的、令人困惑的,并且从性能的角度来看可能适得其反,并且您使用它的原因是基于对其评估顺序保证的含义及其暗示的含义的错误理解表现。虽然不能保证不同编译器标志集的性能(更不用说其他编译器),但如果您 运行 遇到上述代码的 seq 版本 运行s比使用 "production quality" 优化标志和 GHC 编译器的 pseq 版本慢得多,您应该将其视为 GHC 错误并提交错误报告。

长答案当然更长...

首先,让我们弄清楚 seqpseq语义上 相同,因为它们都满足方程式:

seq _|_ b = _|_
seq a b = b -- if a is not _|_
pseq _|_ b = _|_
pseq a b = b -- if a is not _|_

这实际上是他们中的任何一个在语义上保证的唯一事情,而且由于 Haskell 语言的定义(如 Haskell 报告中所给出的那样)只能——充其量—— - 语义保证并且不涉及性能或实现,没有理由在不同编译器或编译器标志之间保证性能的原因之间进行选择。

此外,在您特定的基于 seq 的函数 sum 版本中,不难看出 seq 没有使用未定义的调用的情况第一个参数但是定义的第二个参数(假设使用标准数字类型),所以你甚至没有 使用 seq 的语义属性。您可以将 seq 重新定义为 seq a b = b 并具有完全相同的语义。当然,您知道这一点——这就是为什么您的第一个版本没有使用 seq 的原因。相反,您使用 seq 是为了附带的性能副作用,因此我们超出了语义保证的领域,回到了特定 GHC 编译器实现和性能特征的领域(实际上并没有任何 保证 可言。

其次,这将我们带到 seq 预期目的 。它很少用于其语义属性,因为这些属性不是很有用。谁会想要计算 seq a b 到 return b 除了 如果一些不相关的表达式 a 未能终止,它应该无法终止? (异常——没有双关语——就像处理异常一样,你可以使用 seq 或基于 seqdeepSeq 来强制评估非终止表达式在开始计算另一个表达式之前,以不受控制或受控制的方式。)

相反,seq a b 旨在在 returning b 的结果之前强制对 a 的评估为弱头范式,以防止 thunk 的累积。这个想法是,如果你有一个表达式 b 构建了一个 thunk,这个 thunk 可能会累积在另一个由 a 表示的未评估的 thunk 之上,你可以通过使用 seq a b 来防止这种累积。 "guarantee" 是一个弱点:GHC 保证它理解您不希望 a 在需要 seq a b 的值时保持未计算的 thunk。从技术上讲,它不能保证 a 将是 "evaluated before" b,无论那是什么意思,但是 你不需要那个保证。 当你担心,如果没有这个保证,GHC 可能会首先评估递归调用并仍然累积 thunks,这就像担心 pseq a b 可能评估它的第一个参数,然后等待 15 分钟(只是为了绝对确保第一个参数已被评估!),然后评估其第二个。

在这种情况下,您应该相信 GHC 会做正确的事情。在您看来,实现 seq a b 性能优势的唯一方法是在 b 开始评估之前将 a 评估为 WHNF,但可以想象存在优化在这种或其他情况下,技术上开始评估 b(甚至完全评估 b 到 WHNF),同时让 a 短时间未评估以提高性能,同时仍保留 [=] 的语义32=]。通过使用 pseq 代替,您可以阻止 GHC 进行此类优化。 (在您的 sum 程序情况下,无疑没有这样的优化,但在 seq 的更复杂的使用中,可能会有。)

第三,理解 pseq 实际上是 for 很重要。它首先在 Marlow 2009 中在并发编程的上下文中进行了描述。假设我们想要并行化两个昂贵的计算 foobar,然后组合(比如,相加)它们的结果:

foo `par` (bar `seq` foo+bar)  -- parens redundant but included for clarity

这里的意图是——当需要这个表达式的值时——它会创建一个火花来并行计算 foo,然后通过 seq 表达式开始计算 bar 到 WHNF(即,它是数值,比如说),然后最终评估 foo+bar,这将等待 foo 的火花,然后再添加和 returning 结果。

在这里,可以想象 GHC 将识别对于特定的数字类型,(1) 如果 bar 终止,则 foo+bar 自动失败,满足 [=14= 的形式语义保证]; (2) 将 foo+bar 评估为 WHNF 将自动强制将 bar 评估为 WHNF 以防止任何 thunk 积累,从而满足 seq 的非正式实施保证。在这种情况下,GHC 可能会随意优化 seq 以产生:

foo `par` foo+bar

特别是如果感觉在完成对 WHNF 的 bar 评估之前开始评估 foo+bar 会更高效。

GHC 不够聪明,没有意识到——如果 foo+barfoo 的计算在 foo 火花被安排之前开始,火花将会熄灭,并且不会发生并行执行。

实际上只有在这种情况下,您需要显式延迟要求激发表达式的值,以便有机会在主线程之前安排它 "catches up" 您需要额外的保证pseq 并愿意让 GHC 放弃 seq 较弱保证所允许的额外优化机会:

foo `par` (bar `pseq` foo+bar)

在这里,pseq 将阻止 GHC 引入任何可能允许 foo+barbar 进入 WHNF 之前开始评估(可能使 foo 火花消失)的优化(我们希望这允许有足够的时间来安排火花)。

结果是,如果您将 pseq 用于除并发编程以外的任何其他用途,那么您就用错了。 (好吧,也许有一些奇怪的情况,但是......)如果你想要做的就是强制严格评估 and/or thunk 评估以提高非并发代码的性能,使用 seq (或 $! 根据 seq 定义或 Haskell 严格数据类型根据 $! 定义)是正确的方法。

(或者,如果要相信@Kindaro 的基准测试,也许使用特定编译器版本和标志进行无情的基准测试是正确的方法。)