haskell - 为什么在模式匹配前面添加波形符会减慢我的函数速度？

Question

我在一段 haskell 代码中定义了两个函数:

lengthwtilde [] = 0
lengthwtilde ~(_:xs) = 1 + lengthwtilde xs

lengthwotilde [] = 0
lengthwotilde (_:xs) = 1 + lengthwotilde xs

当我在 ghci 中测试它们时(使用 :set +s)，我发现 lengthwtilde (在模式匹配前面有波浪号的)执行速度明显比 lengthwotilde 慢约三秒。

*Main> lengthwtilde [1..10000000]
10000000
(19.40 secs, 1731107132 bytes)
*Main> lengthwotilde [1..10000000]
10000000
(16.45 secs, 1531241716 bytes)

这是为什么？

Answer 1

在模式匹配前面添加 ~ 使得该匹配无可辩驳。您可以将其视为向模式添加额外的惰性，以便它永远不会失败匹配，除非评估绝对需要该匹配。这是一个简单的例子:

Prelude> (\ (_:_) -> "non-empty") []
"*** Exception: <interactive>:2:2-23: Non-exhaustive patterns in lambda

Prelude> (\ ~(_:_) -> "oops") []
"oops"

使用无可辩驳的模式匹配，即使模式匹配在空列表上失败，由于没有评估绑定(bind)变量，因此不会出现错误。本质上，无可辩驳的模式匹配将函数转换为:

\ xs -> let (_:_) = xs in "oops"

正是这种额外的惰性包裹减慢了长度函数的速度。如果您将相同的let绑定(bind)转换应用于lengthwtilde，您将得到

lengthwtilde [] = 0
lengthwtilde xs' = let (_:xs) = xs' in 1 + lengthwtilde xs

考虑一下如何评估这一点。在顶层，您会得到1+lengthwtilde xs。但 xs 甚至没有被计算，因为它是一个 let 绑定(bind)的变量。因此，在下一步中，首先评估 xs 以确定它与 lengthwtilde 的第二种情况匹配，然后重复该过程。

将此与 lengthwotilde 进行对比。在此函数中，对函数的第二种情况进行匹配的行为也会强制对参数进行求值。最终结果是相同的，但是能够更快地打开它而不是强制另一个重击更加有效。

从技术上讲，lengthwtilde 稍微复杂一些:该参数已经在第二个分支中评估，因为这就是我们确定所处分支的方式，但是它会重新 -当传递到递归调用时被包装。

能够看到生成的核心很有用。以下是 lengthwotilde 的输出(由 ghc -O0 生成:

Foo.lengthwotilde =
  \ (@ t_afD)
    (@ a_afE)
    ($dNum_afF :: GHC.Num.Num a_afE)
    (eta_B1 :: [t_afD]) ->
    letrec {
      lengthwotilde1_af2 [Occ=LoopBreaker] :: [t_afD] -> a_afE
      [LclId, Arity=1]
      lengthwotilde1_af2 =
        \ (ds_dgd :: [t_afD]) ->
          case ds_dgd of _ {
            [] -> GHC.Num.fromInteger @ a_afE $dNum_afF (__integer 0);
            : ds1_dge xs_af1 ->
              GHC.Num.+
                @ a_afE
                $dNum_afF
                (GHC.Num.fromInteger @ a_afE $dNum_afF (__integer 1))
                (lengthwotilde1_af2 xs_af1)
          }; } in
    lengthwotilde1_af2 eta_B1

注意函数lengthwotilde1_af2立即对参数ds_dgd(这是输入列表)执行case，然后在case内部递归，形成一个 thunk(带有一些扩展):

1 + len [2..]
1 + (1 + len [3..])
1 + (1 + (1 + len [4..])

最终需要评估 1 + (1 + (1 + (1 + ..)))

这是lengthwtilde

Foo.lengthwtilde =
  \ (@ t_afW)
    (@ a_afX)
    ($dNum_afY :: GHC.Num.Num a_afX)
    (eta_B1 :: [t_afW]) ->
    letrec {
      lengthwtilde1_afM [Occ=LoopBreaker] :: [t_afW] -> a_afX
      [LclId, Arity=1]
      lengthwtilde1_afM =
        \ (ds_dgh :: [t_afW]) ->
          case ds_dgh of wild_X9 {
            [] -> GHC.Num.fromInteger @ a_afX $dNum_afY (__integer 0);
            : ipv_sgv ipv1_sgw ->
              GHC.Num.+
                @ a_afX
                $dNum_afY
                (GHC.Num.fromInteger @ a_afX $dNum_afY (__integer 1))
                (lengthwtilde1_afM
                   (case wild_X9 of _ {
                      [] ->
                        (Control.Exception.Base.irrefutPatError
                           @ () "foo.hs:(3,1)-(4,42)|(_ : xs)")
                        `cast` (UnsafeCo () [t_afW] :: () ~# [t_afW]);
                      : ds1_dgk xs_aeH -> xs_aeH
                    }))
          }; } in
    lengthwtilde1_afM eta_B1

对此的评估形成了不同的重击:

len [1..]
1 + (len (if null [1..] then error else [2..]))
1 + (len [2..])
1 + (1 + len (if null [2..] then error else [3..]))

最终会产生与第一次相同的添加链，但有一些额外的逻辑来处理无可辩驳的模式失败。

现在，如果您运行经过任何优化的编译代码，ghc 几乎肯定会发现参数不可能为空，因为它们已经被评估并且已知使用 (:) 此时的构造函数。当我使用 ghc -O2 编译代码并运行它时，两个函数的执行时间相同。它们都非常糟糕，因为无论哪种方式都会导致一连串的重击。 length 的标准定义要好得多，因为它是一个很好的 foldl' 定义。