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

Question

seq功能文档说明如下:

关于评估顺序的注释:表达式seq a b不保证a将在之前进行评估b.给出的唯一保证seq是,既a和b会前进行评估seq返回一个值.特别是,这意味着b可以在之前进行评估a.如果需要保证特定的评估顺序,则必须使用pseq"并行"软件包中的功能.

所以我有一个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'在递归调用之前始终对其进行求值.但是,与版本pseq相比,我看到性能下降seq.我机器上的数字(用于计算sum [1 .. 10^7]:

• 幼稚: 2.6s
• seq: 0.2s
• pseq: 0.5s

我正在使用GHC-8.2.2,我用stack ghc -- File.hs命令编译.

之后我尝试编译与stack ghc -- -O File.hs命令之间的性能差距seq并且pseq消失了.他们现在都参与其中0.2s.

那么我的实现是否展示了我想要的属性？或者GHC有一些实施的怪癖？为什么pseq慢？是否存在一些seq a b根据评估顺序具有不同结果的示例(相同的代码但不同的编译器标志/不同的编译器/等)？

Answer 1

答案至今都集中在seq对pseq性能问题,但我认为你本来想知道你们两个应该使用.

简短的回答是:虽然两者都应该在实践中生成几乎相同的代码(至少在打开适当的优化标志时),原语seq,而不是pseq,是您的情况的正确选择.pseq从绩效的角度来看,使用是非惯用的,令人困惑的,并且可能适得其反,而您使用它的原因是基于对其评估顺序保证意味着什么以及它在性能方面意味着什么的错误理解.虽然不能保证不同编译器标志集之间的性能(更不用说其他编译器),但如果您遇到seq上述代码版本运行速度明显慢于pseq使用"生产质量"优化标志的版本的情况. GHC编译器,您应该将其视为GHC错误并提交错误报告.

当然,答案更长的是......

首先,让我们清楚的是,seq和pseq是语义上的意义相同,它们都满足方程:

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返回,b 除非如果一些不相关的表达式a无法终止它将无法终止？(例外 - 没有双关语意思 - 就像处理异常一样,在开始评估另一个表达式之前,您可能会使用seq或deepSeq基于seq强制评估非终止表达式,以不受控制或受控的方式. )

相反,seq a b旨在强制评估a弱头正常形式,然后返回结果b以防止积累thunk.这个想法是,如果你有一个表达式b来构建一个可能在另一个未被评估的thunk之上累积的thunk a,你可以通过使用来防止这种累积seq a b."保证"是一个弱点:GHC保证它理解你不想在需要价值a时保持无价值seq a b的价值.从技术上讲,它并不能保证a将在"之前进行评估" b,无论这意味着什么,但您不需要这种保证. 当你担心,如果没有这个保证,GHC可能会首先评估递归调用并仍然累积thunk,这就像担心pseq a b可能会评估其第一个参数,然后等待15分钟一样荒谬(只是为了确保第一个参数已被评估) !),在评估第二个之前.

在这种情况下,您应该相信GHC做正确的事情.它可能看起来你,只有这样才能实现的性能优势seq a b是a评估前进行评估,以WHNF b开始,但可以想象的是,有在这个优化或其他情况,在技术上开始评估b(或者甚至是全面评估b,以WHNF)虽然a在短时间内没有评估,但仍然保留了语义,同时提高了性能seq a b.pseq相反,通过使用,您可以阻止GHC进行此类优化.(在你的sum程序情况下,毫无疑问没有这样的优化,但在更复杂的使用中seq,可能会有.)

第三,要了解什么是重要的pseq实际上是对.它首先在Marlow 2009中在并发编程的背景下进行了描述.假设我们要并行化两个昂贵的计算foo,bar然后组合(比如说,添加)它们的结果:

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

这里的意图是 - 当需要这个表达式的值时 - 它会创建一个foo并行计算的火花,然后通过seq表达式,bar在最终评估foo+bar哪个将等待之前,开始评估为WHNF(即,它的数值).foo添加和返回结果之前的火花.

在这里,可以想象GHC将认识到对于特定的数字类型,(1)foo+bar如果bar满足,则自动不能终止,满足正式的语义保证seq; (2)foo+bar对WHNF的评估将自动强制评估barWHNF以防止任何thunk积累,从而满足非正式实施保证seq.在这种情况下,GHC可以随意优化seq产量:

foo `par` foo+bar

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

什么GHC不够聪明才能意识到 - 如果foo在计划火花foo+bar之前开始评估in foo,火花就会消失,并且不会发生并行执行.

它只是在这种情况下,你需要明确地延迟要求激发表达式的值,以便在主线程"赶上"之前安排它,你需要额外的保证,pseq并且愿意拥有GHC放弃以下较弱保证所允许的额外优化机会seq:

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

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

结果是,如果你正在使用pseq除并发编程之外的任何东西,那么你使用它是错误的.(好吧,也许有一些奇怪的情况,但是......)如果你想要做的就是强制严格评估和/或thunk评估来提高非并发代码的性能,使用seq(或者用Haskell $!定义)seq根据($!)定义的严格数据类型是正确的方法.

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

Answer 2

我只看到关闭优化的这种差异.与ghc -O两者pseq和seq执行相同.

seq允许转换的轻松语义确实导致代码更慢.我想不出实际发生的情况.我们只是假设GHC做对了.不幸的是,我们没有办法用Haskell的高级语义来表达这种行为.

为什么pseq更慢？

pseq x y = x `seq` lazy y

pseq因此使用seq.观察到的开销是由于呼叫的额外间接pseq.

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

是否存在一些示例,其中seq ab具有不同的结果,具体取决于评估顺序(相同的代码但不同的编译器标志/不同的编译器/等)？

这可以抛出"a"或"b".

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

我想在文章中解释了Haskell中的异常,一个不精确异常的语义.